Trace zero varieties in cryptography: optimal representation and index calculus

Vortrag von Dr. Maike Massierer

Datum: 02.12.13  Zeit: 11.00 - 12.00  Raum: Y27H35/36

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. This group has been proposed for use in cryptographic systems based on the discrete logarithm problem by Frey and for use in pairing-based cryptographic systems by Rubin and Silverberg.

For the efficient use of memory and bandwidth, one desires an optimal-size representation of the F_q-rational points of trace zero varieties, i.e. a representation whose size matches the size of the group. We propose two such representations, together with efficient compression and decompression algorithms (to compute the representation and to recover a point from its representation, respectively) for each method. Both representations 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 varieties. For this purpose, we propose an index calculus algorithm to compute discrete logarithms in these varieties, following the approach of Gaudry for index calculus in abelian varieties of small dimension.