Trace zero varietes in pairing-based cryptography

Abstract

The term cryptography, by etymology or simply by association of ideas, suggests its connection with secret messages and this is made clear from the definition that we find in Wikipedia: “The practice and study of hiding information”. In light of the results of the fundamental article of Diffie and Hellman New Directions in Cryptography [DH76] this simple definition of cryptography seems to require a supplement: nowadays states, public organizations and private individuals can not only exchange information in secrecy, but also sign electronic documents so that the digital signature is easily verifiable, but not falsifiable. To make this possible, Diffie and Hellman introduced the concept of public-key cryptosystems : the use of public keys allows us to exchange secret keys without having to meet in person (for instance, using channels in clear on the network) or generate/verify digital signatures. The first example of a public key cryptosystem was proposed in 1978 by Rivest, Shamir and Adleman [RSA78]. Diffie and Hellman also advanced the idea of establishing a cryptographic system on the discrete logarithm problem (DLP) in a finite field, an idea which they attributed to Prof. Gill of Stanford University, and carried out for the first time in 1985 by ElGamal [ElG85]. In the same year Miller and Koblitz [Mil86, Kob87] proposed to use the group of rational points of an elliptic curve over a finite field. Compared to those already mentioned, elliptic curves allow greater flexibility in building the group and the use of smaller keys at the same level of security. Four years later Koblitz [Kob89] indicated the Jacobian variety of hyperelliptic curves as another possible candidate for the construction of cryptosystems. In 1998 Frey [Fre98, Fre01] suggested to use Trace Zero Varieties (TZV) for cryptosystems based on the DLP. The starting point of Frey’s construction is, in the simplest case, an elliptic curve E defined over a finite field Fq . Let Fqr /Fq be a finite extension. The group E (Fqr ) contains E (Fq ) and the Frobenius automorphism Fqr /Fq extends to E (Fqr ) in a natural way. The TZV is a subgroup of E (Fqr ) (more precisely, a subvariety of the Weil restriction of scalars of E (Fqr ) from Fqr to Fq ) which is globally invariant under the action of the Frobenius and isomorphic to the quotient E (Fqr )/E (Fq ). It is exactly the action of the Frobenius that makes the computation of scalar multiplication on TZV particularly efficient. Several authors addressed the study of TZV: Naumann [Nau99] and Blady [Bla02] considered TZV of elliptic curves over extension fields of degree 3 (r = 3); Weimerskirch [Wei01] analyzed the case for extension fields of degree 5; finally Lange [Lan01, Lan04] built TZV from the Jacobian variety of hyperelliptic curves of genus two, over extension fields of degree 3. Avanzi and Lange [AL04] compared the performance of these three kinds of TZV over fields of odd characteristic. Avanzi and Cesena [Ces04, AC08] compared the same three types of TZV defined over binary fields, highlighting similarities and main differences between TZV defined over fields of even and odd characteristic. 1

The performance of an elliptic curve cryptosystem depends mainly on two aspects that one needs to consider when implementing the scalar multiplication: the first is the choice of the coordinate system used to represent points, such as classical affine coordinates where a point is represented by the pair (x, y ), and the second is the use or not of precomputation. In this work we extend the results of [AC08] over binary fields, by taking into account different types of coordinate systems and evaluating the effect of using or not precomputation (the latter has already been considered in literature). For elliptic curves several coordinate systems are available. The basic idea is to avoid inversions in the field (typically expensive) and to speed up the operation of doubling a point on the curve, which is the one with the major impact on scalar multiplication, especially when using precomputation. Among the proposed coordinate systems for binary elliptic curves, we mention projective coordinates in which a point is represented by the tuple (X, Y, Z ) that corresponds to (x, y ) = (X/Z, Y /Z ) and L´pez-Dahab coordinates o where (X, Y, Z ) corresponds to (x, y ) = (X/Z, Y /Z 2 ). The main result of our analysis is that TZV of elliptic curves over extensions of degree 5 are the most efficient groups suitable to build cryptographic systems based on the DLP. On our Intel platform (32-bit), at 80-bit security they are about 10% faster (20% using precomputation) and at 96-bit security they are about 22% faster (30% using precomputation) than elliptic curves with L´pez-Dahab coordinates (to be o precise, we considered the fastest extended L´pez-Dahab coordinates). For TZV, the o affine coordinates appear to be the most efficient. This is because we work in extension fields, where the bad impact of inversions is reduced (an inversion in a extension field Fqr only requires a single inversion in the ground field Fq ). Nowadays it is easy to be blinded by the incredible amount of memory and computational power which is available in laptops and personal computers. However, it is important to stress that there are countless applications – where cryptography is important and often overlooked – that are or need to be deployed on devices with limited resources, like mobile phones or wireless sensors. In such cases using affine coordinates and avoiding precomputation can be the only way to cope with the constrains imposed by the scenario and TZV turn out to be an excellent solution to improve performance. Indeed, if we limit ourselves to consider affine coordinates, we confirm the results in [AC08] that TZV of elliptic curves are always much more efficient than elliptic curves themselves (by factors about 1.5 for extension of degree 3 and more than 2 for degree 5). To further assess the validity of our results, we perform experiments also on a PowerPC machine, still a relatively powerful server, but the idea is to have a comparison also with an architecture more similar to what can be found in many embedded devices. Here the advantage of TZV is even more accentuated. Finally, following an idea of [HKA06], we develop for TZV a new coordinate system, the compressed L´pez-Dahab coordinates, in which a Fqr -rational point is represented o by the tuple (X, Y, z ) ∈ Fqr × Fqr × Fq that corresponds to (x, y ) = (X/z, Y /z 2 ). The difference with L´pez-Dahab coordinates is therefore that the coordinate z is in Fq , thus o smaller. Arithmetic in this representation is made possible by a particular operation available in extension fields, called pseudo-inversion, that does not involve inversions in the ground field. This new coordinate system turns out to be on average 8 − 10% faster than L´pezo Dahab coordinates, and generally presents similar performance to affine coordinates. We 2

want to remark that, since they do not require inversions in the ground field, compressed coordinates become more effective the worse the inversion is, thus they are attractive for devices with constrained resources. Returning to the history of public-key cryptography, a big step forward has been made with the introduction of pairing-based cryptography. A pairing, from the mathematical point of view, is a non-degenerate, bilinear map and to use it in practical applications, we additionally require that it is efficiently computable. Algebraic geometry gives us two examples of pairings that meet the above definition: the Weil pairing and the Lichtenbaum-Tate pairing, that we shall simply call Tate pairing. The latter is particularly interesting for cryptography because it has better qualities from a computational point of view, at least for moderate security levels. The first use of pairings in cryptography dates back to the 1990’s, when they are exploited by Menezes, Okamoto and Vanstone [MOV93] and by Frey and R¨ck [FR94] to u attack cryptosystems by reducing the DLP in the group of rational points of an elliptic curve to the DLP in a finite field. We have to wait until 2000 to see authors rediscover pairings and use it “for good”, starting to develop cryptographic protocols and schemes based on pairings: Sakai, Ohgishi and Kasahara [SOK00] introduced the first pairing-based key-agreement and signature schemes, and Joux [Jou00] extended the Diffie-Hellman key agreement protocol to a three-party, one-round protocol. Another fundamental construction is the first Identiy-Based Encryption (IBE) scheme realized in 2001 by Boneh and Franklin [BF01]. In IBE, the user’s public key is derived from some known aspects of her identity, such as her name or e-mail address and this eliminates the key distribution or certification problems. The construction of a workable and provably secure scheme was an open problem posed by Shamir in 1984 [Sha85]. These key contributions have been the trigger for an actual explosion of interest in pairing-based cryptography, which led in recent years the definition of many protocols and schemes and motivated the research for ever more efficient implementations. Pairings met TZV in 2002, when Rubin and Silverberg [RS02] proposed to use supersingular abelian varieties of dimension greater than one to improve the security of pairing-based cryptosystems. Besides Jacobian varieties of hyperelliptic curves, the other significant example was the class of TZV (called primitive subgroups in that paper), which can be constructed from elliptic curves. The original work of Rubin and Silverberg and their more recent results presented in [RS09] constitute the motivation of our research. Notably, supersingular TZV of elliptic curves allow to achieve higher “security per bit” than supersingular elliptic curves themselves: in characteristic 3 (r = 5) TZV represent the first example of supersingular abelian varieties with security parameter greater than 6 (in fact 7.5); in characteristic 2 (r = 3) TZV present an alternative to supersingular elliptic curves over F3m which is more efficient, simpler to implement and with equivalent security properties. The computation of pairings over TZV has already been taken into account by Barreto et al. [BK+ 02, BG+ 07], who defined the η and ηT pairings on supersingular abelian varieties. Other pairings, such as the (twisted) Ate pairing [HSV06] and its extended versions [MK+ 07, LLP09, Ver08] can be naturally defined on TZV too. However no work in literature considered using the q th power Frobenius available in TZV to speed-up the computation of pairings. The focus of the present work is exactly that: develop a new algorithm to compute 3

the Tate pairing on TZV exploiting the action of the q th power Frobenius. Our result applies to supersingular TZV in characteristic 2, 3 and p > 3. ˆ In our main theorem we derive a new formula for the Tate pairing t(P, Q): M a q a−1 r

r−1 q i(r+1)

fq,P (Qσi )

ˆ t(P, Q) =

,

i=0

where fq,P is the Miller function, σi is proper power of the q th power Frobenius endomorphism, and a and M are constants depending on the curve. The previous formula yields a new algorithm to compute the Tate pairing over supersingular TZV. We evaluate fq,P at the r points Qσi (raising each evaluation to the proper power q i(r+1) ). At the end we compute the final exponentiation to M a q a−1 . r The algorithm is suitable for a parallel implementation, requiring r processors and achieving a Miller loop of “length” q . Moreover, both in a parallel and in a sequential model, an implementation with precomputation of the multiples of P requires the storage of only log2 q points. Together with implementation details, we also propose a variant of the point compression algorithm of Rubin and Silverberg [RS02] in characteristic 2 which is more efficient and requires no inversion in the field. Experimental results show that the parallel version of our new algorithm is on average 25 − 30% faster than any previous pairing algorithm – notably the ηT pairing described in [BG+ 07]. Besides the computation of pairings, we also analyze the performance of scalar multiplication on supersingular elliptic curves and TZV. Supersingular TZV are much faster than the corresponding elliptic curves and, as we already mentioned, they also allow to achieve higher security per bit. For instance, on our Intel platform (32-bit), scalar multiplication on the supersingular TZV over F2103 (r = 3) is 4 times faster than on the corresponding elliptic curve defined over F2307 , pairing can be up to 30% faster exploiting the parallel version of the new algorithm and finally points can be compressed to 208 bits, allowing a reduction of storage or bandwidth by a factor about 3/2. In conclusion we have seen that TZV, ordinary and supersingular, have many interesting features that make them attractive for building cryptosystems based on the DLP as well as pairing-based cryptosystems. They are also well suited for implementations on devices with constrained resources at moderate security levels.

Foundation The following publications and pre-prints form the foundation of this thesis: • R. M. Avanzi and E. Cesena. Pairing on Supersingular Trace Zero Varieties. Cryptology ePrint Archive, Report 2008/404, 2008. http://eprint.iacr.org/2008/404 A preliminary version of this work was presented at Eurocrypt 2009 poster session. • R. M. Avanzi and E. Cesena. Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications. In J. Hirschfeld, J. Chaumine, and R. Rolland, editors, Algebraic geometry and its applications, volume 5 of Number Theory and Its Applications, pp. 188–215. World Scientific, 2008. Proceedings of the first SAGA conference, Papeete, 7-11 May 2007. 4

• E. Cesena, H. L¨hr, G. Ramunno, A.-R. Sadeghi, and D. Vernizzi. Anonymous o Authentication with TLS and DAA. Submitted to TRUST 2010. • E. Cesena, G. Ramunno, and D. Vernizzi. Towards Trusted Broadcast Encryption. TrustCom 2008: The 2008 International Symposium on Trusted Computing. Zhang Jia Jie (Hunan, China), 18-20 November 2008, pp. 2125–2130.

Organization The dissertation is organized as follows. Chapter 1 introduces pairing-based cryptography with a few relevant cryptographic schemes taken from the literature; this serves as a practical motivation and we will return to the schemes during the course of the dissertation. In Chapter 2 we arrange the mathematical background with particular focus on the Lichtenbaum-Tate pairing. Most of this chapter is taken from two presentations of Prof. Frey at the first Symposium on Algebraic Geometry and its Applications (SAGA 2007) and at the GTEM Workshop on Pairings (Essen, 2009). We adapt the theory to better fit the case of TZV. Chapter 3 is the core of this dissertation. We take a more computationally oriented approach: we discuss the arithmetic in the ideal class group of a TZV, we review techniques for pairing computation taken from the literature and we develop a new algorithm for the computation of the Tate pairing over supersingular TZV which exploits the action of the q th power Frobenius endomorphism. In the end of the chapter we discuss the security of TZV and we provide explicit examples of curves that are used in the experiments. In Chapter 4 we deal with the implementation details and we provide experimental results. For emotional reasons most of this chapter is devoted to the implementation in characteristic two. Notably, in this chapter we define new compressed L´pez-Dahab o coordinates for ordinary TZV of elliptic curves, we analyze the performance of scalar multiplication both on ordinary and supersingular TZV, we detail the parallel and the sequential versions of the new algorithm for the Tate pairing, including experimental results. Finally, Chapter 5 is devoted to real-world applications and notably to the Trusted Computing technology: due to my personal and somehow atypical research experience at Politecnico di Torino, I have gotten to know a more applied way to do research and I wish to include in the dissertation some results obtained in this area. Pairing here is used as a black-box toolkit and actually these topics originated my interest in pairing computation. Unfortunately, due to technical details that will be clarified at proper time, the algorithm for pairing computation developed in this dissertation is probably not the best candidate for such applications, but the hope is to continue my research and let these two routes converge.

References [AC08]

R. M. Avanzi and E. Cesena. Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications. In J. Hirschfeld, J. Chaumine, and R. Rolland, editors, Algebraic geometry and its applications, volume 5 of Number

5

Theory and Its Applications, pages 188–215. World Scientific, 2008. Proceedings of the first SAGA conference, 2007, Papeete. [AL04]

R. M. Avanzi and T. Lange. Cryptographic Applications of Trace Zero Varieties. Unpublished manuscript., 2004.

[BF01]

D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. LNCS, 2139:213–??, 2001.

´ [BG+ 07] P. S. Barreto, S. D. Galbraith, C. O’ H´igeartaigh, and M. Scott. Efficient e pairing computation on supersingular Abelian varieties. Des. Codes Cryptography, 42(3):239–271, 2007. [BK+ 02] P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott. Efficient algorithms for pairing-based cryptosystems. In Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of LNCS, pages 354–368. Springer, 2002. [Bla02]

G. Blady. Die Weil-Restriktion elliptischer Kurven in der Kryptographie. Master’s thesis, Universit¨t-Gesamthochschule Essen, 2002. a

[Ces04]

E. Cesena. Variet` a traccia zero su campi binari – applicazioni crittografiche. a Master’s thesis, Universit` degli Studi di Milano, 2004. a

[DH76]

W. Diffe and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.

[ElG85]

T. ElGamal. A public key cryptosystem and signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, pages 473–481, 1985.

[FR94]

G. Frey and H.-G. R¨ck. A remark concerning m-divisibility and the discrete u logarithm in the divisor class group of curves. Mathematics of Computation, 62(206):865–874, 1994.

[Fre98]

G. Frey. How to disguise an elliptic curve. Talk at Waterloo workshop on the ECDLP, 1998. http://www.cacr.math.uwaterloo.ca/conferences/1998/ ecc98/slides.html.

[Fre01]

G. Frey. Applications of arithmetical geometry to cryptographic constructions. In Finite fields and applications (Augsburg, 1999), pages 128–161. Springer, Berlin, 2001.

[HKA06] F. Hoshino, T. Kobayashi, and K. Aoki. Compressed jacobian coordinates for OEF. In Progress in Cryptology - VIETCRYPT 2006, volume 4341 of LNCS, pages 147–156. Springer, 2006. [HSV06] F. Hess, N. P. Smart, and F. Vercauteren. The Eta Pairing Revisited. IEEE Trans. Inform. Theory, 52:4595–4602, 2006. [Jou00]

A. Joux. A one round protocol for tripartite Diffie–Hellman. In Algorithmic Number Theory, ANTS-IV, volume 1838 of LNCS, pages 385–394. Springer, 2000. 6

[Kob87]

N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177):203–209, 1987.

[Kob89]

N. Koblitz. Hyperelliptic cryptosystems. Journal of Cryptology, 1:139–150, 1989.

[Lan01]

T. Lange. Efficient arithmetic on hyperelliptic curves. PhD thesis, University Essen, 2001.

[Lan04]

T. Lange. Trace zero subvarieties of genus 2 curves for cryptosystems. J. Ramanujan. Math. Soc., 19:15–33, 2004.

[LLP09] E. Lee, H.-S. Lee, and C.-M. Park. Efficient and generalized pairing computation on abelian varieties. IEEE Transactions on Information Theory, 55(4):1793–1803, 2009. [Mil86]

V. S. Miller. Use of elliptic curves in cryptography. In Advances in cryptology – crypto ’85, volume 218 of LNCS, pages 417–426. Springer, Berlin, 1986.

[MK+ 07] S. Matsuda, N. Kanayama, F. Hess, and E. Okamoto. Optimised versions of the Ate and Twisted Ate Pairings. In The 11th IMA International Conference on Cryptography and Coding, volume 4887 of LNCS, pages 302–312. Springer, 2007. [MOV93] A. J. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to a finite field. IEEE Trans. on Inform. Theory, 39:1639–1646, 1993. [Nau99]

N. Naumann. Weil-Restriktion abelscher Variet¨ten. Master’s thesis, Univera sity Essen, 1999.

[RS02]

K. Rubin and A. Silverberg. Supersingular abelian varieties in cryptology. In CRYPTO ’02: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, pages 336–353, London, UK, 2002. Springer.

[RS09]

K. Rubin and A. Silverberg. Using abelian varieties to improve pairing-based cryptography. Journal of Cryptology, 22(3):330–364, 2009.

[RSA78] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signature and public key cryptosystems. Comm. ACM, 21:120–126, 1978. [Sha85]

A. Shamir. Identity-based cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47–53. Springer, 1985.

[SOK00] R. Sakai, K. Ohgishi, and M. Kasahara. Cryptosystems based on pairing. In The 2000 Symposium on Cryptography and Information Security (SCIS2000), pages 26–28, Okinawa, Japan, 2000. [Ver08]

F. Vercauteren. Optimal Pairings. Cryptology ePrint Archive, Report 2008/096, 2008. http://eprint.iacr.org/2008/096.

[Wei01]

A. Weimerskirch. The application of the Mordell–Weil group to cryptographic systems. Master’s thesis, Worchester Polytechnic Institute, 2001.