Paper 2023/1958

Revisiting Pairing-friendly Curves with Embedding Degrees 10 and 14

Yu Dai
Debiao He
Cong Peng
Zhijian Yang
Chang-an Zhao
Abstract

Since 2015, there has been a significant decrease in the asymptotic complexity of computing discrete logarithms in finite fields. As a result, the key sizes of many mainstream pairing-friendly curves have to be updated to maintain the desired security level. In PKC'20, Guillevic conducted a comprehensive assessment of the security of a series of pairing-friendly curves with embedding degrees ranging from $9$ to $17$. In this paper, we focus on pairing-friendly curves with embedding degrees of 10 and 14. First, we extend the optimized formula of the optimal pairing on BW13-310, a 128-bit secure curve with a prime $p$ in 310 bits and embedding degree $13$, to our target curves. This generalization allows us to compute the optimal pairing in approximately $\log r/2\varphi(k)$ Miller iterations, where $r$ and $k$ are the order of pairing groups and the embedding degree respectively. Second, we develop optimized algorithms for cofactor multiplication for $\mathbb{G}_1$ and $\mathbb{G}_2$, as well as subgroup membership testing for $\mathbb{G}_2$ on these curves. Based on these theoretical results a new 128-bit secure curve emerges: BW14-351. Finally, we provide detailed performance comparisons between BW14-351 and other popular curves on a 64-bit platform in terms of pairing computation, hashing to $\mathbb{G}_1$ and $\mathbb{G}_2$, group exponentiations and subgroup membership testings. Our results demonstrate that BW14-351 is a strong candidate for building pairing-based cryptographic protocols.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2024
Contact author(s)
eccdaiy39 @ gmail com
hedebiao @ 163 com
cpeng @ whu edu cn
zhaochan3 @ mail sysu edu cn
History
2024-09-20: revised
2023-12-25: received
See all versions
Short URL
https://ia.cr/2023/1958
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1958,
      author = {Yu Dai and Debiao He and Cong Peng and Zhijian Yang and Chang-an Zhao},
      title = {Revisiting Pairing-friendly Curves with Embedding Degrees 10 and 14},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1958},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1958}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.