On Building Hash Functions from Multivariate Quadratic Equations.
O. Billet, M. Robshaw, and T. Peyrin.
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.