International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Christophe Petit (#592)
Name Christophe Petit
Personal Homepage
Topic of his/her doctorate. Cryptographic hash functions from expander graphs
Category secret-key cryptography
Year of completion 2009
Abstract 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-Damgard. 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 defi ning 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 di fferent forms in other fi elds 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 de finitions of the literature and we describe its positive and negative consequences for applications. Finally, 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
E-Mail Address christophe.petit (at)
Last Change 2011-06-09 13:57:34
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR