Paper 2026/2102

Scalable Small ECDLP Solver via Windowed-Batch Inversion for Additively Homomorphic Encryption

Abstract

Decryption in EC-ElGamal and Twisted ElGamal based Additively Homomorphic Encryption (AHE) requires solving a small exponential Elliptic Curve Discrete Logarithm Problem (ECDLP) that recovers a bounded plaintext scalar $m$ from $m \cdot G$. This recovery step is the performance-critical path in various applications, such as electronic voting systems (e-Voting), private federated learning, and privacy-preserving blockchain confidential payment systems including Zether (EC-ElGamal), Solana Token-2022 Confidential Transfers (Twisted ElGamal), and the forthcoming XRPL XLS-96 standard (EC-ElGamal). The state-of-the-art FastECDLP (Tang et al., 2023) employs the baby-step giant-step algorithm (BSGS) to solve ECDLP in $\ell$-bit range by utilizing a baby-step table $T_1'$ of $2^{\ell_1 - 1}$ affine points and achieves fast decryption by precomputing a giant-step table $T_2'$ of all $2^{\ell_2 - 1}$ affine points where $\ell_1 + \ell_2 = \ell$. Even with the signed-range halving of Tang et al., the giant-step table for secp256k1 requires 5.91 GB for a 58-bit search space and exponentially increases to 378 GB for a 64-bit search space. Thus, as noted by Tang et al., a 64-bit range remains impractical on a typical workstation due to the memory requirements. We present three algorithmic contributions that together eliminate $T_2'$ and enable practical 64-bit decryption. (i) A Jacobian coordinate loop advances the giant-step point iteratively in Jacobian coordinates, removing the need to precompute the giant steps in affine coordinates. (ii) Windowed batch inversion batch-inverts a window of a small $W$ accumulated $Z$-coordinates at once, reducing the per-thread working memory required for the giant-step computation from $O(2^{\ell_2})$ (the size of $T_2'$ in FastECDLP) to $O(W)$ regardless of bit size. (iii) Co-Z arithmetic computes two giant steps simultaneously by maintaining a shared $Z$-coordinate, reducing the field multiplication cost per step. We validate our solver on two machines, a laptop-class Apple M1 Pro and a desktop-class Intel Core Ultra 9 285K, with consistent results across both. On the Intel machine, our complete solver outperforms a faithful re-implementation of FastECDLP at 54-bit and 58-bit ($\ell_1 = 31$, up to $2.3\times$ faster) without storing the giant-step table $T_2'$. At 63-bit and 64-bit, Tang et al.'s giant-step table $T_2'$ requires 189 GB and 378 GB respectively, making their approach infeasible on typical desktop or laptop computers. So far, our solver is the only feasible approach, completing full 63-bit and 64-bit decryption in 53 sec and 105 sec, directly overcoming the memory limitation identified by Tang et al. We also discuss two additional arithmetic optimizations, an inversion-chaining scheme and a co-Z Jacobian addition, that reduce the per-step arithmetic cost.