International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Don’t Forget Pairing-Friendly Curves with Odd Prime Embedding Degrees

Authors:
Yu Dai , School of Mathematics, Wuhan University, Wuhan, China; School of Mathematics, Sun Yat-sen University, Guangzhou, China
Fangguo Zhang , School of Computer Science and Engineering, Sun Yat-sen University,Guangzhou, China; Guangdong Key Laboratory of Information Security, Guangzhou, China
Chang-an Zhao , School of Mathematics, Sun Yat-sen University, Guangzhou, China; Guangdong Key Laboratory of Information Security, Guangzhou, China
Download:
DOI: 10.46586/tches.v2023.i4.393-419
URL: https://tches.iacr.org/index.php/TCHES/article/view/11171
Search ePrint
Search Google
Abstract: Pairing-friendly curves with odd prime embedding degrees at the 128-bit security level, such as BW13-310 and BW19-286, sparked interest in the field of public-key cryptography as small sizes of the prime fields. However, compared to mainstream pairing-friendly curves at the same security level, i.e., BN446 and BLS12-446, the performance of pairing computations on BW13-310 and BW19-286 is usually considered inefficient. In this paper we investigate high performance software implementations of pairing computation on BW13-310 and corresponding building blocks used in pairing-based protocols, including hashing, group exponentiations and membership testings. Firstly, we propose efficient explicit formulas for pairing computation on this curve. Moreover, we also exploit the state-of-art techniques to implement hashing in G1 and G2, group exponentiations and membership testings. In particular, for exponentiations in G2 and GT , we present new optimizations to speed up computational efficiency. Our implementation results on a 64-bit processor show that the gap in the performance of pairing computation between BW13-310 and BN446 (resp. BLS12-446) is only up to 4.9% (resp. 26%). More importantly, compared to BN446 and BLS12-446, BW13-310 is about 109.1% − 227.3%, 100% − 192.6%, 24.5%−108.5% and 68.2%−145.5% faster in terms of hashing to G1, exponentiations in G1 and GT , and membership testing for GT , respectively. These results reveal that BW13-310 would be an interesting candidate in pairing-based cryptographic protocols.
BibTeX
@article{tches-2023-33353,
  title={Don’t Forget Pairing-Friendly Curves with Odd Prime Embedding Degrees},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 4},
  pages={393-419},
  url={https://tches.iacr.org/index.php/TCHES/article/view/11171},
  doi={10.46586/tches.v2023.i4.393-419},
  author={Yu Dai and Fangguo Zhang and Chang-an Zhao},
  year=2023
}