Paper 2024/1790

Revisiting subgroup membership testing on pairing-friendly curves via the Tate pairing

Yu Dai, Wuhan University
Debiao He, Wuhan University
Dmitrii Koshelev, University of Lleida
Cong Peng, Wuhan University
Zhijian Yang, Wuhan University
Abstract

In 2023, Koshelev proposed an efficient method for subgroup membership testing on a list of non-pairing-friendly curves via the Tate pairing. In fact, this method can also be applied to certain pairing-friendly curves, such as the BLS and BW13 families, at a cost of two small Tate pairings. In this paper, we revisit Koshelev's method to enhance its efficiency for these curve families. First, we present explicit formulas for computing the two small Tate pairings. Compared to the original formulas, the new versions offer shorter Miller iterations and reduced storage requirements. Second, we provide a high-speed software implementation on a 64-bit processor. Our results demonstrate that the new method is up to $62.0\%$ and $22.4\%$ faster than the state-of-the-art on the BW13-310 and BLS24-315 curves, respectively, while being $14.1\%$ slower on BLS12-381. When precomputation is utilized, our method achieves speed improvements of up to $34.8\%$, $110.6\%$, and $63.9\%$ on the BLS12-381, BW13-310, and BLS24-315 curves, respectively.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
pairing-friendly curvessubgroup membership testingTate pairing
Contact author(s)
eccdaiy39 @ gmail com
hedebiao @ whu edu cn
dimitri koshelev @ gmail com
cpeng @ whu edu cn
zjyang math @ whu edu cn
History
2024-11-04: approved
2024-11-02: received
See all versions
Short URL
https://ia.cr/2024/1790
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1790,
      author = {Yu Dai and Debiao He and Dmitrii Koshelev and Cong Peng and Zhijian Yang},
      title = {Revisiting subgroup membership testing on pairing-friendly curves via the Tate pairing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1790},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1790}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.