CoChat
Sign Up
Cited by 4Cryptography and Residue ArithmeticAlgebraic Geometry and Number TheoryCryptography and Data Security

The DOI matches its Crossref record; the references it cites are not checked yet.

Isolated elliptic curves and the MOV attack

Open access
Scholl, Travis·2017·Journal of Mathematical Cryptology
DOI 10.1515/jmc-2016-0053
Open this paper in CoChat — free account

Abstract

We present a variation on the CM method that produces elliptic curves over prime fields with nearly prime order that do not admit many efficiently computable isogenies. Assuming the Bateman–Horn conjecture, we prove that elliptic curves produced this way almost always have a large embedding degree, and thus are resistant to the MOV attack on the ECDLP.

Overview

Integrity signals

Registry

Crossref · 10.1515/jmc-2016-0053

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

The citation lists haven’t been fetched yet

References 28 · Cited by 4

Research works printed but not linked: 37

  1. R. Balasubramanian and N. Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm, J. Cryptology 11 (1998), no. 2, 141–145. 10.1007/s001459900040 · DOI
  2. P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. 10.1090/S0025-5718-1962-0148632-7 · DOI
  3. R. Bröker, D. Charles and K. Lauter, Evaluating large degree isogenies and applications to pairing based cryptography, Pairing-Based Cryptography – Pairing 2008, Lecture Notes in Comput. Sci. 5209, Springer, Berlin (2008), 100–112. · DOI
  4. R. Bröker, K. Lauter and A. V. Sutherland, Modular polynomials via isogeny volcanoes, Math. Comp. 81 (2012), no. 278, 1201–1231. · DOI
  5. P.-J. Cahen and J.-L. Chabert, Integer-Valued Polynomials, Math. Surveys Monogr. 48, American Mathematical Society, Providence, 1997. · DOI
  6. H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts in Math. 138, Springer, Berlin, 1993. · DOI
  7. H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, 2006. · DOI
  8. A. C. Cojocaru and I. E. Shparlinski, On the embedding degree of reductions of an elliptic curve, Inform. Process. Lett. 109 (2009), no. 13, 652–654. 10.1016/j.ipl.2009.02.018 · DOI
  9. D. A. Cox, Primes of the Form x2+n⁢y2{x^{2}+ny^{2}}. Fermat, Class Field Theory, and Complex Multiplication, 2nd ed., Pure Appl. Math. (Hoboken), John Wiley & Sons, Hoboken, 2013.
  10. A. Entin, On the Bateman–Horn conjecture for polynomials over large finite fields, preprint (2014), http://arxiv.org/abs/1409.0846. · arXiv
  11. E. Fouvry and H. Iwaniec, Gaussian primes, Acta Arith. 79 (1997), no. 3, 249–287. 10.4064/aa-79-3-249-287 · DOI
  12. G. Frey, M. Müller and H.-G. Rück, The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans. Inform. Theory 45 (1999), no. 5, 1717–1719. 10.1109/18.771254 · DOI
  13. J. Friedlander and A. Granville, Limitations to the equi-distribution of primes. IV, Proc. Roy. Soc. London Ser. A 435 (1991), no. 1893, 197–204. 10.1098/rspa.1991.0138 · DOI
  14. J. Friedlander and H. Iwaniec, Using a parity-sensitive sieve to count prime values of a polynomial, Proc. Natl. Acad. Sci. USA 94 (1997), no. 4, 1054–1058. 10.1073/pnas.94.4.1054 · DOI
  15. J. Friedlander and H. Iwaniec, Opera de Cribro, Amer. Math. Soc. Colloq. Publ. 57, American Mathematical Society, Providence, 2010. · DOI
  16. D. Jao, S. D. Miller and R. Venkatesan, Do all elliptic curves of the same order have the same difficulty of discrete log?, Advances in Cryptology – ASIACRYPT 2005, Lecture Notes in Comput. Sci. 3788, Springer, Berlin (2005), 21–40. · DOI
  17. D. Jao, S. D. Miller and R. Venkatesan, Expander graphs based on GRH with an application to elliptic curve cryptography, J. Number Theory 129 (2009), no. 6, 1491–1504. 10.1016/j.jnt.2008.11.006 · DOI
  18. D. Jao and V. Soukharev, A subexponential algorithm for evaluating large degree isogenies, Algorithmic Number Theory, Lecture Notes in Comput. Sci. 6197, Springer, Berlin (2010), 219–233. · DOI
  19. J. Katz and Y. Lindell, Introduction to Modern Cryptography, 2nd ed., Chapman & Hall/CRC Cryptogr. Netw. Secur., CRC Press, Boca Raton, 2015.
  20. A. H. Koblitz, N. Koblitz and A. Menezes, Elliptic curve cryptography: The serpentine course of a paradigm shift, J. Number Theory 131 (2011), no. 5, 781–814. 10.1016/j.jnt.2009.01.006 · DOI
  21. D. Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996, http://echidna.maths.usyd.edu.au/~kohel/pub/thesis.pdf.
  22. J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic Number Fields, Academic Press, London (1977), 409–464.
  23. F. Luca, D. J. Mireles and I. E. Shparlinski, MOV attack in various subgroups on elliptic curves, Illinois J. Math. 48 (2004), no. 3, 1041–1052. · DOI
  24. A. J. Menezes, T. Okamoto and S. A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), no. 5, 1639–1646. 10.1109/18.259647 · DOI
  25. A. Menezes and E. Teske, Cryptographic implications of Hess’ generalized GHS attack, Appl. Algebra Engrg. Comm. Comput. 16 (2006), no. 6, 439–460. 10.1007/s00200-005-0186-8 · DOI
  26. A. Menezes, E. Teske and A. Weng, Weak fields for ECC, Topics in Cryptology – CT-RSA 2004, Lecture Notes in Comput. Sci. 2964, Springer, Berlin (2004), 366–386. · DOI
  27. S. D. Miller and R. Venkatesan, Spectral analysis of Pollard rho collisions, Algorithmic number theory, Lecture Notes in Comput. Sci. 4076, Springer, Berlin (2006), 573–581. · DOI
  28. M. Pandey, On Eisenstein primes, preprint (2016), https://arxiv.org/abs/1607.00469v1. · arXiv
  29. K. Rubin and A. Silverberg, Choosing the correct elliptic curve in the CM method, Math. Comp. 79 (2010), no. 269, 545–561. 10.1090/S0025-5718-09-02266-2 · DOI
  30. A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185-208 · DOI
  31. erratum, Acta Arith. 5 (1958), 259.
  32. R. Schoof, Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A 46 (1987), no. 2, 183–211. 10.1016/0097-3165(87)90003-3 · DOI
  33. V. Shoup, A Computational Introduction to Number Theory and Algebra, 2nd ed., Cambridge University Press, Cambridge, 2009. · DOI
  34. J. H. Silverman, The Arithmetic of Elliptic Curves, 2nd ed., Grad. Texts in Math. 106, Springer, New York, 2009. · DOI
  35. N. P. Smart, The discrete logarithm problem on elliptic curves of trace one, J. Cryptology 12 (1999), no. 3, 193–196. 10.1007/s001459900052 · DOI
  36. A. V. Sutherland, Isogeny volcanoes, ANTS X – Proceedings of the Tenth Algorithmic Number Theory Symposium, Open Book Ser. 1, Mathematical Sciences Publishers, Berkeley (2013), 507–530. · DOI
  37. W. Wang, Isolated curves for hyperelliptic curve cryptography, Ph.D. thesis, University of Washington, 2012, http://search.proquest.com/docview/1197791596.

Metadata

Authors
Scholl, T.
Affiliations
University of Washington (US)
Corresponding author
Scholl, Travis
ORCID
Scholl, Travis
Venue
Journal of Mathematical Cryptology
Publisher
Walter de Gruyter GmbH
Published
2017-05-11
Volume
11
Issue
3
Pages
131-146
ISSN
  • 1862-2976 (ISSN-L)
  • 1862-2984
DOI
10.1515/jmc-2016-0053
OpenAlex
W2614048686
Cited by
4
References
28
Citations by year
2021: 2 · 2020: 1 · 2019: 1
FWCI
1.02
Type
journal article
Language
en
Open access
Licence
Locations
  • Journal of Mathematical Cryptology (publishedVersion, cc-by-nc-nd)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
Topics
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
  • Physical Sciences › Mathematics › Geometry and Topology › Algebraic Geometry and Number Theory
  • Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
Keywords
elliptic curves, embedding degree, elliptic curve cryptography, discrete logarithm problem, isogenies, complex multiplication, Bateman-Horn conjecture, prime fields

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Isolated elliptic curves and the MOV attack. https://app.cochat.ai/papers/10.1515/jmc-2016-0053
The paper
Scholl, T. (2017). Isolated elliptic curves and the MOV attack. Journal of Mathematical Cryptology. https://doi.org/10.1515/jmc-2016-0053