Abstract
Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of curves that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
Discrete logarithmSchoof's algorithmFinite fieldHessian form of an elliptic curveCounting points on elliptic curvesMathematicsElliptic curveElliptic curve cryptographyMultiplicative functionElliptic curve point multiplicationDiscrete mathematicsModular elliptic curveLogarithmProbabilistic logicPublic-key cryptographyReduction (mathematics)Field (mathematics)Pure mathematicsComputer scienceMathematical analysisStatisticsEncryptionQuarter period
Affiliated Institutions
Related Publications
The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
The Tate pairing is used to reduce the discrete logarithm (DL) problem on certain elliptic curves to the DL in the multiplicative group of finite fields.
A subexponential-time algorithm for computing discrete logarithms overGF(p^2)
An algorithm for computing discrete logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p^{2})</tex> , where <tex ...
An ID-based cryptosystem based on the discrete logarithm problem
In a modern network system, data security technologies such as cryptosystems, signature schemes, etc., are indispensable for reliable data transmission. In particular, for a lar...
An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1...
Algorithms for quantum computation: discrete logarithms and factoring
A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation tim...
Publication Info
- Year
- 1993
- Type
- article
- Volume
- 39
- Issue
- 5
- Pages
- 1639-1646
- Citations
- 1021
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1021
OpenAlex
Cite This
Alfred Menezes,
Takuya Okamoto,
Scott A. Vanstone
(1993).
Reducing elliptic curve logarithms to logarithms in a finite field.
IEEE Transactions on Information Theory
, 39
(5)
, 1639-1646.
https://doi.org/10.1109/18.259647
Identifiers
- DOI
- 10.1109/18.259647