|
|||||
|
|
Expander graphs based on GRH with an application to elliptic curve cryptography |
|
| Authors: | David Jao Stephen D. Miller Ramarathnam Venkatesan |
| Affiliation: | a Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada b Department of Mathematics, 110 Frelinghuysen Road, Rutgers, The State University of New Jersey, Piscataway, NJ 08854, United States c Microsoft Research Cryptography and Anti-Piracy Group, 1 Microsoft Way, Redmond, WA 98052, United States d Cryptography, Security and Applied Mathematics Research Group, Microsoft Research India, Scientia - 196/36 2nd Main, Sadashivnagar, Bangalore 560 080, India |
| Abstract: | TextWe 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.VideoFor a video summary of this paper, please visit http://www.youtube.com/watch?v=7jwxmKWWsyM. |
| Keywords: | Expander graphs Elliptic curves Isogenies L-functions |
| 本文献已被 ScienceDirect 等数据库收录！ | |