Design theory and method of multivariate hash function  

作　　者：WANG HouZhen ZHANG HuanGuo WU QianHong ZHANG Yu LI ChunLei ZHANG XinYu 

机构地区：[1]The Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, School of Computer, Wuhan University, Wuhan 430072, China [2]Key Laboratory of Mathematics Mechanization, Beijing 100080, China

出　　处：《Science China(Information Sciences)》2010年第10期1977-1987,共11页中国科学（信息科学）（英文版）

基　　金：supported by the National High-Tech Research & Development Program of China (Grant No.2007AA01Z4);the National Natural Science Foundation of China (Grants Nos. 60970115, 60970116);the Open Project of Key Laboratory of Mathematics Mechanization (Grant No. KLMM0903)

摘　　要：This paper proposes a novel hash algorithm whose security is based on the multivariate nonlinear polynomial equations of NP-hard problem over a finite field and combines with HAIFA iterative framework. Over the current widely used hash algorithms, the new algorithm has the following advantages： its security is based on a recognized difficult mathematical problem; the hash length can be changed freely; its design can be automated such that users may construct specific hash function meeting the actual needs. Furthermore, we discuss the security, efficiency and performance of the new algorithm. Under some related difficult mathematical assumptions and theoretical analysis, the new algorithm is proven practical by the experiment results, and capable of achieving security of an ideal hash function by choosing suitable parameters. In addition, it can also be used as a pseudo-random number generator for the good randomness of its output.This paper proposes a novel hash algorithm whose security is based on the multivariate nonlinear polynomial equations of NP-hard problem over a finite field and combines with HAIFA iterative framework. Over the current widely used hash algorithms, the new algorithm has the following advantages： its security is based on a recognized difficult mathematical problem; the hash length can be changed freely; its design can be automated such that users may construct specific hash function meeting the actual needs. Furthermore, we discuss the security, efficiency and performance of the new algorithm. Under some related difficult mathematical assumptions and theoretical analysis, the new algorithm is proven practical by the experiment results, and capable of achieving security of an ideal hash function by choosing suitable parameters. In addition, it can also be used as a pseudo-random number generator for the good randomness of its output.

关 键 词：CRYPTOLOGY hash function MQ problem multivariate polynomials 

分 类 号：TN918.1[电子电信—通信与信息系统]