Paper 2025/1311

Batch subgroup membership testing on pairing-friendly curves

Youssef El Housni, Linea

Georgios Fotiadis, Ubitech Ltd.

Abstract

A major challenge in elliptic curve cryptosystems consists in efficiently mitigating the small-subgroup attack. This paper explores batch subgroup membership testing (SMT) on pairing-friendly curves, particularly for the Barreto–Lynn–Scott family of embedding degree 12 (BLS12) due to its critical role in modern pairing-based cryptography. Our research introduces a novel two-step procedure for batch SMT to rapidly verify multiple points at once, cleverly combining the already existing tests based on the Tate pairing and a non-trivial curve endo- morphism. We clarify why the invented technique is significantly faster (despite a negligible error probability) than testing each point individu- ally. Moreover, it is applicable to prominent curves like BLS12-381 and BLS12-377 being frequently employed in zero-knowledge applications. Nonetheless, to further enhance the speed (or reduce the error proba- bility) of the proposed batch point validation, we have generated two new BLS12 curves that are specifically optimized for this purpose. We also provide an open-source high-speed software implementation in Go, showcasing significant performance improvements achieved by our work.

@misc{cryptoeprint:2025/1311,
      author = {Dimitri Koshelev and Youssef El Housni and Georgios Fotiadis},
      title = {Batch subgroup membership testing on pairing-friendly curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1311},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1311}
}