Paper 2024/1195

Constructing More Super-optimal Pairings via Small Degree Endomorphisms

Abstract

Bilinear pairings play a crucial role in public-key cryptography. Accelerating the pairing computation, especially shortening the length of the Miller loop is of great significance. Several researches have been focused on constructing pairings with shorter Miller loops. The variants of Tate pairings such as ate pairings and optimal ate pairings, are successively proposed. Moreover, for several specific pairing-friendly curves with efficiently-computable automorphisms, the Miller loop can be further shortened to $$, where $$ (resp. $$) represents the Euler's function (resp. embedding degree). Such pairings are named as super-optimal (ate) pairings, whose lengths of Miller loops achieve the theoretical lower bound. Nevertheless, not all pairing-friendly curves are compatible with the construction of super-optimal pairings. This paper aims to provide a framework for constructing super-optimal pairings on more pairing-friendly curves by employing the degree-$$ endomorphisms where $$. We mainly targets on enhancing the performance for the pairing computation on family GG22D7 with CM-discriminant $$ and embedding degree $$ (resp. family GG28D11 with CM- discriminant $$ and embedding degree $$) by exploiting degree-$$ endomorphisms (resp. degree-$$ endomorphisms), and provide explicit formulas for the corresponding super-optimal ate pairings. For implementation, by taking a pairing-friendly curve GG22D7-457 at the 192-bit security level as an example, we present the corresponding detailed implementation procedure, computational cost analysis, and experimental results. The results illustrate that compared with the previous method, our new super-optimal pairing formula can reduce about $$ of $$-multiplications for the Miller loop on GG22D7-457. In terms of CPU clock cycles, leveraging our super-optimal pairing formula is $$ faster. This work extends the application of super-optimal pairings, and has the potential to offer a wider range of choices of curves for pairing-based cryptography.