Scholarlink

<p>It is well known that Shor’s algorithm can solve elliptic curve discrete logarithmic problems (ECDLP) in polynomial time on a quantum computer. The optimization of its quantum resources has been a hot issue. In this paper, we optimize quantum resources by utilizing the advantages of Ed25519. By leveraging the special finite field structure of Ed25519 and integer multiplication via the convolution theorem, we achieve significant reductions in quantum resource requirements for modular multiplication: 97% in T-count, 60% in T-depth, and 16% in qubit usage compared with the state-of-the-art result proposed by Häner et al. Then, we have designed reversible point addition operations and incorporated parallelization techniques on Ed25519 to further improve the quantum resources required for solving ECDLP. By incorporating these optimization strategies, we achieve significant improvements across all key metrics: a 75% reduction in T-count, 87% reduction in T-depth, and 12% reduction in qubit requirements compared with the state-of-the-art quantum resources for solving 256-bit ECDLP proposed by Häner et al. Furthermore, in Appendix A, we consider prime fields specified in the ECC standard by NIST; the corresponding modular multiplication demonstrates significant improvements in quantum gate count, circuit depth, and qubit requirements.</p>

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

Improved quantum circuits for elliptic curve discrete logarithm problems on Ed25519

  • 期刊论文

  • 发表日期：

    2025年9月23日

查看全文
  • Yan Huang,
  • Fangguo Zhang,
  • Zhi Hu,
  • Zijian Zhou,
  • Longjiang Qu

摘要

It is well known that Shor’s algorithm can solve elliptic curve discrete logarithmic problems (ECDLP) in polynomial time on a quantum computer. The optimization of its quantum resources has been a hot issue. In this paper, we optimize quantum resources by utilizing the advantages of Ed25519. By leveraging the special finite field structure of Ed25519 and integer multiplication via the convolution theorem, we achieve significant reductions in quantum resource requirements for modular multiplication: 97% in T-count, 60% in T-depth, and 16% in qubit usage compared with the state-of-the-art result proposed by Häner et al. Then, we have designed reversible point addition operations and incorporated parallelization techniques on Ed25519 to further improve the quantum resources required for solving ECDLP. By incorporating these optimization strategies, we achieve significant improvements across all key metrics: a 75% reduction in T-count, 87% reduction in T-depth, and 12% reduction in qubit requirements compared with the state-of-the-art quantum resources for solving 256-bit ECDLP proposed by Häner et al. Furthermore, in Appendix A, we consider prime fields specified in the ECC standard by NIST; the corresponding modular multiplication demonstrates significant improvements in quantum gate count, circuit depth, and qubit requirements.