Paper 2024/1790

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

Abstract

The two groups $\mathbb{G}_1$ and $\mathbb{G}_2$ on pairing-friendly curves typically have nontrivial cofactors, which may give rise to security vulnerabilities (e.g., small subgroup attacks) in pairing-based protocols. In order to avoid the pitfalls of cofactors, it is necessary to perform subgroup membership testing. Previous testing methods for such curves relied on efficiently computable endomorphisms. In 2023, Koshelev introduced a novel technique of subgroup membership testing for a list of non-pairing-friendly curves, requiring at most two small Tate pairings. In fact, this technique can also be applied to certain pairing-friendly curves, such as those from the BLS and BW13 families. In this paper, we revisit Koshelev's method and propose simplified formulas for computing the two Tate pairings. Compared to the original formulas, ours reduce both the number of Miller's iterations and the storage requirements. Moreover, we provide a high-speed software implementation on a 64-bit processor. Our experimental results show that the new method outperforms the state-of-the-art one by up to $62.0\%$ and $41.2\%$ on for singular $\mathbb{G}_1$ membership testing on the BW13-310 and BLS48-575 curves, respectively. When precomputation is utilized, the improvements increase to $110.6\%$ and $74.4\%$ on the two curves, respectively.