A Generalized Birthday Problem
A Generalized Birthday Problem
复制标题
DOI：
10.1007/3-540-45708-9_19
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
D. Wagner
中科院分区：
文献类型：
--
作者：
D. Wagner
我们研究了生日问题的k维推广：给定n位值的k个列表，找到某种方法从每个列表中选择一个元素，使得结果k值xor为零。Fork= 2，这只是非常著名的生日问题，它有一个平方根时间算法，在密码学中有许多应用。在本文中，我们展示了casek> 2的新算法：本文给出了k = 4列表情况下的一个立方根时间算法，并给出了k不受限制时的一个次指数运行时间算法.本文还给出了在密码分析中的几个应用，描述了新的次指数算法，用于构造某些盲签名方案的多一个正整数，用于破坏某些增量散列函数，以及用于找到用于对流密码的快速相关攻击的低权重奇偶校验方程。在这些应用程序中，我们的算法运行在O（22 n）的时间为ann位模，表明模可能需要至少1600位长的安全性，对这些新的攻击。作为一个例子，我们描述了第一个已知的攻击与次指数复杂性的Schnorr和Okamoto-Schnorr盲签名椭圆曲线群。
We study ak-dimensional generalization of the birthday problem: givenklists ofn-bit values, find some way to choose one element from each list so that the resultingkvalues xor to zero. Fork= 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 casek> 2: we show a cube-root time algorithm for the case ofk= 4 lists, and we give an algorithm with subexponential running time whenkis 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 inO(22√n) time for ann-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 blind signatures over elliptic curve groups.