Paper 2013/192

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

David Lubicz and Damien Robert

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
PairingsAbelian varieties
Contact author(s)
damien robert @ inria fr
History
2013-04-02: received
Short URL
https://ia.cr/2013/192
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/192,
      author = {David Lubicz and Damien Robert},
      title = {A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties},
      howpublished = {Cryptology ePrint Archive, Paper 2013/192},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/192}},
      url = {https://eprint.iacr.org/2013/192}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.