Optimal Pairings on Abelian Varieties with Theta Functions

Опубликовано 27 июля 2016, 1:59

Pairings on elliptic curves have allowed the development of new cryptographic protocols like anonymous certificates, multicanal broadcasting... For an elliptic curve, or more generally a Jacobian, computing the pairing uses an algorithm due to Miller that explicitly compute some functions associated to divisors on the curve. In this talk, we show how one can use Riemann relations on the Theta model to compute the Tate and Weil pairings on abelian varieties that are not necessarily Jacobians. We show how to generalize this to pairings reducing the loop length of Miller's algorithm (ate, twisted ate, optimal ate), and also how to compute symmetric pairings on Kummer varieties. While elaborated for general abelian varieties, this algorithm is surprisingly fast in low dimension, and is almost competitive with the fastest known pairings computation on elliptic curves. This is a joint work with David Lubicz.