Consensys Proposes Divide-and-Pair Method, Speeds FourQ Subgroup Checks 10.8x

Consensys has proposed Divide-and-Pair, a new subgroup membership detection method that speeds checks on the FourQ curve by about 10.8 times. According to Odaily, Consensys cryptographer Youssef El Housni and collaborators from Wuhan University of Technology, KU Leuven, and the National Academy of Sciences of Belarus developed the method. The approach treats two existing methods as opposite ends of the same parameter range and selects settings for each curve, with performance no slower than the existing methods. Reported speedups are about 1.6 times for Curve25519, 1.3 times for Curve448, 1.4 times for GC256A, 10.8 times for FourQ, and seven times for Jubjub. On curves that do not have prime order, such as Curve25519, not every point belongs to the target subgroup, and skipping the check may expose systems to small-subgroup attacks. NIST P-series curves have prime order and do not require this check. The method has been integrated into the open-source gnark-crypto library, which is used by Besu, Linea, go-ethereum, and systems based on gnark, including Succinct and Lighter. The paper has been accepted by IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) and is scheduled for publication at CHES 2027.