18 Nov 2026, Wed

New Cryptographic Research Breakthrough Delivers Faster Complete Formulas and Endomorphism Applications for Prime Curves

Cryptographers Diego F. Aranha of Aarhus University and Paulo L. Barreto of the University of Washington Tacoma have released a significant new research paper that breaks a decade-long performance barrier in elliptic curve cryptography. Their paper, designated as Paper 2026/2667 on the Cryptology ePrint Archive and titled "Faster complete formulas and their application to curves with efficient endomorphisms," revisits scalar multiplication on prime curves defined by the equation $y^2 = x^3 + b$ where $p equiv 1 pmod 3$. This prominent family of mathematical curves includes widely used cryptographic standards such as secp256k1, which secures Bitcoin and various blockchain protocols, as well as Barreto-Naehrig (BN) and Barreto-Lynn-Scott (BLS) curves, which are heavily relied upon for pairing-based cryptography, zero-knowledge proofs, and modern cryptographic protocols.

For the first time in ten years, the researchers have successfully improved the efficiency of the best complete addition formulas for these curves. By applying a fifteen-year-old mathematical technique in an entirely novel way, Aranha and Barreto reduced the cost of complete addition from twelve multiplications down to eleven multiplications, or down to ten multiplications when using mixed coordinates. The breakthrough hinges on a clever handling of the final stage of the computation, which is formulated as a three-dimensional cross product that requires only five multiplications.

To demonstrate the practical viability of their theoretical improvements, the authors implemented the new formulas directly within the widely used libsecp256k1 cryptographic library. Their real-world testing showed a notable 5.2 percent performance improvement in constant-time fixed-base scalar multiplication.

Building upon this initial advancement, the researchers went a step further by proposing a complete tripling formula that achieves the exact same operational cost as incomplete tripling in traditional Jacobian coordinates. By combining this new complete tripling formula with their optimized complete addition formula, they constructed an exception-free width-3 $tau$-NAF (non-adjacent form) method that utilizes $tau = 1 – omega$ alongside a six-point precomputed table.

When evaluated within a standard operation-count model, this combined approach proves to be approximately 14 percent faster than exception-free GLV-based scalar multiplication at the 256-bit security level. Furthermore, it outperforms the fastest incomplete GLV methods by three to seven percent, bridging a long-standing performance gap between security-focused complete formulas and speed-focused incomplete formulas.

To validate these operation-count models outside of theoretical projections, the researchers developed constant-time implementations within the RELIC cryptographic toolkit, focusing on the BLS curve families. Within the $mathbbG_1$ group of BLS12-381, BLS24-509, and BLS48-575 curves, the newly introduced $tau$-NAF method demonstrated speed-ups ranging from nine to thirteen percent faster than GLV implementations that rely on standard complete formulas. Additionally, the regular variant of their implementation proved to be ten to twelve percent faster than regular GLV utilizing complete formulas, and five to nine percent faster than regular GLV utilizing traditional incomplete Jacobian formulas.

The performance gains extend to the $mathbbG_2$ group of these same pairing-friendly curves, where the Generalized Lucas Sequence (GLS) method traditionally serves as the primary baseline. In this environment, the $tau$-NAF approach maintained a ten to eleven percent performance advantage over GLS implementations using complete formulas, and remained seven to nine percent faster when compared against Jacobian formulas, while the regular variant secured performance gains of up to six percent.

Beyond scalar multiplication in the primary curve groups, Aranha and Barreto also addressed the arithmetic challenges associated with extension fields. They developed an "imaginary" version of the classic Toom-Cook multiplication algorithm, tailored specifically to optimize extension field arithmetic within the $mathbbG_T$ group. This novel adaptation yields a four to six percent improvement in $mathbbG_T$ exponentiation operations for both the BLS24-509 and BLS48-575 curve families.

By achieving a cyclotomic cube computation at the remarkably low cost of 0.77 multiplications, the researchers successfully extended their $tau$-adic method directly into $mathbbG_T$. This integration drives down the cost of exponentiation even further, making it three percent faster on BLS24-509 and eleven percent faster on BLS48-575. These cumulative optimizations offer cryptographers and software engineers new tools to enhance the efficiency and execution speed of advanced cryptographic primitives without sacrificing the security guarantees provided by complete formulas.

Leave a Reply

Your email address will not be published. Required fields are marked *