HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Trace Zero Varieties in Cryptography: Optimal Representation and Index Calculus

Abstract : The trace zero variety associated to an elliptic or hyperelliptic curve is an abelian variety defined over a finite field F_q. Its F_q-rational points yield a finite group, the trace zero subgroup of the degree zero Picard group of the original curve, consisting of all points of trace zero with respect to some field extension F_{q^n}/F_q of prime degree n. This group has been proposed for use in cryptographic systems based on the discrete logarithm problem by Frey, since the group arithmetic is particularly fast, and for use in pairing-based cryptosystems by Rubin and Silverberg, since it produces particularly secure pairings. In this thesis, we study two aspects of using trace zero subgroups in cryptography: optimal-size representation of the elements and the hardness of the discrete logarithm problem. For the efficient use of memory and bandwidth, one desires an optimal-size representation of the elements of trace zero subgroups, i.e. a representation whose size matches the size of the group. We propose two such representations. The first one builds on an equation for the trace zero subgroup of an elliptic curve that we derive from Semaev's summation polynomials. It can be made practical for small values of n. The second one is via the coefficients of a rational function, and it works for trace zero subgroups of elliptic and hyperelliptic curves of any genus, with respect to a base field extension of any prime degree. For each representation, we present efficient compression and decompression algorithms (to compute the representation, and to recover a full point from its representation), and complement them with implementation results. We discuss in detail the practically relevant cases of small genus and extension degree, and we compare with the other known compression methods of Naumann, Lange, and Silverberg. Both representations that we propose are compatible with scalar multiplication of points, and they are the first representations with this property. We also investigate the hardness of the discrete logarithm problem in trace zero subgroups. For this purpose, we propose an index calculus algorithm to compute discrete logarithms in these groups, following the approach of Gaudry for index calculus in abelian varieties of small dimension. We make the algorithm explicit for small values of n and study its complexity as well as its practical performance with the help of our own Magma implementation. Finally, we compare this approach with other possible attacks on the discrete logarithm problem in trace zero subgroups and draw some general conclusions on the suitability of these groups for cryptographic systems.
Document type :
Complete list of metadata

Cited literature [146 references]  Display  Hide  Download

Contributor : Maike Massierer Connect in order to contact the contributor
Submitted on : Friday, December 19, 2014 - 3:53:13 PM
Last modification on : Wednesday, January 10, 2018 - 2:18:09 PM
Long-term archiving on: : Monday, March 23, 2015 - 6:27:49 PM


  • HAL Id : tel-01097418, version 1



Maike Massierer. Trace Zero Varieties in Cryptography: Optimal Representation and Index Calculus. Mathematics [math]. Université de Bâle, 2013. English. ⟨NNT : urn: urn:nbn:ch:bel-bau-diss107829⟩. ⟨tel-01097418⟩



Record views


Files downloads