Navigating in the Cayley graph of $$SL_2(\mathbb {F}_p)$$ S L 2 ( F p ) and applications to hashing
Navigating in the Cayley graph of $$SL_2(\mathbb {F}_p)$$ S L 2 ( F p ) and applications to hashing
复制标题
在 $$SL_2(mathbb {F}_p)$$ S L 2 ( F p ) 的凯莱图中导航以及哈希应用
DOI：
10.1007/s00233-015-9766-5
复制
发表时间：
2015
期刊：
影响因子：
0.7
通讯作者：
Bromberg L
中科院分区：
文献类型：
--
作者：
Bromberg L
Cayley 哈希函数基于一个简单的想法，即使用一对（半）组元素 A 和 B 分别对 0 和 1 位进行哈希处理，然后通过使用（半）组中元素的乘法以自然方式对任意位字符串进行哈希处理。在本文中，我们重点关注矩阵的哈希。由于有许多已知的矩阵对可以生成自由幺半群，因此对于足够大的素数，这会产生许多矩阵对，它们是抗碰撞散列的候选者。然而，这个技巧也有不利的一面，提升矩阵条目可能有助于发现冲突。 Tillich 和 Zémor 在两个矩阵 A 和 B 生成（作为幺半群）整个幺半群的特殊情况下成功地使用了这种“提升攻击”。然而，在本文中，我们表明，与其他“相似”矩阵对的情况不同，“提升攻击”可以（在某些情况下）在 A 和 B 生成的群中产生碰撞，但不会在正幺半群中产生碰撞。因此，我们认为，对于这些矩阵对，目前不存在会影响相应哈希函数安全性的已知攻击。我们还给出了与某些特定矩阵对相对应的哈希函数的冲突长度的明确下限。
Cayley hash functions are based on a simple idea of using a pair of (semi)group elements,AandB, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing withmatrices over. Since there are many known pairs ofmatrices overthat generate a free monoid, this yields numerous pairs of matrices over, for a sufficiently large primep, that are candidates for collision-resistant hashing. However, this trick has a flip side, and lifting matrix entries tomay facilitate finding a collision. This “lifting attack” was successfully used by Tillich and Zémor in the special case where two matricesAandBgenerate (as a monoid) the whole monoid. However, in this paper we show that the situation with other, “similar”, pairs of matrices fromis different, and the “lifting attack” can (in some cases) produce collisions in thegroupgenerated byAandB, but not in the positivemonoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from.