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. The authors demonstrate that for supersingular elliptic curves, this reduction can be done in probabilistic polynomial time, leading to a probabilistic subexponential time algorithm for the elliptic curve logarithm problem. The reduction is achieved through the use of the Weil pairing, which establishes an isomorphism between the subgroup generated by a point on the elliptic curve and the subgroup of nth roots of unity in an extension field. This allows the elliptic curve logarithm problem to be transformed into a discrete logarithm problem in a finite field, which can be solved more efficiently. The implications of this result for public key cryptography are discussed, highlighting the importance of carefully selecting elliptic curves for cryptographic applications. The paper also provides a detailed description of the reduction process, including algorithms for computing the discrete logarithm in finite fields and the Weil pairing. The results are applied to specific classes of elliptic curves, including supersingular curves, and the cryptographic implications of these results are discussed. The authors conclude that for supersingular curves, the elliptic curve discrete logarithm problem is more tractable than previously believed, and that care must be taken in selecting elliptic curves for cryptographic use.This paper presents a method to reduce the elliptic curve logarithm problem to the discrete logarithm problem in a finite field. The authors demonstrate that for supersingular elliptic curves, this reduction can be done in probabilistic polynomial time, leading to a probabilistic subexponential time algorithm for the elliptic curve logarithm problem. The reduction is achieved through the use of the Weil pairing, which establishes an isomorphism between the subgroup generated by a point on the elliptic curve and the subgroup of nth roots of unity in an extension field. This allows the elliptic curve logarithm problem to be transformed into a discrete logarithm problem in a finite field, which can be solved more efficiently. The implications of this result for public key cryptography are discussed, highlighting the importance of carefully selecting elliptic curves for cryptographic applications. The paper also provides a detailed description of the reduction process, including algorithms for computing the discrete logarithm in finite fields and the Weil pairing. The results are applied to specific classes of elliptic curves, including supersingular curves, and the cryptographic implications of these results are discussed. The authors conclude that for supersingular curves, the elliptic curve discrete logarithm problem is more tractable than previously believed, and that care must be taken in selecting elliptic curves for cryptographic use.