62 citations · 134 across the 12 of their papers we have counts for
6 papers · 1 filter
Rigorous Analysis of a Randomised Number Field Sieve
Jonathan Lee, Ramarathnam Venkatesan
Factorisation of integers is of number theoretic and cryptographic significance. The Number Field Sieve (NFS) introduced circa 1990, is still the state of the art algorithm, bu…
Expander graphs based on GRH with an application to elliptic curve cryptography
David Jao, Stephen D. Miller, Ramarathnam Venkatesan
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 res…
Non-degeneracy of Pollard Rho Collisions
Stephen D. Miller, Ramarathnam Venkatesan
The Pollard Rho algorithm is a widely used algorithm for solving discrete logarithms on general cyclic groups, including elliptic curves. Recently the first nontrivial runtime esti…
Spectral Analysis of Pollard Rho Collisions
Stephen D. Miller, Ramarathnam Venkatesan
We show that the classical Pollard rho algorithm for discrete logarithms produces a collision in expected time O(sqrt(n)(log n)^3). This is the first nontrivial rigorous estimate f…
Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?
David Jao, Stephen D. Miller, Ramarathnam Venkatesan
The aim of this paper is to justify the common cryptographic practice of selecting elliptic curves using their order as the primary criterion. We can formalize this issue by asking…
Constructing elliptic curves with a known number of points over a prime field
Amod Agashe, Kristin Lauter, Ramarathnam Venkatesan
Elliptic curves with a known number of points over a given prime field with n elements are often needed for use in cryptography. In the context of primality proving, Atkin and Mora…