Batch subgroup membership testing on pairing-friendly curves

Abstract

A major challenge in elliptic curve cryptosystems consists in mitigating efficiently 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 endomorphism. We clarify why the invented technique is significantly faster (despite a negligible error probability) than testing each point individually. 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 probability) 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 explicitly significant performance improvements achieved by our work.

Publication
Pre-print