Paper 2022/716

x-Superoptimal Pairings on some Elliptic Curves with Odd Prime Embedding Degrees

Emmanuel Fouotsa, The University of Bamenda
Azebaze Guimagang Laurian, The University fo Yaounde 1
Ayissi Raoul, The University of Yaounde 1
Abstract

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 $\mathbb{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 wchich is about $27.3\%$ and $49\%$ faster than the optimal ate pairing previousely computed on $BW13-P310$ and $BW19-P286$ respectively.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Optimal pairingSuperoptimal pairing$x$-Superoptimal pairing Miller function
Contact author(s)
emmanuelfouotsa @ yahoo fr
azebazelaurian @ yahoo fr
raoulayissi @ yahoo fr
History
2022-06-06: approved
2022-06-05: received
See all versions
Short URL
https://ia.cr/2022/716
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/716,
      author = {Emmanuel Fouotsa and Azebaze Guimagang Laurian and Ayissi Raoul},
      title = {x-Superoptimal Pairings on some Elliptic Curves with Odd Prime Embedding Degrees},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/716},
      year = {2022},
      url = {https://eprint.iacr.org/2022/716}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.