Remember Me
Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:

OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Lubicz , David; Robert , Damien (2016)
Publisher: HAL CCSD
Languages: English
Types: Article
Subjects: [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC]

Classified by OpenAIRE into

arxiv: Mathematics::Number Theory
International audience; A Kummer variety is the quotient of an abelian variety by the automorphism $(-1)$ acting on it. Kummer varieties can be seen as a higher dimensional generalisation of the $x$-coordinate representation of a point of an elliptic curve given by its Weierstrass model. Although there is no group law on the set of points of a Kummer variety, there remains enough arithmetic to enable the computation of exponentiations via a Montgomery ladder based on differential additions. In this paper, we explain that the arithmetic of a Kummer variety is much richer than usually thought. We describe a set of composition laws which exhaust this arithmetic and show that these laws may turn out to be useful in order to improve certain algorithms. We explain how to compute efficiently these laws in the model of Kummer varieties provided by level $2$ theta functions. We also explain how to recover the full group law of the abelian variety with a representation almost as compact and in many cases as efficient as the level $2$ theta functions model of Kummer varieties.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [BBJ+08] D. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters. “Twisted edwards curves”. In: Progress in Cryptology-AFRICACRYPT 2008 (2008), pp. 389-405 (cit. on p. 2).
    • [Ber06] D. J. Bernstein. “Differential addition chains”. 2006. url: http://cr.yp.to/ecdh/ diffchain-20060219.pdf (cit. on pp. 5, 6).
    • [BCL+14] D. J. Bernstein, C. Chuengsatiansup, T. Lange, and P. Schwabe. “Kummer strikes back: new DH speed records”. 2014. eprint: 2014/134.pdf (cit. on p. 2).
    • [BL04] C. Birkenhake and H. Lange. Complex abelian varieties. Second. Vol. 302. Grundlehren der Mathematischen Wissenschaften [Fundament al Principles of Mathematical Sciences]. Berlin: Springer-Verlag, 2004, pp. xii+635. isbn: 3-540-20488-1 (cit. on pp. 7, 8, 10, 15).
    • [BCH+13] J. W. Bos, C. Costello, H. Hisil, and K. Lauter. “Fast cryptography in genus 2”. In: Advances in Cryptology-EUROCRYPT 2013. Springer, 2013, pp. 194-210 (cit. on p. 2).
    • [Bro06] D. R. Brown. “Multi-dimensional Montgomery ladders for elliptic curves”. 2006. eprint: 2006/220 (cit. on pp. 6, 16).
    • [Can87] D. G. Cantor. “Computing in the Jacobian of a hyperelliptic curve”. In: Math. Comp. 48.177 (1987), pp. 95-101. issn: 0025-5718 (cit. on p. 1).
    • [Cos11] R. Cosset. “Application des fonctions thêta à la cryptographie sur courbes hyperelliptiques”. PhD thesis. 2011 (cit. on p. 2).
    • [CR13] R. Cosset and D. Robert. “An algorithm for computing (`; `)-isogenies in polynomial time on Jacobians of hyperelliptic curves of genus 2”. Accepted for publication in Mathematics of computation. 2013. url: http://www.normalesup.org/~robert/pro/publications/ articles/niveau.pdf. HAL: hal-00578991, eprint: 2011/143 (cit. on pp. 2, 12, 15).
    • [Dup06] R. Dupont. “Moyenne arithmetico-geometrique, suites de Borchardt et applications”. In: These de doctorat, Ecole polytechnique, Palaiseau (2006) (cit. on p. 11).
    • [GLV01] R. P. Gallant, R. J. Lambert, and S. A. Vanstone. “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”. In: CRYPTO. Ed. by J. Kilian. Vol. 2139. Lecture Notes in Computer Science. Springer, 2001, pp. 190-200. isbn: 3-540-42456-3 (cit. on pp. 6, 13).
    • [Gau07] P. Gaudry. “Fast genus 2 arithmetic based on Theta functions”. In: Journal of Mathematical Cryptology 1.3 (2007), pp. 243-265 (cit. on pp. 1, 2, 13, 16).
    • [GL09] P. Gaudry and D. Lubicz. “The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines”. In: Finite Fields and Their Applications 15.2 (2009), pp. 246-260 (cit. on p. 1).
    • [GL12] E. Z. Goren and K. E. Lauter. “Genus 2 curves with complex multiplication”. In: International Mathematics Research Notices 2012.5 (2012), pp. 1068-1142 (cit. on p. 11).
    • [Got59] E. Gottschling. “Explizite bestimmung der randflächen des fundamentalbereiches der modulgruppe zweiten grades”. In: Mathematische Annalen 138.2 (1959), pp. 103-124 (cit. on p. 11).
    • [Har00] R. Hartshorne. Algebraic geometry. Springer, 2000 (cit. on p. 10).
    • [HC] H. Hisil and C. Costello. “Jacobian Coordinates on Genus 2 Curves”. In: (). eprint: 2014/385 (cit. on pp. 1, 17).
    • [Igu72] J.-I. Igusa. Theta functions. Die Grundlehren der mathematischen Wissenschaften, Band 194. New York: Springer-Verlag, 1972, pp. x+232 (cit. on p. 8).
    • [Kem88] G. Kempf. “Multiplication over abelian varieties”. In: American Journal of Mathematics 110.4 (1988), pp. 765-773 (cit. on pp. 10-12).
    • [Kem89] G. Kempf. “Linear systems on abelian varieties”. In: American Journal of Mathematics 111.1 (1989), pp. 65-94 (cit. on pp. 8, 10, 14).
    • [Koh11] D. Kohel. “Arithmetic of split Kummer surfaces: Montgomery endomorphism of Edwards products”. In: Coding and Cryptology. Springer, 2011, pp. 238-245 (cit. on p. 4).
    • [Koi76] S. Koizumi. “Theta relations and projective normality of abelian varieties”. In: American Journal of Mathematics (1976), pp. 865-889 (cit. on pp. 8-11, 14).
    • [Lan05] T. Lange. “Formulae for arithmetic on genus 2 hyperelliptic curves”. In: Applicable Algebra in Engineering, Communication and Computing 15.5 (2005), pp. 295-328 (cit. on p. 1).
    • [LR10] D. Lubicz and D. Robert. “Efficient pairing computation with theta functions”. In: Algorithmic Number Theory. Lecture Notes in Comput. Sci. (2010). Ed. by G. Hanrot, F. Morain, and E. Thomé. 9th International Symposium, Nancy, France, ANTS-IX, July 19-23, 2010, Proceedings. doi: 10.1007/978-3-642-14518-6_21 (cit. on pp. 11, 12).
    • [LR12] D. Lubicz and D. Robert. “Computing isogenies between abelian varieties”. In: Compos. Math. 148.5 (2012), pp. 1483-1515. issn: 0010-437X. doi: 10.1112/S0010437X12000243. url: http://dx.doi.org/10.1112/S0010437X12000243 (cit. on pp. 2, 9, 12, 13, 15).
    • [LR13] D. Lubicz and D. Robert. “A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties”. In: (2013). preprint (cit. on pp. 2, 7, 11-13).
    • [Mon87] P. L. Montgomery. “Speeding the Pollard and elliptic curve methods of factorization”. In: Mathematics of computation 48.177 (1987), pp. 243-264 (cit. on p. 1).
    • [Mon92] P. L. Montgomery. “Evaluating recurrences of form Xm+n= f (Xm, Xn, Xm- n) via Lucas chains”. In: Available at ftp. cwi. nl:/pub/pmontgom/lucas. ps. gz 349 (1992) (cit. on p. 1).
    • [Mum66a] D. Mumford. “On the equations defining abelian varieties. I”. In: Invent. Math. 1 (1966), pp. 287-354 (cit. on p. 8).
    • [Mum66b] D. Mumford. “On the equations defining abelian varieties. I”. In: Invent. Math. 1 (1966), pp. 287-354 (cit. on pp. 2, 7-10).
    • [Mum67a] D. Mumford. “On the equations defining abelian varieties. II”. In: Invent. Math. 3 (1967), pp. 75-135 (cit. on p. 2).
    • [Mum67b] D. Mumford. “On the equations defining abelian varieties. III”. In: Invent. Math. 3 (1967), pp. 215-244 (cit. on p. 2).
    • [Mum69] D. Mumford. “Varieties defined by quadratic equations”. In: Questions on Algebraic Varieties (CIME, III Ciclo, Varenna, 1969) (1969), pp. 29-100 (cit. on p. 10).
    • [Mum70] D. Mumford. Abelian varieties. Tata Institute of Fundamental Research Studies in Mathematics, No. 5. Published for the Tata Institute of Fundamental Research, Bombay, 1970, pp. viii+242 (cit. on p. 7).
    • [Mum83] D. Mumford. Tata lectures on theta I. Vol. 28. Progress in Mathematics. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. Boston, MA: Birkhäuser Boston Inc., 1983, pp. xiii+235. isbn: 3-7643-3109-7 (cit. on pp. 7-9).
    • [Mum84] D. Mumford. Tata lectures on theta II. Vol. 43. Progress in Mathematics. Jacobian theta functions and differential equations, With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. Boston, MA: Birkhäuser Boston Inc., 1984, pp. xiv+272. isbn: 0-8176-3110-0 (cit. on p. 11).
    • [Mum91] [Rob10] D. Mumford. Tata lectures on theta III. Vol. 97. Progress in Mathematics. With the collaboration of Madhav Nori and Peter Norman. Boston, MA: Birkhäuser Boston Inc., 1991, pp. viii+202. isbn: 0-8176-3440-1 (cit. on p. 8).
    • D. Robert. “Fonctions thêta et applications à la cryptographie”. PhD thesis. Université Henri-Poincarré, Nancy 1, France, July 2010. url: http://www.normalesup.org/~robert/ pro/publications/academic/phd.pdf. Slides http://www.normalesup.org/~robert/ pro/publications/slides/2010-07-phd.pdf, TEL: tel-00528942. (Cit. on pp. 2, 11).
    • IRMAR, Universté de Rennes 1, Campus de Beaulieu, F-35042 Rennes FRANCE E-mail address:
    • URL: http://perso.univ-rennes1.fr/david.lubicz/
    • Délégation Générale de l'Armement, CELAR - BP 57419, 35174 Bruz Cedex INRIA Bordeaux-Sud-Ouest, 200 avenue de la Vieille Tour, 33405 Talence Cedex FRANCE E-mail address:
  • No related research data.
  • No similar publications.
Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok