Paper 2022/348

Fast Subgroup Membership Testings for $\G_1$, $\G_2$ and $\G_T$ on Pairing-friendly Curves

Yu Dai and Kaizhan Lin and Zijian Zhou and Chang-An Zhao

Abstract

Pairing-based cryptographic protocols are typically vulnerable to small-subgroup attacks in the absence of protective measures. To thwart them, one of effective measures is to execute subgroup membership testings for the three $r$-order subgroups $\G_1$, $\G_2$ and $\G_T$, which are generally considered expensive. Inspired by the method given by Scott, we revisit this issue and generalize the testing method in this paper. Our method can be applied to a large class of curves, including curves admitting a twist and without a twist. The resulting implementation shows that for many popular pairing-friendly curves, the proposed technique significantly improves the performance of membership testings for the above three subgroups as compared with the fastest previously known one. More precisely, for $\G_2$ testing on curves admitting a twist, the new technique is about 1.9, 5.1, and 3.6 times faster than the previous one on \textit{BN-446}, \textit{KSS16-P310} and \textit{KSS18-P348}, respectively. For $\G_2$ testing on curves without a twist, there exists no efficient testing method for $\G_2$ in the literature until now. In this situation, the proposed method is about $17.3$ and $20$ times faster than the naive one on \textit{BW13-P310} and \textit{BW9-P286}, respectively.