This talk will explain a new construction of secure cryptographic hash functions from Ramanujan graphs with a certain property. We propose constructing provable collision resistant hash functions from expander graphs in which finding cycles is hard. As an example, we give a specific family of optimal expander graphs for provable collision resistant hash function constructions: the family of Ramanujan graphs constructed by Pizer. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves over F_{p^2} with l-isogenies, l a prime different from p), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. Constructing the 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. If time permits we will discuss generalizations of Pizer's graphs to higher dimensional abelian varieties. Joint work with Denis Charles and Eyal Goren.
Copyright. All Rights Reserved.