Optimal Pairings on Abelian Varieties with Theta Functions

  • Damien Robert | University of Bordeaux

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.

Speaker Details

Damien Robert is an INRIA researcher in the LFANT team at University of Bordeaux. Previously, he was a postdoctoral researcher at Microsoft Research (MSR) in the cryptography group. Damien works in the field of applications of abelian varieties in public key cryptography, with main subjects of interest Jacobians of hyperelliptic curves (and more specifically genus 2 curves), computing isogenies and point counting, and also arithmetic with theta functions and class polynomials generation. Damien Robert worked on his PhD thesis under the supervision of Guillaume Hanrot in the Caramel team at Nancy.

    • Portrait of Damien Robert

      Damien Robert

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks