ArcAdiA
http://dspace-roma3.caspur.it:80
The DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.2017-02-22T17:20:07ZTrace zero varietes in pairing-based cryptography
http://hdl.handle.net/2307/597
<Title>Trace zero varietes in pairing-based cryptography</Title>
<Authors>Cesena, Emanuele</Authors>
<Issue Date>2010-03-26</Issue Date>
<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 deﬁnition that we ﬁnd
in Wikipedia: “The practice and study of hiding information”.
In light of the results of the fundamental article of Diﬃe and Hellman New Directions in Cryptography [DH76] this simple deﬁnition 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 veriﬁable, but not falsiﬁable. To make this possible, Diﬃe
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 ﬁrst example of a public key cryptosystem was proposed in 1978 by Rivest,
Shamir and Adleman [RSA78]. Diﬃe and Hellman also advanced the idea of establishing
a cryptographic system on the discrete logarithm problem (DLP) in a ﬁnite ﬁeld, an idea
which they attributed to Prof. Gill of Stanford University, and carried out for the ﬁrst
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 ﬁnite ﬁeld. Compared to those already mentioned, elliptic curves allow greater ﬂexibility 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 deﬁned over a ﬁnite ﬁeld Fq . Let Fqr /Fq be a ﬁnite 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 eﬃcient.
Several authors addressed the study of TZV: Naumann [Nau99] and Blady [Bla02]
considered TZV of elliptic curves over extension ﬁelds of degree 3 (r = 3); Weimerskirch [Wei01] analyzed the case for extension ﬁelds of degree 5; ﬁnally Lange [Lan01,
Lan04] built TZV from the Jacobian variety of hyperelliptic curves of genus two, over extension ﬁelds of degree 3. Avanzi and Lange [AL04] compared the performance of these
three kinds of TZV over ﬁelds of odd characteristic. Avanzi and Cesena [Ces04, AC08]
compared the same three types of TZV deﬁned over binary ﬁelds, highlighting similarities and main diﬀerences between TZV deﬁned over ﬁelds 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 ﬁrst is
the choice of the coordinate system used to represent points, such as classical aﬃne
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 ﬁelds, by taking into account diﬀerent types of coordinate systems and evaluating the eﬀect 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 ﬁeld (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 eﬃcient 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
aﬃne coordinates appear to be the most eﬃcient. This is because we work in extension
ﬁelds, where the bad impact of inversions is reduced (an inversion in a extension ﬁeld
Fqr only requires a single inversion in the ground ﬁeld 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 aﬃne 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 aﬃne
coordinates, we conﬁrm the results in [AC08] that TZV of elliptic curves are always much
more eﬃcient 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 ﬁelds, called pseudo-inversion, that does not involve inversions in
the ground ﬁeld.
This new coordinate system turns out to be on average 8 − 10% faster than L´pezo
Dahab coordinates, and generally presents similar performance to aﬃne coordinates. We
2
want to remark that, since they do not require inversions in the ground ﬁeld, compressed
coordinates become more eﬀective 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 eﬃciently computable. Algebraic geometry gives us two examples of pairings that meet the above deﬁnition: 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 ﬁrst 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 ﬁnite ﬁeld.
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 ﬁrst pairing-based key-agreement and
signature schemes, and Joux [Jou00] extended the Diﬃe-Hellman key agreement protocol to a three-party, one-round protocol.
Another fundamental construction is the ﬁrst 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 certiﬁcation 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 deﬁnition of many protocols
and schemes and motivated the research for ever more eﬃcient 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 signiﬁcant 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 ﬁrst 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 eﬃcient, 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 deﬁned 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 deﬁned 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 ﬁnal 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 eﬃcient and requires no inversion in the ﬁeld.
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 deﬁned over F2307 , pairing can be up to 30% faster exploiting the parallel version of the new algorithm and ﬁnally 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 Scientiﬁc, 2008. Proceedings of
the ﬁrst 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 ﬁrst Symposium on Algebraic Geometry and its Applications (SAGA
2007) and at the GTEM Workshop on Pairings (Essen, 2009). We adapt the theory to
better ﬁt 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 deﬁne 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 clariﬁed 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 Scientiﬁc, 2008. Proceedings of the ﬁrst 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. Eﬃcient
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. Eﬃcient 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 crittograﬁche.
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 ﬁelds 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 Diﬃe–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. Eﬃcient 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. Eﬃcient 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 ﬁnite ﬁeld. 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.</Abstract>2010-03-25T23:00:00Z