A provably secure non-iterative hash function resisting birthday attack

详细信息    查看全文

• 作者：Shenghui Su^a ; ^b ; ^d ; ^{reesse@126.com} ; Tao Xie^a ; Shuwang Lü ; ^c
• 关键词：Hash function ; Compression algorithm ; Non-iterative structure ; Provable security ; Birthday attack ; Meet-in-the-middle attack
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：22 November 2016
• 年：2016
• 卷：654
• 期：Complete
• 页码：128-142
• 全文大小：454 K
• 卷排序：654

文摘

To examine the integrity and authenticity of an IP address efficiently and economically, this paper proposes a new non-iterative hash function called JUNA that is based on a multivariate permutation problem and an anomalous subset product problem to which no subexponential time solutions are found so far. JUNA includes an initialization algorithm and a compression algorithm, and converts a short message of n bits which is regarded as only one block into a digest of m   bits, where 80≤m≤23280≤m≤232 and 80≤m≤n≤409680≤m≤n≤4096. The analysis and proof show that the new hash is one-way, weakly collision-free, and strongly collision-free, and its security against existent attacks such as birthday attack and meet-in-the-middle attack is to O(2m)O(2m). Moreover, a detailed proof that the new hash function is resistant to the birthday attack is given. Compared with the Chaum–Heijst–Pfitzmann hash based on a discrete logarithm problem, the new hash is lightweight, and thus it opens a door to convenience for utilization of lightweight digital signing schemes.