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

Loubna Ghammam; Nadia El Mrabet; Walid Haddaji; Leila Ben Abdelghani

Paper 2025/384

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

Loubna Ghammam

, ITK Engineering GmbH Im Speyerer Tal 6 Rülzheim 76761 Germany

Nadia El Mrabet

, Laboratory of Secure System and Architecture (SSA), Ecole des Mines de Saint Etienne,880 Rte de Mimet, Campus Georges Charpak Provence, 13120, Gardanne, France

Walid Haddaji, Center for military research, military academy, Tunis, Tunisia

Leila Ben Abdelghani, Laboratory of Analysis, Probability and Fractals, Faculty of Sciences, Environment Avenue, Omrane, 5000, Monastir, Tunisia

Abstract

In pairing-based cryptography, the final exponentiation with a large fixed exponent is crucial for ensuring unique outputs in both Tate and optimal ate pairings. While significant strides have been made in optimizing elliptic curves with even embedding degrees, progress remains limited for curves with odd embedding degrees, especially those divisible by $3$. This paper introduces novel techniques to optimize the computation of the final exponentiation for the optimal ate pairing on such curves. The first technique leverages the structure of certain existing seeds to enable the use of cyclotomic cubing and extends this concept to generate new seeds with similar characteristics. The second technique focuses on producing new sparse ternary representation seeds to utilize cyclotomic cubing as a replacement for squaring. These approaches result in performance improvements of up to $19.3\%$ in the computation of the final exponentiation for the optimal ate pairing on $BLS15$ and $BLS27$ curves.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Elliptic curves pairings final exponentiation cyclotomic cubing complexity
Contact author(s): ghammam loubna @ gmail com
nadia elmrabet @ emse fr
haddajiwalid95 @ gmail com
leila benabdelghani @ gmail com
History: 2025-04-17: last of 2 revisions; 2025-02-28: received; See all versions
Short URL: https://ia.cr/2025/384
License: CC BY

BibTeX

@misc{cryptoeprint:2025/384,
      author = {Loubna Ghammam and Nadia El Mrabet and Walid Haddaji and Leila Ben Abdelghani},
      title = {Optimizing Final Exponentiation for Pairing-Friendly Elliptic Curves with Odd Embedding Degrees Divisible by 3},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/384},
      year = {2025},
      url = {https://eprint.iacr.org/2025/384}
}