Paper 2022/769 Original: eprint.iacr.org/2022/769 ↗

Faster Beta Weil Pairing on BLS Pairing Friendly Curves with Odd Embedding Degree

Abstract

Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the $\beta$-Weil pairing on curves with odd embedding degree which involve vertical line functions useful for sparse multiplications. For computations we used Miller's algorithm combined with storage and multifunction methods. Applying our framework to BLS-$27$, BLS-$15$ and BLS-$9$ curves at respectively the $256$ bit, the $192$ bit and the $128$ bit security level, we obtain faster $\beta$-Weil pairings than the previous state-of-the-art constructions. The correctness of all the formulas and bilinearity of pairings obtained in this work is verified by a SageMath code.