International Association
for Cryptologic Research

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.