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) iacr.org.
Christophe Petit (#592)
Topic of his/her doctorate.
Cryptographic hash functions from expander graphs
Year of completion
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 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. 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
christophe.petit (at) uclouvain.be