Journal Article

x-superoptimal pairings on elliptic curves with odd prime embedding degrees: BW13-P310 and BW19-P286

Guimagang, Laurian Azebaze, Fouotsa, Emmanuel, Ayissi, Raoul

2025

Overview

The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group G of points of the elliptic curve is more predominant. At 128-bit security level two curves BW13-P310 and BW19-P286 with odd embedding degrees 13 and 19 suitable for super optimal pairing have been recommended for such pairing based protocols. But a prime embedding degree (k=13;19) eliminates some important optimisation for the pairing computation. However The Miller loop length of the superoptimal pairing is the half of that of the optimal ate pairing but involve more exponentiations that affect its efficiency. In this work, we successfully develop methods and construct algorithms to efficiently evaluate and avoid heavy exponentiations that affect the efficiency of the superoptimal pairing. This leads to the definition of new bilinear and non degenerate pairing on BW13-P310 and BW19-P286 called x-superoptimal pairing where its Miller loop is about 15.3% and 39.8% faster than the one of the optimal ate pairing previously computed on BW13-P310 and BW19-P286 respectively.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Computer systems / Curves / Efficiency / Embedding / Optimization / Prime numbers