REVIEW PAPER
CONSTRUCTING PAIRING-FRIENDLY GENUS 2 CURVES
1
Szkoła Główna Handlowa w Warszawie
Publication date: 2014-12-05
SBN 2014;6(2): 95-124
KEYWORDS
ABSTRACT
For applications in pairing-based cryptography we need special curves for
which the Weil and Tate pairings can be efficiently computed. Such curves, commonly
called pairing-friendly, require specific 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 first determines parameters of its Jacobian,
which are usually given by Weil numbers for genus 2 curves, and then one uses the CM
method to find 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 first 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.
REFERENCES (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).
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
