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

The \textit{V. S. Miller}'s algorithm [J. Cryptology 17, No. 4, 235--261 (2004; Zbl 1078.14043)] was proposed as a tool to efficiently compute the pairing of Weil on elliptic curves and later on improved and applied to other pairings as well. The algorithm finds the function associated (up to a constant factor) to a principal divisor of the form \(n[P]-n[0]\),\, with \(P\)\, a point of order \(n\),\, using a chain of double and add points. In a previous work [Lect. Notes Comput. Sci. 6197, 251--269 (2010; Zbl 1260.11043)] the authors of the present paper presented a new approach (which doesn't use Miller's algorithm) to compute pairings. That algorithm is based on the theory of theta functions and can be applied to all abelian varieties (and also to Kummer varieties using \textit{symmetric pairings}). In the present paper, the authors study the adaptation of Miller's algorithm to the new setting, i.~e., to compute the function associated to a divisor on an abelian variety with Chern class 0 linearly equivalent to \(0\)\, and ``we focus on the optimizations which consist in reducing the number of loops in pairings computation algorithms by using non-trivial endomorphisms of the abelian varieties'' (the Frobenius endomorphism in the case of a finite underlying field). The structure of the paper is as follows: Section 2 summarizes the theory of (classical analytic) theta functions, Section 3 deals with the addition laws in the set of points of an abelian variety, Section 4 is devoted to the generalization of Miller's algorithm to abelian varieties and Section 5 to the computation of Weil and Tata pairings of those varieties. Then Section 6 deals with generalizations of ate pairings to abelian varieties (defined over a finite field) and Section 7 with optimal ate pairings. Finally Section 8 discusses some computational issues.