Scholarlink

<p>In public-key cryptography, the intractability of the discrete logarithm problem (DLP) over the multiplicative cyclic group <i>G</i><sub><i>T</i></sub> 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<i>G</i><sub><i>T</i></sub>DLP, an efficient algorithm for solving small-exponent DLP over <i>G</i><sub><i>T</i></sub>. By using partial bytes of key components of <i>G</i><sub><i>T</i></sub> 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 <i>G</i><sub><i>T</i></sub>, 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 <i>l</i> ≥ 40, Fast<i>G</i><sub><i>T</i></sub>DLP achieves over 60 times the efficiency of BSGS; when <i>l</i> = 46, the decryption time of the AHE schemes is reduced from 222 to 2.82&#xa0;s. This breakthrough extends the plaintext length in AHE schemes, enhancing information density in computation and transmission.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月2日

查看全文
  • Zhenjie Xie,
  • Shengli Liu,
  • Yao Zhang,
  • Youqiang Luo

摘要

In public-key cryptography, the intractability of the discrete logarithm problem (DLP) over the multiplicative cyclic group GT 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 FastGTDLP, an efficient algorithm for solving small-exponent DLP over GT. By using partial bytes of key components of GT 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 GT, 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, FastGTDLP 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.