Abstract In public-key cryptography, the intractability of the discrete logarithm problem (DLP) over the multiplicative cyclic group G T is a crucial security foundation for elliptic curve bilinear pairings, as well as a bottleneck for the decryption efficiency of additively homomorphic encryption (AHE). Although the traditional baby-step giant-step (BSGS) algorithm is widely used, its high computational redundancy and memory overhead limit improvements in plaintext length and decryption performance. We propose Fast G T DLP, an efficient algorithm for solving small-exponent DLP over G T . By using partial bytes of key components of G T elements as keys and employing cuckoo hashing, the dictionary space is significantly compressed. Additionally, by computing only key components and leveraging the mathematical properties of G T , the computational cost is dramatically reduced. Two versions of the algorithm are provided to adapt to different plaintext lengths. Experimental results show that when the plaintext length l ≥ 40, Fast G T DLP achieves over 60 times the efficiency of BSGS; when l = 46, the decryption time of the AHE schemes is reduced from 222 to 2.82 s. This breakthrough extends the plaintext length in AHE schemes, enhancing information density in computation and transmission.
Xie et al. (Tue,) studied this question.