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% 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Revisiting Subgroup Membership Testing on Pairing-Friendly Curves via the Tate Pairing

  • Yu Dai,
  • Debiao He,
  • Dimitri Koshelev,
  • Cong Peng,
  • Zhijian Yang

摘要

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% 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.