A generalized birthday problem. (English) Zbl 1026.94541

Yung, Moti (ed.), Advances in cryptology - CRYPTO 2002. 22nd annual international cryptology conference, Santa Barbara, CA, USA, August 18-22, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2442, 288-303 (2002).
Summary: We study a \(k\)-dimensional generalization of the birthday problem: given \(k\) lists of \(n\)-bit values, find some way to choose one element from each list so that the resulting \(k\) values XOR to zero. For \(k =2\), this is just the extremely well-known birthday problem, which has a square-root time algorithm with many applications in cryptography. In this paper, we show new algorithms for the case \(k >2:\) we show a cube-root time algorithm for the case of \(k =4\) lists, and we give an algorithm with subexponential running time when \(k\) is unrestricted.
We also give several applications to cryptanalysis, describing new subexponential algorithms for constructing one-more forgeries for certain blind signature schemes, for breaking certain incremental hash functions, and for finding low-weight parity check equations for fast correlation attacks on stream ciphers. In these applications, our algorithm runs in \(O(2^{2\sqrt{n}})\) time for an \(n\)-bit modulus, demonstrating that moduli may need to be at least 1600 bits long for security against these new attacks. As an example, we describe the first-known attack with subexponential complexity on Schnorr and Okamoto-Schnorr [see for example C. Schnorr, Security of blind discrete log signatures against interactive attacks, ICICS 2001, Lect. Notes Comput. Sci. 2229, 1-12 (2001)] blind signatures over elliptic curve groups.
For the entire collection see [Zbl 0997.00039].


94A60 Cryptography
60C05 Combinatorial probability
68Q25 Analysis of algorithms and problem complexity
94A62 Authentication, digital signatures and secret sharing
Full Text: Link