×

zbMATH — the first resource for mathematics

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
Software:
Magma; ECPP
PDF BibTeX XML Cite
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, (), 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 · 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].
[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, (), 146-163 · Zbl 1186.94440
[12] Freeman, D.M.; Satoh, T., Supplement to ‘constructing pairing-friendly hyperelliptic curves using Weil restriction’, 2010, available at
[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, (), 60-73 · Zbl 1209.11056
[15] Frey, G.; Kani, E.; Völklein, H., Curves with infinite K-rational geometric fundamental group, (), 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, (), 26-41 · Zbl 1081.94023
[17] Galbraith, S.D.; Harrison, M.; Morales, D.J.M., Efficient hyperelliptic arithmetic using balanced representation for divisors, (), 342-356 · Zbl 1232.14017
[18] Galbraith, S.D.; Lin, X.; Morales, D.J.M., Pairings on hyperelliptic curves with a real model, (), 265-281 · Zbl 1186.11074
[19] Galbraith, S.; Lin, X.; Scott, M., Endomorphisms for faster elliptic curve cryptography on a large class of curves, (), 518-535 · Zbl 1239.94048
[20] Gaudry, P.; Schost, É., On the invariants of the quotients of the Jacobian of a curve of genus 2, (), 373-386 · Zbl 1063.14039
[21] Gaudry, P.; Schost, É., Construction of secure random curves of genus 2 over prime fields, (), 239-256 · Zbl 1122.11315
[22] Hitt, L., On the minimal embedding field, (), 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\), (), 164-177 · Zbl 1186.94454
[24] Lang, S., Elliptic functions, Grad. texts in math., vol. 112, (1987), 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, (), 215-251
[28] Rubin, K.; Silverberg, A., Using primitive subgroups to do more with fewer bits, (), 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, (), 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 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), (), 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 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.