Paper 2025/670

Biextensions in pairing-based cryptography

Jianming Lin, Sun Yat-sen University
Damien Robert, Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251, INRIA CANARI team, Talence, France
Chang-An Zhao, Sun Yat-sen University
Yuhao Zheng, Sun Yat-sen University
Abstract

Bilinear pairings constitute a cornerstone of public-key cryptography, where advancements in Tate pairings and their efficient variants have emerged as a critical research domain within cryptographic science. Currently, the computation of pairings can be effectively implemented through three distinct algorithmic approaches: Miller’s algorithm, the elliptic net algorithm (as developed by Stange), and cubical-based algorithms (as proposed by Damien Robert). Biextensions are the geometric object underlying the arithmetic of pairings, and all three approaches can be seen as a different way to represent biextension elements. In this paper, we revisit the biextension geometric point of view for pairing computation and investigate in more detail the cubical representation for pairing-based cryptography. Utilizing the twisting isomorphism, we derive explicit formulas and algorithmic frameworks for the ate pairing and optimal ate pairing computations. Additionally, we present detailed formulas and introduce an optimized shared cubical ladder algorithm for super-optimal ate pairings. Through concrete computational analyses, we compare the performance of our cubical-based methods with the Miller's algorithm on various well-known families of pairing-friendly elliptic curves. Our results demonstrate that the cubical-based algorithm outperforms the Miller's algorithm by bits in certain specific situations, establishing its potential as an alternative for pairing computation.

Note: Some typos in Alg. 8 were corrected. Thank Krijn Reijnders for pointing out this error.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Pairing computationMiller's algorithmbiextensioncubical arithmeticsuper-optimal ate pairing
Contact author(s)
linjm28 @ mail2 sysu edu cn
damien robert @ inria fr
zhaochan3 @ mail sysu edu cn
zhengyh57 @ mail2 sysu edu cn
History
2025-04-30: revised
2025-04-14: received
See all versions
Short URL
https://ia.cr/2025/670
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/670,
      author = {Jianming Lin and Damien Robert and Chang-An Zhao and Yuhao Zheng},
      title = {Biextensions in pairing-based cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/670},
      year = {2025},
      url = {https://eprint.iacr.org/2025/670}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.