FastGTDLP: efficient algorithm for small-exponent discrete logarithm problem over group GT

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. Addi