nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

11.06.2018 | Original Paper

On the near prime-order MNT curves

verfasst von: Duc-Phong Le, Nadia El Mrabet, Safia Haloui, Chik How Tan

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely \(k = 3, 4\), and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valença to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree k and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves.

Vorheriger Artikel Several classes of binary linear codes and their weight enumerators

Nächster Artikel Three questions of Bertram on locally maximal sum-free sets

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The embedding degree is the smallest integer k such that r divides \((q^k-1)\).

Arène, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster computation of the Tate pairing. J Number Theory 131(5), 842–857 (2011)MathSciNetCrossRefMATH

Balasubramanian, R., Koblitz, N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone Algorithm. J Cryptol 11(2), 141–145 (1998). https://doi.org/10.1007/s001459900040 MathSciNetCrossRefMATH

Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Proceedings of the Cryptology in Africa 1st International Conference on Progress in Cryptology, AFRICACRYPT’08, pp. 389–405. Springer Berlin (2008). http://portal.acm.org/citation.cfm?id=1788634.1788672

Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Proceedings of the Advances in Crypotology 13th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT’07, pp. 29–50. Springer, Berlin (2007). http://portal.acm.org/citation.cfm?id=1781454.1781458

Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In: CRYPTO ’01: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, pp. 213–229. Springer (2001)

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd C. (ed.) ASIACRYPT ’01: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’01, pp. 514–532. Springer, London (2001)

Fotiadis, G., Konstantinou, E.: On the efficient generation of generalized mnt elliptic curves. In: Muntean T., Poulakis D., Rolland R. (eds.) Algebraic Informatics, Lecture Notes in Computer Science, vol. 8080, pp. 147–159. Springer, Berlin (2013). http://dx.doi.org/10.1007/978-3-642-40663-8_15

Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23, 224–280 (2010). https://doi.org/10.1007/s00145-009-9048-z MathSciNetCrossRefMATH

Frey, G., Rück, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865–874 (1994). https://doi.org/10.2307/2153546 MathSciNetMATH

10.

Galbraith, S., McKee, J., Valença, P.: Ordinary abelian varieties having small embedding degree. Finite Fields Appl. 13(4), 800–814 (2007). https://doi.org/10.1016/j.ffa.2007.02.003. http://www.sciencedirect.com/science/article/pii/S1071579707000147

11.

Grillet, P.A.: Abstract Algebra. Springer, Berlin (2007)MATH

12.

Iwaniec, H., Kowalski, E.: Analytic Number Theory. No. vol. 53 in American Mathematical Society Colloquium Publications. American Mathematical Society, Providence (2004)

13.

Urroz, J., Luca, F., Shparlinski, I.E.: On the number of isogeny classes of pairing-friendly elliptic curves and statistics of MNT curves. Math. Comput. 81(278), 1093–1110 (2012)MathSciNetCrossRefMATH

14.

Joux, A.: A one round protocol for Tripartite Diffie-Hellman. In: ANTS-IV: Proceedings of the 4th International Symposium on Algorithmic Number Theory, pp. 385–394. Springer (2000)

15.

Karabina, K., Teske, E.: On prime-order elliptic curves with embedding degrees k = 3, 4, and 6. In: Proceedings of the 8th International Conference on Algorithmic Number Theory, ANTS-VIII’08, pp. 102–117. Springer, Berlin (2008). http://portal.acm.org/citation.cfm?id=1789715.1789723

16.

Le, D.P., Mrabet, N.E., Tan, C.H.: On near prime-order elliptic curves with small embedding degrees. In: Algebraic Informatics—6th International Conference, CAI 2015, Stuttgart, Germany, September 1–4, 2015. Proceedings, pp. 140–151 (2015)

17.

Le, D.P., Tan, C.H.: Improved Miller’s algorithm for computing pairings on Edwards curves. IEEE Trans. Comput. 63(10), 2626–2632 (2014)MathSciNetCrossRefMATH

18.

Menezes, A., Vanstone, S., Okamoto, T.: Reducing elliptic curve logarithms to logarithms in a finite field. In: STOC ’91: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, pp. 80–89. ACM, New York (1991). http://doi.acm.org/10.1145/103418.103434

19.

Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans Fundam Electron Commun Comput Sci 84(5), 1234–1243 (2001)MATH

20.

Nagell, T.: Introduction to Number Theory. Wiley, New York (1951)MATH

21.

Page, D., Smart, N., Vercauteren, F.: A comparison of MNT curves and supersingular curves. Appl. Algebra Eng. Commun. Comput. 17(5), 379–392 (2006)MathSciNetCrossRefMATH

22.

Scott, M., Barreto, P.S.: Generating more MNT elliptic curves. Des. Codes Cryptogr. 38, 209–217 (2006). http://dx.doi.org/10.1007/s10623-005-0538-1. http://portal.acm.org/citation.cfm?id=1110940.1110952

Titel: On the near prime-order MNT curves
verfasst von: Duc-Phong Le
Nadia El Mrabet
Safia Haloui
Chik How Tan
Publikationsdatum: 11.06.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2019
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-018-0363-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2019

Three questions of Bertram on locally maximal sum-free sets

Quantum codes from cyclic codes over the ring

Several classes of binary linear codes and their weight enumerators

Four families of minimal binary linear codes with

Orthogonal matrix and its application in Bloom’s threshold scheme

On the Cipolla–Lehmer type algorithms in finite fields