A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Language
en
Article de revue
This item was published in
Journal of Symbolic Computation. 2015, vol. 67, p. 68-92
Elsevier
English 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 ...Read more >
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.Read less <
English Keywords
Pairings
Abelian varieties
Cryptography
European Project
Algorithmic Number Theory in Computer Science
ANR Project
Espaces de paramètres pour une arithmétique efficace et une évaluation de la sécurité des courbes - ANR-12-BS01-0010
SIM et théorie des couplages pour la sécurité de l'information et des communications - ANR-12-INSE-0014
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
SIM et théorie des couplages pour la sécurité de l'information et des communications - ANR-12-INSE-0014
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
Origin
Hal imported