Najnowszy Numer
Archiwum
O Nas
Międzynarodowa Rada Naukowa
Rada Redakcyjna
Kontakt
Recenzenci
Standardy etyczne
Standardy etyczne czasopisma (COPE)
Polityka Open Access
Procedura zabezpieczająca oryginalność publikacji
Dla Autorów
Wymagania Edytorskie
Wytyczne Merytoryczne
Proces Recenzji
Dla Recenzentów
ARTYKUŁ PRZEGLĄDOWY
KONSTRUOWANIE KRZYWYCH GENUSU 2 Z DANYM STOPNIEM ZANURZENIOWYM
1
Szkoła Główna Handlowa w Warszawie
Data publikacji: 05-12-2014
SBN 2014;6(2): 95-124
SŁOWA KLUCZOWE
kryptografia oparta na iloczynach dwuliniowychkrzywe z danymstopniem zanurzeniowymiloczyny dwuliniowe Weila i TateCM metodaliczby Weila
STRESZCZENIE
W kryptografii 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ń endomorfizmó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 opowiednie 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.
REFERENCJE (45)
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. Broker, 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. Broker ¨ , A p-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), 2417–2435.
8.
R. Broker, P. Stevenhagen ¨ , Efficient CM-constructions of elliptic curves over finite fields, Math. Comp. 76 (2007), 2161–2179.
9.
D. Cox, Primes of the form x 2 + 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ą endomorfizmów i podgrupą ustalonego rzędu, Materiały z konferencji „Kryptografia i Bezpieczeństwo Informacji”, Warszawa 2014.
13.
A. Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089–1107.
14.
K. Eisentrager, K. Lauter, A CRT algorithm for constructing genus 2 curves over finite fields, in Proceedings of AGCT 2005: Arithmetics, Geometry, and Coding Theory – Soci´et´e Math´ematique 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 field, 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 Diffie–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 field, 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 y 2 = x 5+ax, In: Pairing-Based Cryptography – Pairing 2008. LNCS, vol. 5209, pp. 164–177. Springer, Heidelberg (2008).
29.
A. Menezes, T. Okamoto, S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inf. Theory 39, 1639–1646 (1993).
30.
J.F. Mestre, Construction de courbes de genre 2 `a partir de leurs modules, In Effective methods in algebraic geometry (Castiglioncello, 1990), pages 313–334. Birkh¨auser, Boston, MA (1991).
31.
V.S. Miller, The Weil pairing, and its efficient 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).
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).
36.
F. Oort, Abelian varieties over finite fields. Higher-dimensional varieties over finite fields, Summer school in G¨ottingen, 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´enie des vari´et´es ab´eliennes sur un corps fini, (d’apr´es T. Honda.) S´eminarie Bourbaki 1968/69, expos´e 352, Lect. Notes in Math., vol. 179, pp. 95–110. Springer (1971).
44.
J. Tate, Endomorphisms of abelian varieties over finite fields, Inventiones Mathematicae 2 (1966).
45.
W.C. Waterhouse, J.S. Milne, Abelian varieties over finite fields, Proc. Symp. Pure Math. 20, 53–64 (1971).
Udostępnij
| ISSN: | 2082-2677 |
Przetwarzamy dane osobowe zbierane podczas odwiedzania serwisu. Realizacja funkcji pozyskiwania informacji o użytkownikach i ich zachowaniu odbywa się poprzez dobrowolnie wprowadzone w formularzach informacje oraz zapisywanie w urządzeniach końcowych plików cookies (tzw. ciasteczka). Dane, w tym pliki cookies, wykorzystywane są w celu realizacji usług, zapewnienia wygodnego korzystania ze strony oraz w celu monitorowania ruchu zgodnie z Polityką prywatności. Dane są także zbierane i przetwarzane przez narzędzie Google Analytics (więcej).
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
