A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties

Article English OPEN
Lubicz , David ; Robert , Damien (2015)
  • Publisher: Elsevier
  • Journal: Journal of Symbolic Computation (issn: 0747-7171)
  • Related identifiers: doi: 10.1016/j.jsc.2014.08.001
  • Subject: [ MATH.MATH-NT ] Mathematics [math]/Number Theory [math.NT] | Abelian varieties | Cryptography | Pairings

International audience; In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we obtain a variant of optimal pairings on abelian varieties. Finally, by introducing new addition formulas, we explain how to compute optimal pairings on Kummer varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case.
  • References (11)
    11 references, page 1 of 2

    1. Christophe Ar`ene, Tanja Lange, Michael Naehrig, and Christophe Ritzenthaler. Faster computation of the Tate pairing. J. Number Theory, 131(5):842-857, 2011. With supplementary material available online.

    2. Paulo S. L. M. Barreto, Steven D. Galbraith, Colm O´' hE´igeartaigh, and Michael Scott. Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptogr., 42(3):239-271, 2007.

    3. Joppe W Bos, Craig Costello, Huseyin Hisil, and Kristin Lauter. Two is greater than one. Technical report, Cryptology ePrint Archive, Report 2012/670, 2012. Available at: http://eprint. iacr. org/2012/670.

    4. Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, editors. Handbook of elliptic and hyperelliptic curve cryptography. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.

    5. Romain Cosset and Damien Robert. An algorithm for computing (ℓ, ℓ)-isogenies in polynomial time on jacobians of hyperelliptic curves of genus 2. HAL: hal-00578991, eprint: 2011/143, 03 2011.

    6. Craig Costello, Tanja Lange, and Michael Naehrig. Faster pairing computations on curves with high-degree twists. Public Key Cryptography-PKC 2010, pages 224-242, 2010.

    7. Andreas Enge. Bilinear pairings on elliptic curves. HAL: , 2012.

    8. Steven D. Galbraith, Florian Hess, and Frederik Vercauteren. Hyperelliptic pairings. In Pairing-based cryptography-Pairing 2007, volume 4575 of Lecture Notes in Comput. Sci., pages 108-131. Springer, Berlin, 2007.

    9. Steven D Galbraith and Xibin Lin. Computing pairings using x-coordinates only. Designs, Codes and Cryptography, 50(3):305-324, 2009.

    10. P. Gaudry. Fast genus 2 arithmetic based on Theta functions. J. of Mathematical Cryptology, 1:243-265, 2007.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository
Share - Bookmark