E. [. Avanzi and . Cesena, Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications, Algebraic Geometry and Its Applications, pp.188-215, 2007.
DOI : 10.1142/9789812793430_0010

H. R. Avanzi, C. Cohen, G. Doche, T. Frey, K. Lange et al., Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications, 2006.

J. W. Bos, C. Costello, H. Hisil, and K. Lauter, High-Performance Scalar Multiplication Using 8-Dimensional GLV/GLS Decomposition, Cryptographic Hardware and Embedded Systems ? CHES 2013, pp.331-338, 2013.
DOI : 10.1007/978-3-642-40349-1_19

W. Bosma, J. Cannon, and C. Playoust, The Magma Algebra System I: The User Language, Journal of Symbolic Computation, vol.24, issue.3-4, pp.235-265, 1997.
DOI : 10.1006/jsco.1996.0125

. J. Bdl-+-12-]-d, N. Bernstein, T. Duif, P. Lange, B. Schwabe et al., High-speed high-security signatures, J. Cryptogr. Eng, vol.2, issue.2, pp.77-89, 2012.

]. G. Bla02 and . Blady, Die Weil-Restriktion elliptischer Kurven in der Kryptographie, Master's thesis Voloch, Efficient computation of roots in finite fields, Des. Codes Crytogr, vol.39, issue.2, pp.275-280, 2002.

]. D. Can87 and . Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp, vol.48, issue.177, pp.95-101, 1987.

]. E. Ces08 and . Cesena, Pairing with supersingular trace zero varieties revisited [Ces10] , Trace zero varieties in pairing-based cryptography The GHS attack in odd characteristic, Die03] C. Diem, pp.18-19, 2003.

J. [. Diem and . Scholten, An attack on a trace-zero cryptosystem

A. Enge, P. Gaudry, and E. Thomé, An L(1/3) Discrete Logarithm Algorithm for Low Degree Curves, Journal of Cryptology, vol.68, issue.226, pp.24-41, 2011.
DOI : 10.1007/s00145-010-9057-y
URL : https://hal.archives-ouvertes.fr/inria-00135324

A. Faz-hernández, P. Longa, and A. H. Sánchez, Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves, Topics in cryptology CT-RSA 2014, LNCS, vol.8366, pp.1-27, 2014.

]. G. Fre99 and . Frey, Applications of arithmetical geometry to cryptographic constructions, Proceedings of the 5th International Conference on Finite Fields and Applications, pp.128-161, 1999.

]. P. Gau07 and . Gaudry, Fast genus 2 arithmetic based on Theta functions [Gau09] , Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, Gong and L. Harn, Public-key cryptosystems based on cubic finite field extensions, pp.243-265, 1999.

P. Gaudry, F. Hess, and N. P. Smart, Constructive and destructive facets of Weil descent on elliptic curves, Journal of Cryptology, vol.44, issue.1, pp.19-46, 2002.
DOI : 10.1007/s00145-001-0011-x
URL : https://hal.archives-ouvertes.fr/inria-00512763

X. [. Galbraith and . Lin, Computing pairings using x-coordinates only, Des. Codes Crytogr, pp.305-324, 2009.

X. [. Galbraith, M. Lin, and . Scott, Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves, J. Cryptology, vol.47, issue.3, pp.446-469, 2011.
DOI : 10.1007/3-540-48892-8_15

R. P. Gallant, R. J. Lambert, and S. A. Vanstone, Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms, Advances in Cryptology: Proceedings of CRYPTO '01, pp.190-200, 2001.
DOI : 10.1007/3-540-44647-8_11

M. [. Gorla and . Massierer, Point compression for the trace zero subgroup over a small degree extension field, Des. Codes Crytogr, pp.335-357, 2015.

J. Gerhard, J. Von-zur-gathenhss01, ]. F. Hess, G. Seroussi, and N. P. Smart, Modern computer algebra Two topics in hyperelliptic cryptography, Proceedings of SAC '01, pp.181-189, 1999.

]. N. Kob91 and . Koblitz, CM-curves with good cryptographic properties Advances in Cryptology: Proceedings of CRYPTO '91, LNCS, vol.576, pp.179-287, 1991.

]. T. Lan01 and . Lange, Trace zero subvarieties of genus 2 curves for cryptosystem, [Lan05] , Formulae for arithmetic on genus 2 hyperelliptic curvesLS12] P. Longa and F. Sica, Four-dimensional Gallant?Lambert?Vanstone scalar multiplication, Advances in Cryptology: Proceedings of ASIACRYPT '12, pp.15-33, 2001.

E. [. Lenstra and . Verheul, The XTR public key system Advances in Cryptology, Proceedings of CRYPTO '00 (M. Bellare, pp.1-19, 2000.

]. V. Mil04 and . Miller, The Weil pairing, and its efficient calculation, Mon87] P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, pp.235-261, 1987.

A. [. Rubin and . Silverberg, Supersingular abelian varieties in cryptology Advances in Cryptology: Proceedings of CRYPTO '02, LNCS, vol.2442, pp.336-353, 2002.

]. A. Sil05, . Silverberg-[-ss95-]-p, C. Smith, and . Skinner, Compression for trace zero subgroups of elliptic curves, Trends Math A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, Advances in Cryptology: Proceedings of ASIACRYPT '94 (J. Pieprzyk and R. Safavi-Naini, pp.93-100, 1995.

]. L. Was08 and . Washington, Elliptic Curves: Number Theory and Cryptography, second ed., Discrete Mathematics and its Applications, Wei01] A. Weimerskirch, corresponding v-polynomials. It follows that the overall complexity of decompression is O(log q) operations in F q, 2008.

E. Gorla, Institut de mathématiques, Rue Emile-Argand, vol.11, 2000.

M. Massierer and M. Institut, Rheinsprung 21, 4051 Basel, Switzer- land E-mail address: maike.massierer@inria