International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Maike Massierer (#1021)
Name Maike Massierer
Personal Homepage
Institution Universit├Ąt Basel
Topic of his/her doctorate. Trace zero varieties in cryptography: Optimal representation and index calculus
Category public-key cryptography
Keywords discrete logarithm problem, elliptic curve cryptography, foundations, number theory
Ph.D. Supervisor(s) Elisa Gorla
Year of completion 2014
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.
E-Mail Address maike.massierer (at)
Last Change 2014-06-21 12:25:00
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR