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

DOI10.1016/j.jnt.2008.11.006zbMath1228.05167arXiv0811.0647OpenAlexW2100201258MaRDI QIDQ1019852

Stephen D. Miller, Ramarathnam Venkatesan, David D. W. Yao

Publication date: 28 May 2009

Published in: Journal of Number Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.0647

zbMATH Keywords

elliptic curves\(L\)-functionsisogeniesexpander graphs

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Related Items (26)

The elliptic scalar multiplication graph and its application in elliptic curve cryptography ⋮ Quantum lattice enumeration and tweaking discrete pruning ⋮ On the hardness of the computational ring-LWR problem and its applications ⋮ Pseudorandom numbers and hash functions from iterations of multivariate polynomials ⋮ A Survey on some Applications of Graph Theory in Cryptography ⋮ Improved algorithm for the isogeny problem for ordinary elliptic curves ⋮ Isolated elliptic curves and the MOV attack ⋮ Séta: Supersingular Encryption from Torsion Attacks ⋮ A proof of the conjectured run time of the Hafner-McCurley class group algorithm ⋮ A subexponential-time, polynomial quantum space algorithm for inverting the CM group action ⋮ Generating subgroups of ray class groups with small prime ideals ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation ⋮ Towards practical key exchange from ordinary isogeny graphs ⋮ CSIDH: an efficient post-quantum commutative group action ⋮ Unnamed Item ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Post-quantum static-static key agreement using multiple protocol instances ⋮ Isogeny graphs of ordinary abelian varieties ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ A trade-off between classical and quantum circuit size for an attack against CSIDH ⋮ Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\) ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Threshold schemes from isogeny assumptions ⋮ Computing endomorphism rings of elliptic curves under the GRH ⋮ Random self-reducibility of ideal-SVP via Arakelov random walks

Cites Work

• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Note on the girth of Ramanujan graphs
• Ramanujan graphs
• The discrete logarithm problem on elliptic curves of trace one
• The distribution of values of \(L(1,\chi_d)\)
• Tough Ramsey graphs without short cycles
• Counting points on elliptic curves over finite fields
• A taxonomy of pairing-friendly elliptic curves
• Character sums in short intervals and the multiplication table modulo a large prime
• Endomorphisms of Abelian varieties over finite fields
• Die Typen der Multiplikatorenringe elliptischer Funktionenkörper
• The complexity of class polynomial computation via floating point approximations
• Computing modular polynomials in quasi-linear time
• Candidate One-Way Functions Based on Expander Graphs
• Explicit Bounds for Primality Testing and Related Problems
• Bits Security of the Elliptic Curve Diffie–Hellman Secret Keys
• Elliptic Curve Cryptosystems
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Random Cayley graphs and expanders
• Reducing elliptic curve logarithms to logarithms in a finite field
• Explicit bounds for primes in residue classes
• Advanced Topics in Computional Number Theory
• MV3: A New Word Based Stream Cipher Using Rapid Mixing and Revolving Buffers
• Discriminants of Complex Multiplication Fields of Elliptic Curves over Finite Fields
• Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
• Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves
• More Discriminants with the Brezing-Weng Method
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Expander graphs based on GRH with an application to elliptic curve cryptography