You are looking at a specific version 20060123:205537 of this paper. See the latest version.

Paper 2006/021

Cryptographic hash functions from expander graphs

Denis Charles and Eyal Goren and Kristin Lauter

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionssupersingular elliptic curvesRamanujan graphs
Contact author(s)
klauter @ microsoft com
History
2006-01-23: received
Short URL
https://ia.cr/2006/021
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.