Computing pairings on elliptic curves with embedding degree two via biextensions

Abstract Bilinear pairings have emerged as a fundamental tool in public-key cryptography, enabling advanced protocols such as identity-based encryption, 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 base field multiplications (respectively CPU clock cycles) by 17.53 % (respectively 13.58 %) for the reduced Tate pairing on supersingular curves with a 1536-bit field size and by 12.37 % (respectively 8.39 %) for the Omega pairing on non-supersingular curves of the same size. 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.