Fast subgroup membership testings for \(\mathbb{G}_1, \mathbb{G}_2\) and \(\mathbb{G}_T\) on pairing-friendly curves (Q6074017)

Let \(E\) be an ordinary elliptic curve \(E\) over a prime field \(\mathbb{F}_p\). A pairing on \(E\) is a bilinear map \(e : G_1 \times G_2 \rightarrow G_T \), where \(G_1\), \(G_2\) and \(G_T\) are three cyclic subgroups with large prime order \(r\). In the asymmetric case, the input groups \(G_1\) and \(G_2\) are two distinct subgroups of \(E(\mathbb{F}_{p^k} )\), while the output group \(G_T\) is a subgroup of \(\mathbb{F}^*_{p^k}\). The security of pairing-based cryptographic protocols is based on the difficulty of Discrete Logarithm Problem in the above groups. Such protocols are typically vulnerable to small-subgroup attacks. Subgroup membership testing is one of the feasible methods to address these attacks. Recently, a new method is proposed of subgroup membership testing for \(G_1\), \(G_2\) and \(G_T\) on the BLS family [\textit{M. Scott}, Cryptology. ePrint Archive, Paper 2021/1130 (2021), \url{https://eprint.iacr.org/2021/1130}]. Furthermore, it is proved that is also also suitable for the BN family [\textit{N. El Mrabet} (ed.) et al., Progress in cryptology -- AFRICACRYPT 2023. 14th international conference on cryptology in Africa, Sousse, Tunisia, July 19--21, 2023. Proceedings. Cham: Springer (2023; Zbl 1529.94003)]. In this paper, a general method for \(G_2\) membership testing on pairing-friendly curves is proposed, and it is shown that it requires around \(\log r/\phi(k)\) bit operations on many pairing friendly curves. Furthermore, fast methods for \(G_1\) and \(G_T\) membership testing are also presented, which require approximately \(\log r/2\) and \(\log r/\phi(k)\) bit operations, respectively. Moreover, the proposed techniques are implemented over different pairing-friendly curves on a 64-bit computing platform within the RELIC cryptographic library.