Paper 2025/1311

Batch subgroup membership testing on pairing-friendly curves

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.