Paper 2024/517

Fast pairings via biextensions and cubical arithmetic

Damien Robert, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux
Abstract

Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, \ldots, pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions. This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt these algorithms to pairings on any model of abelian varieties with a polarisation $\Phi_D$, as long as we have an explicit theorem of the square for $D$. In particular, we give explicit formulas for the arithmetic of the biextension (and cubical torsor structure) associated to the divisor $D=2(0_E)$ on an elliptic curve. We derive very efficient pairing formulas on elliptic curves and Kummer lines. Notably for generic pairings on Montgomery curves, our cubical biextension ladder algorithm to compute pairings costs only $15M$ by bits, which as far as I know is faster than any pairing doubling formula in the literature.

Note: Corrected some typos

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
pairingselliptic curvesdiscrete logarithm
Contact author(s)
damien robert @ inria fr
History
2024-07-03: last of 4 revisions
2024-04-01: received
See all versions
Short URL
https://ia.cr/2024/517
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/517,
      author = {Damien Robert},
      title = {Fast pairings via biextensions and cubical arithmetic},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/517},
      year = {2024},
      url = {https://eprint.iacr.org/2024/517}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.