Paper 2021/1162

Software Implementation of Optimal Pairings on Elliptic Curves with Odd Prime Embedding Degrees

Yu Dai, Zijian Zhou, Fangguo Zhang, and Chang-An Zhao

Abstract

Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy reduction into the finite field arithmetic. Then, we present a new method to execute Miller's algorithm. Compared with the standard Miller iteration formulas, the new ones provide a more efficient software implementation of pairing computations. At last, we also give a fast formula to perform the final exponentiation. Our implementation results indicate that it can be computed efficiently, while it is slower than that over the BLS-446 curve at the same security level.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Pairing ComputationsOdd Prime Embedding DegreeMiller Iteration
Contact author(s)
daiy39 @ mail2 sysu edu cn
History
2021-09-14: received
Short URL
https://ia.cr/2021/1162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1162,
      author = {Yu Dai and Zijian Zhou and Fangguo Zhang and Chang-An Zhao},
      title = {Software Implementation of Optimal Pairings on Elliptic Curves with Odd Prime Embedding Degrees},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1162},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1162}},
      url = {https://eprint.iacr.org/2021/1162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.