ConsenSys Researchers Propose Divide-and-Pair Method to Accelerate Elliptic Curve Subgroup Membership Checks

Huo Xing Cai Jing reports that ConsenSys posted on X that its cryptographer Youssef El Housni, along with collaborators from Wuhan University of Technology, KU Leuven, and the National Academy of Sciences of Belarus, has proposed a new method for subgroup membership detection called "Divide-and-Pair."

On non-prime-order curves such as Curve25519, not all points belong to the target subgroup; skipping this check may expose the system to small-subgroup attacks. In contrast, NIST P-series curves have prime order and do not require this check. This method treats two known approaches as endpoints within the same parameter range, selecting optimal settings for each curve while maintaining or exceeding the speed of previous methods. According to ConsenSys, the speedup factors for each curve are approximately: Curve25519 at 1.6x, Curve448 at 1.3x, GC256A at 1.4x, FourQ at 10.8x, and Jubjub at 7x.

This method has been integrated into the open-source library gnark-crypto. The library currently runs on Besu, Linea, go-ethereum, and systems based on gnark such as Succinct and Lighter. The related paper has been accepted by IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) and will be presented at CHES 2027.