Paper 2025/384

Optimizing Final Exponentiation for Pairing-Friendly Elliptic Curves with Odd Embedding Degrees Divisible by 3

Abstract

In pairing-based cryptography, final exponentiation with a large fixed exponent is crucial for ensuring unique outputs in Tate and optimal Ate pairings. While optimizations for elliptic curves with even embedding degrees have been well-explored, progress for curves with odd embedding degrees, particularly those divisible by $3$, has been more limited. This paper presents new optimization techniques for computing the final exponentiation of the optimal Ate pairing on these curves. The first exploits the fact that some existing seeds have a form enabling cyclotomic cubing and extends this to generate new seeds with the same form. The second is to generate new seeds with sparse ternary representations, replacing squaring with cyclotomic cubing. The first technique improves efficiency by $1.7\%$ and $1.5\%$ compared to the square and multiply (\textbf{SM}) method for existing seeds at $192$-bit and $256$-bit security levels, respectively. For newly generated seeds, it achieves efficiency gains of $3.6\%$ at $128$-bit, $5\%$ at $192$-bit, and $8.5\%$ at $256$-bit security levels. The second technique improves efficiency by $3.3\%$ at $128$-bit, $19.5\%$ at $192$-bit, and $4.3\%$ at $256$-bit security levels.