ZesT: an all-purpose hash function based on Zemor-Tillich

Hash functions are a very important cryptographic primitive. The collision resistance of provable hash functions relies on hard mathematical problems. This makes them very appealing for the cryptographic community since collision resistance is by far the most important property that a hash function should satisfy. However, provable hash functions tend to be slower than specially-designed hash functions like SHA, and their algebraic structure often implies homomorphic properties and weak behaviors on particular inputs. We introduce the ZesT hash function, a provable hash function that is based on the Zemor-Tillich hash function. ZesT is provably collision and preimage resistant if the balance problem corresponding to Zemor-Tillich is hard, a problem that has remained unbroken since CRYPTO'94. The function admits an ultra-lightweight implementation in ASIC and it is currently between 2 to 3 times less ecient than SHA on FPGA, and between 4 to 10 times slower than SHA in software. The function has structural parallelism, and its simplicity will certainly allow a much wider range of implementations and many code optimization techniques. A careful examination and pseudorandom tests performed with the Dieharder revealed no apparent malleability weakness, which suggests that the function can be used as a general-purpose hash function. Finally, ZesT can be slightly modied to reach all the requirements of the NIST competition. We stress that the hardness of the balance problem corresponding to Zemor-Tillich should be further studied and better established by the cryptography community. In that case, our function ZesT will denfinitely become a very appealing all-purpose hash function