FastGTDLP: New algorithm tackles small-exponent discrete logarithms in group GT

Cryptographers in China have unveiled a new algorithm that dramatically accelerates one of the most persistent bottlenecks in modern encryption, slashing decryption times that once stretched to nearly four minutes down to under three seconds. The algorithm, called FastGTDLP, targets a specialized version of the discrete logarithm problem that sits at the heart of homomorphic encryption schemes used in federated learning, blockchain systems, and privacy-preserving computations. According to the research team at Information Engineering University in Zhengzhou, the new method achieves more than sixty times the efficiency of the widely used baby-step giant-step algorithm when plaintexts reach forty bits or longer, and nearly eighty-fold improvements in full decryption pipelines for forty-six-bit messages.

The discrete logarithm problem, or DLP, is one of the classical pillars of public-key cryptography. In schemes built on elliptic curve bilinear pairings, security rests on the assumption that recovering an exponent from a group element is computationally infeasible. Yet the very same mathematical structure creates an awkward paradox for a family of encryption schemes known as additively homomorphic encryption, or AHE. These schemes allow computations to be performed directly on encrypted data, but to achieve their additive property they must encode each plaintext message as a power of a generator inside a particular mathematical arena: the multiplicative cyclic group GT, which is the value domain of the elliptic curve pairing. Decryption then requires solving a discrete logarithm with a small exponent to recover the original message. The difficulty of that recovery grows exponentially with the length of the plaintext in bits, and beyond roughly forty bits the computation time becomes impractically slow. This ceiling has long constrained how much information can be packed into a single encrypted value, inflating both communication overhead and computation cost in large-scale privacy-preserving applications.

The research, published in the journal Cybersecurity, builds on the baby-step giant-step algorithm first proposed by Daniel Shanks in 1971. BSGS trades memory for speed by precomputing a dictionary of powers of the generator and then walking through candidate exponents until a match is found. For general groups and for elliptic curve discrete logarithms, BSGS performs admirably, achieving a time complexity on the order of the square root of the group order. But applying it directly to group GT exposes two crushing weaknesses. First, elements of GT in the SM9 identity-based cryptographic standard used for the team’s experiments live in a twelfth-degree extension of a base finite field, meaning each element comprises twelve components, and a single multiplication inside GT requires 144 base-field multiplications. Because the dictionary lookup actually depends on only partial information from each element, the vast majority of that computation is wasted redundancy. Second, the space demands are enormous: with 32-byte base-field elements, a single GT element spans 384 bytes, and storing the roughly sixteen million precomputed elements needed for a 24-bit baby-step phase would consume roughly six gigabytes before accounting for the typical eightfold redundancy of standard hash-table structures, pushing total requirements near fifty gigabytes, well beyond ordinary computers.

The new work attacks both weaknesses simultaneously through three core innovations. The first is dictionary key compression. Rather than using the complete 384-byte GT element as the dictionary key, the algorithm uses just the lowest 64 bits of a single component, a reduction by a factor of 48. The team analyzed collision probabilities using the birthday paradox, showing that for the parameter choices in question the chance of a problematic key collision during dictionary construction is minuscule, and a final verification step, which checks whether raising the generator to the candidate solution reproduces the target element, guarantees correctness. Because the verification probability approaches one in practice, the extra exponentiation operations it demands are negligible.

The second innovation exploits the internal arithmetic of GT to slash computation. Since dictionary lookups no longer require full elements, the algorithm computes only a single key component during each iteration, skipping the other eleven entirely and reducing the multiplication cost to one twelfth of the naive approach. The researchers provide explicit formulas showing how the highest and lowest components of a product can be derived from pairwise products of the operands’ components, allowing the relevant piece to be extracted without ever assembling the full result.

The third and mathematically most elegant innovation is an expansion of the iteration range, built on a striking property of inversion within GT. When an element of GT is inverted, six of its twelve components remain unchanged, which the authors call symmetric components, while the other six simply flip sign, the antisymmetric components. This means that inversion, normally an expensive operation in finite-field arithmetic, is nearly free over GT. The team leverages this to make each dictionary query cover both a positive and a negative exponent range: for symmetric-component keys, the key of an element and the key of its inverse are identical, so a single stored entry matches exponents in a doubled interval. By additionally computing both the product and the quotient of the running accumulator with each giant-step element, quantities whose component calculations share most of their intermediate work, the algorithm effectively runs on two legs instead of one. Combined with a doubling of the giant-step distance, the coverage per iteration expands fourfold, cutting the number of iterations to one quarter of what BSGS requires with only marginal additional cost per step.

These ideas are packaged into two concrete implementations. FastGTDLP-sym uses the lowest component of the element, which belongs to the symmetric set, as the dictionary key and performs two dictionary queries per iteration, requiring on average slightly more post-match verifications. FastGTDLP-asym uses the highest component, which is antisymmetric, performs four queries per iteration, and needs only a single verification after a match. The choice between them depends on the plaintext length: in the team’s experiments, the asymmetric variant performs best when the giant-step phase involves fourteen bits or fewer, while the symmetric variant takes over for longer ranges. On top of the core algorithm, the authors incorporate cuckoo hashing, a data structure that maps each key to one of several candidate positions using multiple short hash functions, cutting memory redundancy from eightfold to about 1.3-fold. By extracting 32-bit segments of the GT components to serve implicitly as hash indices, the dictionary shrinks from roughly a gigabyte to about 166 megabytes, less than eleven percent of the original footprint. Because each iteration is independent, the workload also parallelizes cleanly across threads, with the authors noting that sixteen threads can divide a 16-bit giant-step phase into chunks of just over a thousand iterations each.

The experimental results are striking. Tested on the SM9 curve parameters using an open-source Python library for Chinese cryptographic algorithms, with each measurement averaged over 500 runs, FastGTDLP begins outperforming BSGS at plaintext lengths of thirty bits, and the advantage widens rapidly as length increases. At forty-six bits, the symmetric variant reaches 78.9 times the efficiency of BSGS and the asymmetric variant 69.6 times. The Pollard Kangaroo algorithm, another classical candidate for small-exponent discrete logs, was measured to be nearly a thousand times slower than BSGS in this setting and was excluded from the comparisons. When the algorithm was embedded into two full identity-based AHE schemes, one published earlier by members of the same team and another based on SM2 and SM9, the effect on end-to-end decryption was transformative: at a plaintext length of forty-six bits, decryption time fell from 222 seconds to 2.82 seconds. The team attributes the improvement to the fact that, at these lengths, discrete logarithm solving dominates the decryption cost almost entirely, so gains in the DLP solver translate directly into gains in the overall scheme.

The practical implications extend across the growing ecosystem of privacy-preserving technologies. Additively homomorphic encryption underpins secure data aggregation in federated learning, where thousands of participants contribute encrypted model updates; auditable confidential transactions in blockchain systems; and privacy-preserving online auctions. In all of these, the usable plaintext length determines how much information each ciphertext can carry, and longer plaintexts mean fewer ciphertexts, less network traffic, and richer computation on encrypted data. By making forty-six-bit plaintexts decryptable in seconds rather than minutes, the new algorithm extends the practical reach of pairing-based AHE by roughly an additional byte per message, which the authors note is a meaningful step toward making such schemes viable in production privacy computing and blockchain deployments. Because the ciphertext expansion and communication costs scale with the gap between plaintext and group size, every bit recovered from the decryption bottleneck improves the information density of the entire pipeline.

Importantly, the authors emphasize that their optimizations, although demonstrated on the SM9 curve, are curve-agnostic in principle. The core techniques, partial-component keys, selective component computation, and inversion-based iteration expansion, can be re-derived for other pairing-friendly elliptic curves by adjusting the extension-field arithmetic to match each curve’s embedding degree and tower structure. The team also outlines an ambitious agenda for future work: deeper exploration of the mathematical properties of GT to widen the per-iteration coverage further, and GPU acceleration and heterogeneous computing to push toward plaintext lengths of sixty-four bits and beyond, a threshold that has remained firmly out of reach for pairing-based homomorphic schemes.

The work also sits within a broader research conversation about the discrete logarithm problem itself. For general elliptic curve groups, no sub-exponential algorithms are known, and generic-group lower bounds confirm that sqrt-order complexity is asymptotically optimal, which is precisely why the new paper’s gains come from exploiting the specific algebraic structure of GT rather than from any generic improvement. Prior efforts had chipped away at the problem from various angles: truncated lookup tables to reduce memory, MapReduce-based distributed collision search in cloud environments, and earlier SM9-based AHE designs that achieved moderate speedups by exploiting algebraic properties of GT without changing the order of magnitude. What distinguishes FastGTDLP is the combination of a fourfold iteration expansion, a twelvefold reduction in per-step computation, and a nearly order-of-magnitude compression of dictionary storage, which together compound into the reported sixty to eighty-fold overall gains. For a problem that has constrained pairing-based homomorphic encryption for over two decades, the result represents one of the largest practical leaps in recent memory, and it arrives just as demand for efficient encrypted computation is surging across industry and academia.