Abstract
Recent advances in hash functions cryptanalysis provide a strong impetus to explore new designs. This paper describes a new hash function mq-hash that depends for its security on the difficulty of solving randomly drawn systems of multivariate equations over a finite field. While provably achieving pre-image resistance for a hash function based on multivariate equations is relatively easy, naïve constructions using multivariate equations are susceptible to collision attacks. In this paper, therefore, we describe a mechanism—also using multivariate quadratic polynomials—yielding the collision-free property we seek while retaining provable pre-image resistance. Therefore, mq-hash offers an intriguing companion proposal to the provably collision-free hash function vsh.
This work has been supported in part by the French government through the SAPHIR and MAC projects.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aiello, W., Haber, S., Venkatesan, R.: New Constructions for Secure Hash Functions. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 150–167. Springer, Heidelberg (1998)
Augot, D., Finiasz, M., Sendrier, N.: A Family of Fast Syndrome Based Cryptographic Hash Functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 64–83. Springer, Heidelberg (2005)
Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: ICPSS, pp. 71–74 (2004)
Berbain, C., Gilbert, H., Patarin, J.: QUAD: A Practical Stream Cipher with Provable Security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 109–128. Springer, Heidelberg (2006)
Berbain, C.: Personal communication (November 21, 2006)
Bentahar, K., Page, D., Silverman, J.H., Saarinen, M.-J.O., Smart, N., LASH (2006), Available from: http://csrc.nist.gov/pki/HashWorkshop/2006/
Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320–335. Springer, Heidelberg (2002)
Contini, S., Lenstra, A.K., Steinfeld, R.: VSH, an Efficient and Provable Collision-Resistant Hash Function. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 165–182. Springer, Heidelberg (2006)
Damgård, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Ding, J., Schmidt, D.: Rainbow, a New Multivariable Polynomial Signature Scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005)
Fouque, P.-A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 341–353. Springer, Heidelberg (2005)
Fraenkel, A.S., Yesha, Y.: Complexity of Problems in Games, Graphs, and Algebraic Equations. Discr. Appl. Math. 1, 15–30 (1979)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co (1979)
Joux, A.: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In: Franklin, M.k. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)
Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2n Work. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005)
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar Signature Schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999)
Lenstra, A.K., Page, D., Stam, M.: Discrete logarithm variants of VSH. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 229–242. Springer, Heidelberg (2006)
Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.C.: One Way Hash Functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1989)
National Institute of Standards and Technology. FIPS 197: Advanced Encryption Standard (November 2001), Available from: http://csrc.nist.gov
National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard (August 2002), http://csrc.nist.gov
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Patarin, J., Courtois, N.T., Goubin, L.: QUARTZ, 128-Bit Long Digital Signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001)
Patarin, J., Courtois, N.T., Goubin, L.: FLASH, a Fast Multivariate Signature Algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001)
Peyrin, T., Gilbert, H., Muller, F., Robshaw, M.J.B.: Combining Compression Functions and Block Cipher-based Hash Functions. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 315–331. Springer, Heidelberg (2006)
Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis. Katholieke Universiteit Leuven (1993)
Ronald, L.: Rivest. RFC 1320: The MD4 Message-Digest Algorithm (April 1992), http://www.ietf.org/rfc/rfc1320.txt
Rivest, R.L.: RFC 1321: The MD5 Message-Digest Algorithm (April 1992), http://www.ietf.org/rfc/rfc1321.txt
Smid, M.E., Branstad, D.K.: Response to Comments of the NIST Proposed Digital Signature Standard. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 76–88. Springer, Heidelberg (1993)
Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving Underdefined Systems of Multivariate Quadratic Equations. Public Key Cryptography, 211–227 (2002)
Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Ziarko, W., Yao, Y. (eds.) RSCTC 2000. LNCS (LNAI), vol. 2005, pp. 17–36. Springer, Heidelberg (2001)
Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Wolf, C., Preneel, B.: Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations, http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Billet, O., Robshaw, M.J.B., Peyrin, T. (2007). On Building Hash Functions from Multivariate Quadratic Equations. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds) Information Security and Privacy. ACISP 2007. Lecture Notes in Computer Science, vol 4586. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73458-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-73458-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73457-4
Online ISBN: 978-3-540-73458-1
eBook Packages: Computer ScienceComputer Science (R0)