Paper 2004/312
Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves
David Jao, Stephen D. Miller, and Ramarathnam Venkatesan
Abstract
Cryptographic applications using an elliptic curve over a finite field filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random selfreducibility for dlog over finite fields is well known; the nontrivial part here is that one must relate nonisomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare “random” type NIST FIPS 1862 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 random reducibilitydiscrete logelliptic curvesisogeniesmodular formsLfunctionsgeneralized Riemann hypothesisRamanujan graphsexpandersrapid mixing
 Contact author(s)
 miller @ math rutgers edu
 History
 20041116: received
 Short URL
 https://ia.cr/2004/312
 License

CC BY
BibTeX
@misc{cryptoeprint:2004/312, author = {David Jao and Stephen D. Miller and Ramarathnam Venkatesan}, title = {Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves}, howpublished = {Cryptology {ePrint} Archive, Paper 2004/312}, year = {2004}, url = {https://eprint.iacr.org/2004/312} }