The Consensys cryptography team proposed the Divide-and-Pair method to accelerate the verification of elliptic curve subgroup members
Consensys published on platform 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, proposed a new subgroup member detection method called Divide-and-Pair.Not all points on non-prime order curves like Curve25519 belong to the target subgroup; skipping this check may lead to small subgroup attacks. The NIST P series curves are of prime order and do not require this check. This method treats two known schemes as the two ends of the same parameter range, selecting optimal settings for each curve, with speeds not lower than the original methods. According to Consensys, the speedup factors for each curve are: approximately 1.6 times for Curve25519, approximately 1.3 times for Curve448, approximately 1.4 times for GC256A, approximately 10.8 times for FourQ, and approximately 7 times for Jubjub.This method has been integrated into the open-source library gnark-crypto. This library currently runs on Besu, Linea, go-ethereum, as well as 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 published at CHES 2027.
