Paper 2024/1195

Constructing More Super-optimal Pairings via Small Degree Endomorphisms

Abstract

A variety of cryptographic applications are enabled by the properties of bilinear pairings on elliptic curves. Thus, efficient pairing computation is of crucial importance for practical deployments of pairing-based cryptographic protocols. One of the most important technical approaches is to construct pairing variants with short Miller loops in efficiency. Driven by this motivation, the variants of Tate pairings such as the ate and the optimal ate pairings, are successively proposed. Moreover, on specific pairing-friendly curves admitting efficiently computable automorphisms, the number of basic Miller iterations can be further reduced to $\log_2(r)/2\varphi(k)$, where $\varphi$ and $k$ denote the Euler's totient function and the embedding degree with respect to $r$, respectively. Such pairings are named as the super-optimal ate pairings. Nevertheless, several curves are not compatible with the existing methods for constructing super-optimal ate pairings as they admit no non-trivial automorphisms. This paper aims to establish a framework for constructing super-optimal ate pairings on more pairing-friendly curves employing degree-$n$ endomorphisms with $n > 1$. In practice, small degree endomorphisms (e.g. $n = 2, 3$) can be computed efficiently and are primarily considered for enhancing the performance of pairing computations. More precisely, pairing-friendly curves with CM-discriminants $7$ and $11$ are equipped with degrees-$2$ and $3$ endomorphisms, respectively, possessing the potential for constructing super-optimal ate pairings. For example, we exploit degree-$2$ endomorphism (resp. degree-$3$ endomorphism) and provide explicit formulas for the super-optimal ate pairings on family GG22D7 with CM-discriminant \(D = 7\) and embedding degree \(k = 22\) (resp. GG28D11 with CM-discriminant \(D = 11\) and embedding degree \(k = 28\)). Additionally, we select a pairing-friendly curve GG22D7-457 at the 192-bit security level for implementation, and present detailed computational procedure, concrete cost analysis, together with the experimental results. The results illustrate that our new super-optimal pairing formula derives a saving of about \(31.9\%\) \(\mathbb{F}_{p}\)-multiplications for the Miller loop on GG22D7-457 compared to the previous method. In terms of CPU clock cycles, leveraging our new formula is $26.0\%$ faster. This work expands the application of super-optimal pairings, and thus offer a broader range of choices of curves for pairing-based cryptography.