Expander graphs based on GRH with an application to elliptic curve cryptography

2008/11/30 by David Jao, Stephen D. Miller, Ramarathnam Venkatesan
Computer Science · Mathematics · #Coding theory and cryptography #Cryptography and Residue Arithmetic #Geometric and Algebraic Topology #math.CO #math.NT

paper · pdf · doi:10.1016/j.jnt.2008.11.006

published as J. Number Theory 129 (2009), pp. 1491-1504 · 24 pages, to appear in the Journal of Number Theory

arxiv created 2009/01/15 · openalex publication_date 2009/02/24 · arxiv updated 2014/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our result implies that the Cayley graph of (Z/qZ)* with respect to small prime generators is an expander. As another application, we show that the graph of small prime degree isogenies between ordinary elliptic curves achieves non-negligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem.

Citations

• Elliptic curve cryptosystems
• Random Cayley graphs and expanders
• Reducing elliptic curve logarithms to logarithms in a finite field
• Extreme values of |ζ(1+it)|