Miyaji Laboratory

Abstract

The security of elliptic curve cryptography is closely related to the computational complexity of the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against ECDLP are exponential-time, generic discrete logarithm algorithms such as Pollard's rho method. Recently, there is a line of research on index calculus for ECDLP started by Semaev, Gaudry, and Diem. Under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP in some cases. In this paper, we investigate the computational complexity of ECDLP for elliptic curves in various forms--including Hessian, Montgomery, (twisted) Edwards, and Weierstrass using index calculus. The research question we would like to answer is: Using index calculus, is there any significant difference in the computational complexity of ECDLP for elliptic curves in various forms? We will provide some empirical evidence and insights showing an affirmative answer in this paper.