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

JOURNAL OF NUMBER THEORY

卷:129

Article

Jao, David²  Miller, Stephen D.¹  Venkatesan, Ramarathnam^3,4 

[1] Rutgers State Univ, Dept Math, Piscataway, NJ 08854 USA

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[3] Microsoft Res Cryptog & Antipiracy Grp, Redmond, WA 98052 USA

[4] Microsoft Res India, Cryptog Secur & Appl Math Res Grp, Bangalore 560080, Karnataka, India

关键词: Expander graphs;    Elliptic curves;    Isogenies;    L-functions;   

DOI  :  10.1016/j.jnt.2008.11.006

来源: Elsevier

【 摘 要 】

Text. 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 nonnegligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem. Video. For a video summary of this paper, please visit http://www.youtube.com/watch?v=7jwxmKWWsyM. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free