Paper 2025/468 Original: eprint.iacr.org/2025/468 ↗

Optimized Frobenius and Cyclotomic Cubing for Enhanced Pairing Computation

Abstract

Efficient implementation of pairing-based cryptosystems relies on high-performance arithmetic in finite fields $\mathbb{F}_{p}$ and their extensions $\mathbb{F}_{p^k}$, where $k$ denotes the embedding degree. A small embedding degree is crucial since a part of the arithmetic for pairing computation occurs in $\mathbb{F}_{{p}^k}$, including squaring, multiplication, and Frobenius operations. In this paper, we present a fast and efficient method for computing the Frobenius endomorphism in the finite field $\mathbb{F}_{p^k}$, along with an analysis of its computational complexity. Furthermore, we introduce an optimization for cyclotomic cubing operations tailored to several pairing-friendly elliptic curves, which are essential for the calculation of Tate pairing and its derivatives.