The advent of quantum computing has intensified concerns about the security of widely deployed cryptographic primitives, including RSA and elliptic curve cryptography. In turn, this has heightened demand for next‑generation cryptographic algorithms capable of withstanding quantum attacks, with lattice‑based cryptography emerging as a leading candidate for both encryption and signature schemes. The security of lattice‑based cryptography is grounded in the Shortest Vector Problem (SVP), whose hardness remains unresolved despite numerous proposed algorithms aimed at assessing or attacking it. Among algorithms for tackling SVP, the Sieve family is characterized by a trade‑off between running time and space complexity. In this paper, we introduce the Ideal Triple Sieve, which combines the space efficiency of the Tuple Minkowski Sieve with the rotational advantages of the Ideal Gauss Sieve. The algorithm is designed for broad applicability and, in particular, achieves superior performance on prime cyclotomic ideal lattices, where it outperforms the Ideal Gauss Sieve. Consequently, it yields Minkowski‑reduced lattice vectors whose quality is substantially higher than that of Gauss‑reduced vectors. At the same time, the Ideal Triple Sieve retains the same asymptotic space complexity as the Ideal Gauss Sieve, \(O(\frac{1}{n}2^{0.1887n+o(n)})\) , and its running time is \(O(n^22^{0.4812n+o(n)})\) . In addition, we develop a set of techniques that exploit structural properties of ideal lattices to further improve the efficiency of the Ideal Triple Sieve. These techniques enable faster evaluation of norms and inner products and eliminate unnecessary reduction steps, thereby markedly reducing execution time. Finally, we present experimental results for our proposal, demonstrating efficiency compared with existing methods.

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

POSTER: An Efficient Sieve Algorithm for Ideal Lattices

  • Yuntao Wang,
  • Kazutaka Toda

摘要

The advent of quantum computing has intensified concerns about the security of widely deployed cryptographic primitives, including RSA and elliptic curve cryptography. In turn, this has heightened demand for next‑generation cryptographic algorithms capable of withstanding quantum attacks, with lattice‑based cryptography emerging as a leading candidate for both encryption and signature schemes. The security of lattice‑based cryptography is grounded in the Shortest Vector Problem (SVP), whose hardness remains unresolved despite numerous proposed algorithms aimed at assessing or attacking it. Among algorithms for tackling SVP, the Sieve family is characterized by a trade‑off between running time and space complexity. In this paper, we introduce the Ideal Triple Sieve, which combines the space efficiency of the Tuple Minkowski Sieve with the rotational advantages of the Ideal Gauss Sieve. The algorithm is designed for broad applicability and, in particular, achieves superior performance on prime cyclotomic ideal lattices, where it outperforms the Ideal Gauss Sieve. Consequently, it yields Minkowski‑reduced lattice vectors whose quality is substantially higher than that of Gauss‑reduced vectors. At the same time, the Ideal Triple Sieve retains the same asymptotic space complexity as the Ideal Gauss Sieve, \(O(\frac{1}{n}2^{0.1887n+o(n)})\) , and its running time is \(O(n^22^{0.4812n+o(n)})\) . In addition, we develop a set of techniques that exploit structural properties of ideal lattices to further improve the efficiency of the Ideal Triple Sieve. These techniques enable faster evaluation of norms and inner products and eliminate unnecessary reduction steps, thereby markedly reducing execution time. Finally, we present experimental results for our proposal, demonstrating efficiency compared with existing methods.