×

Constructing pairing-friendly hyperelliptic curves using Weil restriction. (English) Zbl 1245.11075

A pairing-friendly curve is a curve over a finite field \(\mathbb{F}_q\) whose Jacobian has small embedding degree \(k = [\mathbb{F}_{q}(\zeta_r) ~|~ \mathbb{F}_{q}]\) with respect to a large subgroup of prime order \(r\). Such curves, particularly elliptic curves and, to a lesser extent, genus \(2\) hyperelliptic curves, have a variety of applications in public-key cryptosystems. Supersingular curves are pairing-friendly, but the possible embedding degrees are limited to at most \(12\) for genus \(\leq 2.\) Thus, methods for constructing ordinary curves with small embedding degree have been of particular interest. The goal is to find such curves for which the finite field size is small compared to the \(r,\) measured by the \(\rho\)-value.
In this paper, the authors describe a new method for constructing pairing-friendly genus \(2\) hyperelliptic curves over finite fields \(\mathbb{F}_q\) whose Jacobians are ordinary and simple. The main idea is to use existing methods to construct an elliptic curve over \(\mathbb{F}_q\) that becomes pairing friendly over \(\mathbb{F}_q^d,\) and to use the Weil restriction of scalars to find a pairing friendly genus 2 curve over \(\mathbb{F}_q.\) This construction yields curves defined over smaller fields relative to the subgroup size than previous constructions, and hence smaller \(\rho\) values. Using constructions due to Cocks and Pinch [Identity-based cryptosystems based on the Weil pairing (unpublished manuscript) (2001)] and F. Brezing and A. Weng [“Elliptic curves suitable for pairing based cryptography”, Des. Codes Cryptography 37, No. 1, 133–141 (2005; Zbl 1100.14517)] yields curves with generically smaller \(\rho\) values than those obtained from other constructions (\(4\) as opposed to \(8\)), as well as a record value of about \(2.2\) (compared with \(4\)).

MSC:

11G20 Curves over finite and local fields
14G15 Finite ground fields in algebraic geometry
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography

Citations:

Zbl 1100.14517

Software:

Magma; ECPP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atkin, A.; Morain, F., Elliptic curves and primality proving, Math. Comp., 61, 29-68 (1993) · Zbl 0792.11056
[2] Bateman, P.; Horn, R., A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp., 16, 363-367 (1962) · Zbl 0105.03302
[3] Benger, N.; Charlemagne, M.; Freeman, D., On the security of pairing-friendly abelian varieties over non-prime fields, (Pairing-Based Cryptography — Pairing 2009. Pairing-Based Cryptography — Pairing 2009, Lecture Notes in Comput. Sci., vol. 5671 (2009), Springer), 52-65 · Zbl 1250.14016
[4] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039
[5] Brezing, F.; Weng, A., Elliptic curves suitable for pairing based cryptography, Des. Codes Cryptogr., 37, 133-141 (2005) · Zbl 1100.14517
[6] Bröker, R., Constructing elliptic curves of prescribed order, PhD dissertation, Universiteit Leiden, 2006, available at
[7] Cassels, J. W.S.; Flynn, E. V., Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2, London Math. Soc. Lecture Note Ser., vol. 230 (1996), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0857.14018
[8] C. Cocks, R. Pinch, Identity-based cryptosystems based on the Weil pairing, unpublished manuscript, 2001, while this manuscript is generally unavailable, the main result appears as Theorem 4.1 of [13]; C. Cocks, R. Pinch, Identity-based cryptosystems based on the Weil pairing, unpublished manuscript, 2001, while this manuscript is generally unavailable, the main result appears as Theorem 4.1 of [13]
[9] Diem, C., A study on theoretical and practical aspects of Weil-restrictions of varieties, PhD dissertation, Universität-Gesamthochschule Essen, 2001, available at · Zbl 0985.14011
[10] Duursma, I.; Kiyavash, N., The vector decomposition problem for elliptic and hyperelliptic curves, J. Ramanujan Math. Soc., 20, 59-76 (2005) · Zbl 1110.14021
[11] Freeman, D., A generalized Brezing-Weng algorithm for constructing pairing-friendly ordinary abelian varieties, (Pairing-Based Cryptography — Pairing 2008. Pairing-Based Cryptography — Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209 (2008), Springer), 146-163 · Zbl 1186.94440
[12] Freeman, D. M.; Satoh, T., Supplement to ‘Constructing pairing-friendly hyperelliptic curves using Weil restriction’, 2010, available at · Zbl 1245.11075
[13] Freeman, D.; Scott, M.; Teske, E., A taxonomy of pairing-friendly elliptic curves, J. Cryptology, 23, 224-280 (2010) · Zbl 1181.94094
[14] Freeman, D.; Stevenhagen, P.; Streng, M., Abelian varieties with prescribed embedding degree, (Algorithmic Number Theory — ANTS-VIII. Algorithmic Number Theory — ANTS-VIII, Lecture Notes in Comput. Sci., vol. 5011 (2008), Springer), 60-73 · Zbl 1209.11056
[15] Frey, G.; Kani, E.; Völklein, H., Curves with infinite \(K\)-rational geometric fundamental group, (Aspects of Galois Theory. Aspects of Galois Theory, London Math. Soc. Lecture Note Ser., vol. 256 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 85-118 · Zbl 0978.14021
[16] Furukawa, E.; Kawazoe, M.; Takahashi, T., Counting points for hyperelliptic curves of type \(y^2 = x^5 + a x\) over finite prime fields, (Selected Areas in Cryptography — SAC 2003. Selected Areas in Cryptography — SAC 2003, Lecture Notes in Comput. Sci., vol. 3006 (2004), Springer), 26-41 · Zbl 1081.94023
[17] Galbraith, S. D.; Harrison, M.; Morales, D. J.M., Efficient hyperelliptic arithmetic using balanced representation for divisors, (Algorithmic Number Theory Symposium — ANTS-VIII. Algorithmic Number Theory Symposium — ANTS-VIII, Lecture Notes in Comput. Sci., vol. 5011 (2008), Springer), 342-356 · Zbl 1232.14017
[18] Galbraith, S. D.; Lin, X.; Morales, D. J.M., Pairings on hyperelliptic curves with a real model, (Pairing-Based Cryptography — Pairing 2008. Pairing-Based Cryptography — Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209 (2008), Springer), 265-281 · Zbl 1186.11074
[19] Galbraith, S.; Lin, X.; Scott, M., Endomorphisms for faster elliptic curve cryptography on a large class of curves, (Advances in Cryptology — EUROCRYPT 2009. Advances in Cryptology — EUROCRYPT 2009, Lecture Notes in Comput. Sci., vol. 5479 (2009), Springer), 518-535 · Zbl 1239.94048
[20] Gaudry, P.; Schost, É., On the invariants of the quotients of the Jacobian of a curve of genus 2, (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes — AAECC-14. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes — AAECC-14, Lecture Notes in Comput. Sci., vol. 2227 (2001), Springer), 373-386 · Zbl 1063.14039
[21] Gaudry, P.; Schost, É., Construction of secure random curves of genus 2 over prime fields, (Advances in Cryptology — EUROCRYPT 2004. Advances in Cryptology — EUROCRYPT 2004, Lecture Notes in Comput. Sci., vol. 3027 (2004), Springer), 239-256 · Zbl 1122.11315
[22] Hitt, L., On the minimal embedding field, (Pairing-Based Cryptography — Pairing 2007. Pairing-Based Cryptography — Pairing 2007, Lecture Notes in Comput. Sci., vol. 4575 (2007), Springer), 294-301 · Zbl 1151.94518
[23] Kawazoe, M.; Takahashi, T., Pairing-friendly hyperelliptic curves with ordinary Jacobians of type \(y^2 = x^5 + a x\), (Pairing-Based Cryptography — Pairing 2008. Pairing-Based Cryptography — Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209 (2008), Springer), 164-177 · Zbl 1186.94454
[24] Lang, S., Elliptic Functions, Grad. Texts in Math., vol. 112 (1987), Springer-Verlag: Springer-Verlag New York
[25] Maisner, D.; Nart, E., Abelian surfaces over finite fields as Jacobians, Experiment. Math., 11, 321-337 (2002), with an appendix by Everett W. Howe · Zbl 1101.14056
[26] Mazur, B.; Rubin, K.; Silverberg, A., Twisting commutative algebraic groups, J. Algebra, 314, 419-438 (2007) · Zbl 1128.14034
[27] Paterson, K., Cryptography from pairings, (Blake, I. F.; Seroussi, G.; Smart, N. P., Advances in Elliptic Curve Cryptography (2005), Cambridge Univ. Press), 215-251
[28] Rubin, K.; Silverberg, A., Using primitive subgroups to do more with fewer bits, (Algorithmic Number Theory — ANTS VI. Algorithmic Number Theory — ANTS VI, Lecture Notes in Comput. Sci., vol. 3076 (2004), Springer), 18-41 · Zbl 1125.94328
[29] Rubin, K.; Silverberg, A., Using abelian varieties to improve pairing-based cryptography, J. Cryptology, 22, 330-364 (2009) · Zbl 1170.94013
[30] Rubin, K.; Silverberg, A., Choosing the correct elliptic curve in the CM method, Math. Comp., 79, 545-561 (2010) · Zbl 1213.11127
[31] Satoh, T., Generating genus two hyperelliptic curves over large characteristic finite fields, (Advances in Cryptology — EUROCRYPT 2009. Advances in Cryptology — EUROCRYPT 2009, Lecture Notes in Comput. Sci., vol. 5479 (2009), Springer), 536-553 · Zbl 1239.94065
[32] Silverman, J., Advanced Topics in the Arithmetic of Elliptic Curves, Grad. Texts in Math., vol. 151 (1994), Springer-Verlag: Springer-Verlag New York · Zbl 0911.14015
[33] Sutherland, A., Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. (2009), in press, available at
[34] Tate, J., Endomorphisms of abelian varieties over finite fields, Invent. Math., 2, 134-144 (1966) · Zbl 0147.20303
[35] Tate, J., Classes d’isogénie des variétés abéliennes sur un corps fini (d’après T. Honda), (Séminaire Bourbaki 1968/69. Séminaire Bourbaki 1968/69, Lecture Notes in Math., vol. 179 (1971), Springer), 95-110
[36] van Wamelen, P., Examples of genus two CM curves defined over the rationals, Math. Comp., 68, 307-320 (1999) · Zbl 0906.14025
[37] Waterhouse, W. C., Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4), 2, 521-560 (1969) · Zbl 0188.53001
[38] Weil, A., Adèles and Algebraic Groups, Progr. Math., vol. 23 (1982), Birkhäuser: Birkhäuser Boston, with appendices by M. Demazure and Takashi Ono · Zbl 0493.14028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.