Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field

Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field

1991 | Alfred Menezes & Scott Vanstone, Tatsuaki Okamoto
This paper presents a method to reduce the elliptic curve logarithm problem to the discrete logarithm problem in a finite field extension. Specifically, for supersingular elliptic curves, the reduction is achieved in probabilistic polynomial time, providing a probabilistic subexponential time algorithm for the elliptic curve logarithm problem. The authors demonstrate that this reduction is useful for special classes of elliptic curves, including those recommended for implementation. The paper also discusses the implications of these results for public key cryptography, highlighting the importance of selecting appropriate elliptic curves to ensure security and efficiency. The main contributions include an algorithm for reducing the elliptic curve logarithm problem to a discrete logarithm problem in a finite field extension and a detailed analysis of the reduction for supersingular curves, showing that it can be performed in probabilistic polynomial time.This paper presents a method to reduce the elliptic curve logarithm problem to the discrete logarithm problem in a finite field extension. Specifically, for supersingular elliptic curves, the reduction is achieved in probabilistic polynomial time, providing a probabilistic subexponential time algorithm for the elliptic curve logarithm problem. The authors demonstrate that this reduction is useful for special classes of elliptic curves, including those recommended for implementation. The paper also discusses the implications of these results for public key cryptography, highlighting the importance of selecting appropriate elliptic curves to ensure security and efficiency. The main contributions include an algorithm for reducing the elliptic curve logarithm problem to a discrete logarithm problem in a finite field extension and a detailed analysis of the reduction for supersingular curves, showing that it can be performed in probabilistic polynomial time.
Reach us at info@study.space
[slides] Reducing elliptic curve logarithms to logarithms in a finite field | StudySpace