Paper 2025/1652
Computing Pairings on Elliptic Curves with Embedding Degree Two via Biextensions
, Sun Yat-sen University, Sun Yat-sen University, Jiaying University, Sun Yat-sen University, Guangdong Key Laboratory of Information SecurityAbstract
Bilinear pairings have emerged as a fundamental tool in public-key cryptography, enabling advanced protocols such as Identity-Based Encryption (IBE), short signatures, and zero-knowledge proofs. This paper focuses on optimizing pairing computations on curves with embedding degree 2, addressing both theoretical foundations and practical implementations. We propose an optimized double-and-add ladder algorithm that leverages the technique of y-coordinate recovery, achieving superior performance for the Tate pairing on supersingular curves and the Omega pairing on non-supersingular curves. Our method is implemented based on the RELIC cryptographic library, demonstrating significant efficiency improvements over Miller’s algorithm. Specifically, it reduces the number of Fp-multiplications (resp. CPU clock cycles) by 17.53% (resp. 13.58%) for the reduced Tate pairing on SS-1536 and by 12.37% (resp. 8.39%) for the Omega pairing on NSS-1536. This work establishes the first comprehensive implementation framework for cubical-based pairing computations on curves with embedding degree 2, providing quantified optimizations for practical cryptographic deployment.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Pairing computationSupersingularNon-supersingularBiextensionMiller’s algorithm
- Contact author(s)
-
zhengyh57 @ mail2 sysu edu cn
linjm28 @ alumni sysu edu cn
zhaochan3 @ mail sysu edu cn - History
- 2025-09-12: approved
- 2025-09-12: received
- See all versions
- Short URL
- https://ia.cr/2025/1652
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1652,
author = {Yuhao Zheng and Jianming Lin and Chang-an Zhao},
title = {Computing Pairings on Elliptic Curves with Embedding Degree Two via Biextensions},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1652},
year = {2025},
url = {https://eprint.iacr.org/2025/1652}
}
