Cryptographic Hash Functions from Expander Graphs |
| |
Authors: | Denis X Charles Kristin E Lauter Eyal Z Goren |
| |
Affiliation: | (1) Microsoft Research, Redmond, WA 98052, USA;(2) McGill University, Montréal, Canada, H3A 2K6 |
| |
Abstract: | We propose constructing provable collision resistant hash functions from expander graphs in which finding cycles is hard.
As examples, we investigate two specific families of optimal expander graphs for provable collision resistant 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
with ℓ-isogenies, ℓ a prime different from p), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. For the LPS
graphs, the underlying hard problem is a representation problem in group theory. Constructing our hash functions from optimal
expander graphs implies that the outputs closely approximate the uniform distribution. This property is useful for arguing
that the output is indistinguishable from random sequences of bits. We estimate the cost per bit to compute these hash functions,
and we implement our hash function for several members of the Pizer and LPS graph families and give actual timings. |
| |
Keywords: | Cryptographic hash functions Expander graphs Elliptic curve cryptography Isogenies Ramanujan graphs Supersingular elliptic curves |
本文献已被 SpringerLink 等数据库收录! |
|