## CryptoDB

### Paper: Cryptographic hash functions from expander graphs

Authors: Denis Charles Eyal Goren Kristin E. Lauter URL: http://eprint.iacr.org/2006/021 Search ePrint Search Google We propose constructing provable collision resistant hash functions from expander graphs. As examples, we investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves over ${\FF}_{p^2}$ with $\ell$-isogenies, $\ell$ a prime different from $p$), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. We estimate the cost per bit to compute these hash functions, and we implement our hash function for several members of the LPS graph family and give actual timings.
##### BibTeX
@misc{eprint-2006-21515,
title={Cryptographic hash functions from expander graphs},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / hash functions, supersingular elliptic curves, Ramanujan graphs},
url={http://eprint.iacr.org/2006/021},
note={ klauter@microsoft.com 13171 received 23 Jan 2006},
author={Denis Charles and Eyal Goren and Kristin E. Lauter},
year=2006
}