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
-
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},
url = {https://eprint.iacr.org/2021/1162}
}