Computer Science ›› 2013, Vol. 40 ›› Issue (6): 45-48.

Previous Articles     Next Articles

Improved Multivariate Hash Function

ZOU You-jiao,MA Wen-ping,RAN Zhan-jun and CHEN He-feng   

  • Online:2018-11-16 Published:2018-11-16

Abstract: A multivariate hash function based on multivariate public key cryptographic algorithm MI was researched and its security was analyzed so that the method to broke the hash function was found.For this reason,the improved hash function was proposed.The improved hash function can keep all advantages of the original hash function.Further more it is immune on the collision.Its preimage attack,second preimage attack,differential attack and algebraic attack were also analyzed in this paper.The avalanche effect and its stability of the improved hash function were tested on the basis of a mathematical model.The experiment data shows the improved hash function meets the strict avalanche criterion and its avalanche effect is perfect and stable.

Key words: MQ problem,Multivariate polynomials,Hash function,Avalanche effect

[1] Wang Xiao-yun,Yu Hong-bo.How to break MD5and otherhash functions[C]∥Proceedings of EUROCRYPT 2005,LNCS 3494.Berlin:Springer-Verlag,2005:19-35
[2] Wang Xiao-yun,Yao A C,Yao F.Cryptanalysis of SHA-1Hash Function[R].Cryptographic Hash Workshop,Invited Report.2005
[3] Wang Xiao-yun,Yu Hong-bo,Wang Wei,et al.Cryptanalysis on HMAC/NMAC-MD5and MD5-MAC[C]∥Proceedings of EUROCRYPT 2009.Berlin:Springer-Verlag,2009:121-133
[4] Federal Register.Government Printing Office[J]. 2007,72(212):62212-62220
[5] Gauravaram P,Knudsen L R,Matusiewicz K,et al.groestl_FinalRnd.zip.http://ehash.iaik.tugraz.at /wiki/groestl
[6] Ferguson N,Lucks S,Schneier B,et al.Skein_FinalRnd.zip.http://ehash.iaik.tugraz.at/wiki/Skein
[7] Aumasson J-P,Henzen L,Meier W,et al.Blake_FinalRnd.zip.http://ehash.iaik.tugraz.at/wiki/BLAKE
[8] Yuan Z,Wang W,Jia K T,et al.New birthday attacks on some MACs based on block ciphers[C]∥Proceedings of CRYPTO 2009.Berlin:Springer-Verlag,2009:209-230
[9] 王尚平,任娇霞,张亚玲,等.改进M-D结构的二次多变量hash函数[J].哈尔滨工业大学学报,2011,32(4):464-470
[10] Ding J T,Yang B Y.Multivariates polynomials for hashing.Cryptology ePrint Archive.http://eprint.iacr.org/2007/137.pdf,2007
[11] 王后珍,张焕国,杨飏.多变元Hash 函数的构造与分析[J].电子学报,2011,39(1):237-241
[12] Zou You-jiao,Ma Wen-ping,Ran Zhan-jun,et al.A New Multivariate Hash Function With HAIFA Construction[C]∥10th IEEE Int.Conf.on Trust,Security and Privacy in Computing and Communications, TrustCom 2011,8th IEEE Int.Conf.on Embedded Software and Systems,ICESS 2011,6th Int.Conf.on FCST 2011.2011:884-888
[13] Ding J T.Multivariate Public Key Cryptosystems[M].Berlin:Springer-Verlag,2006:11-190
[14] 王后珍,张焕国,伍前红,等.多变量Hash函数的构造理论和方法[J].中国科学:信息科学,2010,40(10):1299-1311
[15] Biham E,Dunkelman O.A framework for iterative hash func-tions-HAIFA[C]∥Proceedings of Second NIST Crypto-graphic Hash Workshop.2006
[16] Kelsey J,Schneier B.Second Preimages on n-Bit Hash Functions for Much Less than 2n[C]∥Cryptology,Proceedings of EUROCRYPT 2005,Lecture Notes in Computer Science 3494.Sprin-ger-Verlag,2005:474-490
[17] Adams W W,Loustaunau P.Introduction to Grbner Bases[D].Graduate Studies in Mathematics,American Mathematical Socie-ty,Providence,R.I.,1994
[18] Courtois N,Klimov A,Patarin J,et al.Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations[C]∥Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT).Lecture Notes in Computer Science.1807,Belgium:Springer,2000:392-407
[19] Ding J,Buchmann J,Mohamed M S,et al.MutantXL[C]∥Proc.Symbolic Computation and Cryptography.Beijing,2008:16-22
[20] Mohamed M S,Mohamed W S,Ding J,et al.MXL2:Solving po-lynomial equations over GF(2) using an improved mutant stra-tegy[C]∥ J.Buchmann,J.Ding,eds.Post-Quantum Cryptography-PQCrypto 2008(Cincinnati,2008).Lect.Notes Comput.Sci.5299.Berlin:Springer,2008:203-215
[21] Mohamed M S E,Cabarcas D,Ding Jin-tai,et al.MXL3:An efficient algorithm for computing Grbner bases of zero-dimensional ideals[C]∥Proceedings of ICISC 2009.Lect.Notes Comput.Sci.5984.Springer,2010:87-100
[22] Webster A,Tavares F,Stafford E.On the design of S-boxes[C]∥Advances in Cryptology-Crypto’85.Lecture Notes in Computer Science 218.New York,NY:Springer-Verlag,1985:523-534

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!