On graph-based cryptographic hash functions

Hash functions are an invaluable tool for cryptography. They must primarily satisfy collision resistance, but standardized hash functions like SHA also satisfy stronger properties needed for the wide range of their applications. The design of many hash functions including SHA is based on a compression function that is close to a block cipher and on a domain extension transform like Merkle-Damgård. However, recent attacks against the collision resistance of SHA-1 suggest investigating new designs. The expander hash design, proposed in the early nineties by Zémor and Tillich and recently rediscovered by Charles, Goren and Lauter, consists in defining a cryptographic hash function from an expander graph. The design is simple and elegant and important hash function properties can be interpreted as graph properties. When Cayley expander graphs are used, collision resistance reduces to the hardness of group-theoretical problems. Although these problems are not classical in cryptography, they appear in different forms in other fields and in at least one case, they have remained unbroken since 1994. This thesis studies the expander hash design, its main strengths and weaknesses and the security and efficiency of currently existing instances. We introduce new functions, the Morgenstern hash function and the vectorial and projective versions of the Zémor-Tillich function. We study the security of particular constructions. We present new algorithms breaking the preimage resistance of the LPS hash function and the collision and preimage resistances of the Morgenstern hash function. We improve collision and preimage attacks against Zémor-Tillich and we describe hard and easy components of collision search for this function. We capture the malleability of expander hashes by two definitions of the literature and we describe its positive and negative consequences for applications. We introduce ZesT, an all-purpose hash function based on Zémor-Tillich, keeping its provable collision resistance and its parallelism but avoiding its malleability. Our function is provably secure, parallelizable, scalable, admits a wide range of (very) efficient implementations and can be used as a general-purpose hash function.