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

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.

24 pages, to appear in the Journal of Number Theory

References in corpus (3)

• Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
• Extreme values of $|\zeta (1+it)|$
• More Discriminants with the Brezing-Weng Method

Cited by in corpus (7)

• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Computing endomorphism rings of elliptic curves under the GRH
• A low-memory algorithm for finding short product representations in finite groups
• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• Generating subgroups of ray class groups with small prime ideals
• ExpanderGraph-128: A Novel Graph-Theoretic Block Cipher with Formal Security Analysis and Hardware Implementation
• Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies