A provably secure non-iterative hash function resisting birthday attack

作     者：Su, Shenghui Xie, Tao Lu, Shuwang 

作者机构：Natl Univ Def Technol Sch Comp Changsha 410073 Hunan Peoples R China Beijing Univ Technol Lab Trusted Comp Beijing 100124 Peoples R China Univ Chinese Acad Sci Sch Comp Beijing 100039 Peoples R China BFID Corp Lab Computat Complex Beijing 100098 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2016年第654卷

页      面：128-142页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministry of Science and Technology of the People's Republic of China, MOST, (2009AA01Z441) Ministry of Science and Technology of the People's Republic of China, MOST National Natural Science Foundation of China, NSFC, (61472476) National Natural Science Foundation of China, NSFC 

主　　题：Hash function Compression algorithm Non-iterative structure Provable security Birthday attack Meet-in-the-middle attack 

摘      要：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 = 232 and 80 = 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 0(2(m)). 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. (C) 2016 Elsevier B.V. All rights reserved.