The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Reducing elliptic curve logarithms to logarithms in a finite field
Open accessAbstract
Previously, no general-purpose algorithm was known for the elliptic curve logarithm problem that ran in better than exponential time.In this paper we demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying hit e 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.The implications of our results to public key cryptography are discussed. , the subgroup of 2? generated by P, and the subgroup of nth roots of unity in Fqk, where n denot es the order of P. The isomorphism is given by the Weil pairing.Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.This is indeed the case for special classes of elliptic curves, including the
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Koblitz, N. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866109-5 · Cited by 5,634
The Arithmetic of Elliptic Curves
Silverman, J. H. (1986) · Graduate Texts in Mathematics · doi:10.1007/978-1-4757-1920-8 · Cited by 4,044
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Elliptic curves over finite fields and the computation of square roots mod 𝑝
Schoof, R. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777280-6 · Cited by 515
Discrete logarithms in finite fields and their cryptographic significance
Odlyzko, A. M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39757-4_20 · Cited by 367
Fast evaluation of logarithms in fields of characteristic two
Coppersmith, D. (1984) · IEEE Transactions on Information Theory · doi:10.1109/tit.1984.1056941 · Cited by 297
Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100295 · Cited by 285
Coppersmith, D., Odlzyko, A. M., & Schroeppel, R. (1986) · Algorithmica · doi:10.1007/bf01840433 · Cited by 271
Nonsingular plane cubic curves over finite fields
Schoof, R. (1987) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(87)90003-3 · Cited by 268
The Multiple Polynomial Quadratic Sieve
Silverman, R. D. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866119-8 · Cited by 159
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Self-citationElliptic Curve Public Key Cryptosystems
Menezes, A. (1993) · Springer eBooks · doi:10.1007/978-1-4615-3198-2 · Cited by 852
Self-citationA secure and efficient conference key distribution system: Extended abstract
Burmester, M., & Desmedt, Y. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053443 · Cited by 844
A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography
Malan, D. J., Welsh, M., & Smith, M. D. (2005) · 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004. IEEE SECON 2004. · doi:10.1109/sahcn.2004.1381904 · Cited by 712
jPBC: Java pairing based cryptography
De Caro, A., & Iovino, V. (2011) · 2011 IEEE Symposium on Computers and Communications (ISCC) · doi:10.1109/iscc.2011.5983948 · Cited by 703
Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes
Okamoto, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_3 · Cited by 581
Self-citationThe Weil Pairing, and Its Efficient Calculation
Miller, V. S. (2004) · Journal of Cryptology · doi:10.1007/s00145-004-0315-8 · Cited by 578
A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
Frey, G., & Ruck, H.-G. (1994) · Mathematics of Computation · doi:10.2307/2153546 · Cited by 551
A One Round Protocol for Tripartite Diffie–Hellman
Joux, A. (2004) · Journal of Cryptology · doi:10.1007/s00145-004-0312-y · Cited by 452
Shared generation of authenticators and signatures
Desmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_37 · Cited by 394
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE
Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., & Stebila, D. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978425 · Cited by 320
Efficient Elliptic Curve Exponentiation Using Mixed Coordinates
Cohen, H., Miyaji, A., & Ono, T. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49649-1_6 · Cited by 296
Metadata
- Authors
- Menezes, A., Vanstone, S., & Okamoto, T.
- Venue
- Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91
- Publisher
- ACM Press
- Published
- 1991
- Pages
- 80-89
- OpenAlex
- W2028358228
- Cited by
- 337
- References
- 20
- FWCI
- 12.70
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.