Konstruowanie krzywych genusu 2 z danym stopniem zanurzeniowym

Dryło, R.

Artykuł - szczegóły

Tytuł artykułu

Konstruowanie krzywych genusu 2 z danym stopniem zanurzeniowym

Autorzy

Dryło R.

Wybrane pełne teksty z tego czasopisma

http://sbn.wat.edu.pl/

Identyfikatory

Warianty tytułu

Constructing pairing-friendly genus 2 curves

Języki publikacji

Abstrakty

W kryptograﬁi opartej na iloczynach dwuliniowych stosuje się specjalne krzywe, dla których iloczyny dwuliniowe Weila i Tate można efektywnie obliczyć. Takie krzywe, zwykle nazywane pairing-friendly, mają mały stopień zanurzeniowy i wymagają specjalnej konstrukcji. W praktyce stosuje się głównie krzywe eliptyczne i hipereliptyczne genusu 2. Konstrukcje takich krzywych opierają się na metodzie mnożeń zespolonych (CM metodzie) i stąd ograniczają się do krzywych, których pierścień endomorﬁzmów jakobianu jest generowany przez odpowiednio małe liczby. Aby skonstruować krzywą najpierw wyznacza się parametry jej jakobianu, które zwykle są dane przez liczby Weila dla krzywych genusu 2, a następnie stosuje się CM metodę, aby znaleźć równanie krzywej. Freeman, Scott i Teske zebrali i opisali w ujednolicony sposób metody konstruowania krzywych eliptycznych z danym stopniem zanurzeniowym. Istnieje kilka różnych podejść do konstruowania krzywych genusu 2, z których pierwsze podali Freeman, Stevenhagen i Streng, Kawazoe-Takahashi i Freeman-Satoh. W tym opracowaniu opisujemy podejście oparte na idei autora, w którym wykorzystujemy odpowiednie wielomiany wielu zmiennych, aby jako ich wartości otrzymywać liczby Weila odpowiadające jakobianom krzywych genusu 2 z danym stopniem zanurzeniowym. Takie podejście pozwala konstruować zarówno krzywe genusu 2 o jakobianie absolutnie prostym oraz prostym, ale nie absolutnie prostym. Podajemy bezpośrednie wzory, które wyznaczają rodziny parametryczne krzywych genusu 2 z danym stopniem zanurzeniowym.

For applications in pairing-based cryptography we need special curves for which the Weil and Tate pairings can be eﬃciently computed. Such curves, commonly called pairing-friendly, require speciﬁc constructions. In practice we mainly use elliptic curves or hyperelliptic curves of genus 2. Methods for constructing pairing-friendly curves are based on the complex multiplication (CM) method, and thus are restricted to curves whose endomorphism ring of the Jacobian is generated by suitably small numbers. To construct such a curve one ﬁrst determines parameters of its Jacobian, which are usually given by Weil numbers for genus 2 curves, and then one uses the CM method to ﬁnd a curve equation. Methods for constructing pairing-friendly elliptic curves were gathered and described in a coherent language by Freeman, Scott and Teske. There are several approaches to construct pairing-friendly genus 2 curves the ﬁrst of which were developed by Freeman, Stevenhagen, and Streng, Kawazoe-Takahashi, and Freeman-Satoh. In this paper we describe an approach based on the idea of the author, where we use suitable polynomials of several variables to obtain as their values Weil numbers corresponding to Jacobians of pairing-friendly genus 2 curves. This approach can be used to construct both genus 2 with absolutely simple Jacobian, and with simple, but not absolutely simple. We give explicit formulas, which determine parametric families of pairing-friendly genus 2 curves.

Słowa kluczowe

kryptografia oparta na iloczynach dwuliniowych krzywe z danym stopniem zanurzeniowym iloczyny dwuliniowe Weila i Tate metoda CM liczby Weila

pairing-based cryptography pairing-friendly curves Weil and Tate pairings CM method Weil numbers

Wydawca

Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego

Czasopismo

Studia Bezpieczeństwa Narodowego

Rocznik

2014

Tom

R. 4, Nr 6

Strony

95--124

Opis fizyczny

Bibliogr. 45 poz.

Twórcy

autor

Dryło R.

rdrylo@sgh.waw.pl

Szkoła Główna Handlowa, Aleja Niepodległości 162, 02-554 Warszawa
Instytut Matematyczny PAN, ul. Śniadeckich 8, 00-950 Warszawa

Bibliografia

[1] P.S.L.M. Barreto, M. Naehrig, Pairing-friendly elliptic curves of prime order, in Selected Areas in Cryptography–SAC 2005, Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2006), pp. 319–331.
[2] P. Bateman, R. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comput. 16, 363–367 (1962).
[3] J. Belding, R. Bröker, A. Enge, K. Lauter, Computing Hilbert class polynomials, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 282–295.
[4] D. Boneh, M. Franklin, Identity-based encryption from the Weil pairing, In Advances in Cryptology Crypto 2001. LNCS, vol. 2139, pp. 213–229. Springer, Berlin (2001). Full version: SIAM J. Comput. 32(3), 586–615 (2003).
[5] D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing, In Advances in Cryptology Asiacrypt 2001, LNCS, vol. 2248, pp. 514–532. Springer, Berlin (2002). Full version: J. Cryptol. 17, 297–319 (2004).
[6] F. Brezing, A. Weng, Elliptic curves suitable for pairing based cryptography, Des. Codes Cryptogr. 37, 133–141 (2005).
[7] R. Bröker, A p-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), 2417–2435.
[8] R. Bröker, P. Stevenhagen, Eﬃcient CM-constructions of elliptic curves over ﬁnite ﬁelds, Math. Comp. 76 (2007), 2161–2179.
[9] D. Cox, Primes of the form x2 + ny2. Fermat, Class Field Theory and Complex Multiplication, John Wiley & Sons (1989).
[10] R. Dryło, A New Method for Constructing Pairing-Friendly Abelian Surfaces, In: Pairing-Based Cryptography – Pairing 2010. LNCS, vol. 6487, pp. 298-311. Springer, Heidelberg (2010).
[11] R. Dryło, Constructing Pairing-Friendly Genus 2 Curves with Split Jacobian, Lecture Notes in Computer Sciences (INDOCRYPT 2012) 7668 (2012), 437-458.
[12] R. Dryło, Z. Jelonek, Krzywe eliptyczne z zadaną grupą endomorﬁzmów i podgrupą ustalonego rzędu, Materiały z konferencji „Kryptograﬁa i Bezpieczeństwo Informacji”, Warszawa 2014.
[13] A. Enge, The complexity of class polynomial computation via ﬂoating point approximations, Math. Comp. 78 (2009), 1089–1107.
[14] K. Eisentrager, K. Lauter, A CRT algorithm for constructing genus 2 curves over ﬁnite ﬁelds, in Proceedings of AGCT 2005: Arithmetics, Geometry, and Coding Theory – Société Mathématique de France, 2011.
[15] D. Freeman, Constructing pairing-friendly elliptic curves with embedding degree 10, in Algorithmic Number Theory Symposium–ANTS-VII. Lecture Notes in Computer Science, vol. 4076 (Springer, Berlin, 2006), pp. 452–465.
[16] D. Freeman, Constructing pairing-friendly genus 2 curves with ordinary Jacobians, In Pairing-Based Cryptography – Pairing 2007, LNCS, vol. 4575, pp. 152–176. Springer, Verlag (2007).
[17] D. Freeman, A generalized Brezing-Weng algorithm for constructing pairing-friendly ordinary abelian varieties, In: Pairing-Based Cryptography – Pairing 2008, LNCS, vol. 5209, pp. 46–163, Springer, Heidelberg (2008).
[18] D. Freeman, T. Satoh, Constructing pairing-friendly hyperelliptic curves using Weil restriction, J. Number Theory 131, 959–983 (2011).
[19] D. Freeman, M. Scott, E. Teske, A taxonomy of pairing-friendly elliptic curves, J. Cryptol. 23, 224–280 (2010).
[20] D. Freeman, P. Stevenhagen, M. Streng, Abelian varieties with prescribed embedding degree, In: Algorithmic Number Theory – ANTS VIII. LNCS, vol. 5011, pp. 60–73, Springer, Heidelberg (2008).
[21] S. Galbraith, Supersingular curves in cryptography, In ASIACRYPT 2001, LNCS, 2248, pp. 495–513. Springer, Berlin (2001).
[22] S. Galbraith, F. Hess, F. Vercauteren, Hyperelliptic pairings, In Pairing-based cryptography – Pairing 2007, LNCS vol. 4575 108–131. Springer, Berlin, (2007).
[23] E. Howe, H. Zhu, On the existence of absolutely simple abelian varieties of a given dimension over an arbitrary ﬁeld, J. Number Theory 92, 139–163 (2002).
[24] J. Igusa, Arithmetic Variety of Moduli for Genus Two, Ann. Math. 72, 612–649 (1960).
[25] A. Joux, A one round protocol for tripartite Diﬃe-Hellman, In Algorithmic Number Theory Symposium – ANTS-IV. LNCS, vol. 1838, pp. 385–393, Springer, Berlin (2000), Full version: J. Cryptol. 17, 263–276 (2004).
[26] E. Kachisa, E. Schaefer, M. Scott, Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic ﬁeld, In Pairing-Based Cryptography–Pairing 2008, LNCS, vol. 5209, pp. 126–135. Springer, Heidelberg (2008).
[27] M. Kawazoe, T. Takahashi, Pairing-friendly ordinary hyperelliptic curves with ordinary Jacobians of type y2 = x5+ax, In: Pairing-Based Cryptography – Pairing 2008. LNCS, vol. 5209, pp. 164–177. Springer, Heidelberg (2008).
[28] S. Lang, Elliptic functions, Springer, 1987.
[29] A. Menezes, T. Okamoto, S. Vanstone, Reducing elliptic curve logarithms to logarithms in a ﬁnite ﬁeld, IEEE Trans. Inf. Theory 39, 1639–1646 (1993).
[30] J.F. Mestre, Construction de courbes de genre 2 à partir de leurs modules, In Eﬀective methods in algebraic geometry (Castiglioncello, 1990), pages 313–334. Birkhäuser, Boston, MA (1991).
[31] V.S. Miller, The Weil pairing, and its eﬃcient calculation, Journal of Cryptology, 17, 235–261, 2004.
[32] J.S. Milne, Abelian varieties, In G. Cornell, J. Silverman, (eds.) Arithmetic Geometry 103–150. Springer, New York (1986).
[33] J.S. Milne, Complex multiplication http://www.jmilne.org/math/CourseNotes/
[34] A. Miyaji, M. Nakabayashi, S. Takano, New explicit conditions of elliptic curve traces for FR-reduction, IEICE Trans. Fundam. E84-A(5), 1234–1243 (2001).
[35] D. Mumford, Abelian varieties, Oxford University Press 1970.
[36] F. Oort, Abelian varieties over ﬁnite ﬁelds. Higher-dimensional varieties over ﬁnite ﬁelds, Summer school in Göttingen, pp. 66, June 2007.
[37] K. Rubin, A. Silverberg, Using abelian varieties to improve pairing-based cryptography, J. Cryptol. 22, 330-364 (2009).
[38] G. Shimura, Abelian Varieties with Complex Multiplication and Modular Functions, Princeton University Press, 1998.
[39] J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 151. Springer-Verlag, New York (1994).
[40] M. Streng, Complex multiplication of abelian surfaces, PhD thesis, Universiteit Leiden (2010).
[41] M. Streng, Computing Igusa Class Polynomials Mathematics of Computation, Vol. 83, pp 275–309, (2014).
[42] A. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80, 501–538 (2011).
[43] J. Tate, Classes d’isogénie des variétés abéliennes sur un corps ﬁni, (déprés T. Honda.) Séminarie Bourbaki 1968/69, exposé 352, Lect. Notes in Math., vol. 179, pp. 95–110. Springer (1971).
[44] J. Tate, Endomorphisms of abelian varieties over ﬁnite ﬁelds, Inventiones Mathematicae 2 (1966).
[45] W.C. Waterhouse, J.S. Milne, Abelian varieties over ﬁnite ﬁelds, Proc. Symp. Pure Math. 20, 53–64 (1971).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-0b8a9d7a-4517-49e6-8622-98dc9a8bd194