Scholarlink

<p>Lattice enumeration is a widely used framework for investigating the computational properties of lattices. Its tree-based algorithm (Kannan in: STOC. ACM, New York, pp 193–206, 1983; Fincke and Pohst in J Math Comput 44(170):463–471, 1985) to find vectors which meet specific conditions is a fundamental subroutine in various applications. However, its time complexity is typically super-exponential in the lattice rank, which motivated Schnorr et al. in the 1990s to find a trade-off between the time complexity and the success probability of finding a solution. This effort was revisited by Gama et al. (EUROCRYPT 2010. Lecture notes in computer science. Springer, vol 6110, pp 257–278, 2010) and led to the extreme pruning strategy, which offers exponential speedups. They proposed an efficient algorithm to output a pruning strategy and a predicted cost for any given success probability. In this paper, we present a practical situation in which the actual cost of pruned enumeration is significantly larger than the predicted cost, which precisely happens when the Gaussian heuristic fails: the number of lattice points in some cylinder intersection is much bigger than the ratio between the intersection volume and the lattice co-volume. This phenomenon occurs when pruning parameters are set for a very small success probability. The likely source of this occurrence is the confinement of the searching region to a subspace. To address this, we propose a modification to the cost prediction and an update to the discussion of the cost lower bound (Aono et al. in Advances in Cryptology—CRYPTO 2018. Springer, Cham, pp 608–637, 2018). The revised lower bounds are approximately 20–30 times larger than the previous ones in cryptographically used settings.</p>

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

On tiny-probability lattice enumeration

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月25日

查看全文
  • Yoshinori Aono,
  • Phong Q. Nguyen

摘要

Lattice enumeration is a widely used framework for investigating the computational properties of lattices. Its tree-based algorithm (Kannan in: STOC. ACM, New York, pp 193–206, 1983; Fincke and Pohst in J Math Comput 44(170):463–471, 1985) to find vectors which meet specific conditions is a fundamental subroutine in various applications. However, its time complexity is typically super-exponential in the lattice rank, which motivated Schnorr et al. in the 1990s to find a trade-off between the time complexity and the success probability of finding a solution. This effort was revisited by Gama et al. (EUROCRYPT 2010. Lecture notes in computer science. Springer, vol 6110, pp 257–278, 2010) and led to the extreme pruning strategy, which offers exponential speedups. They proposed an efficient algorithm to output a pruning strategy and a predicted cost for any given success probability. In this paper, we present a practical situation in which the actual cost of pruned enumeration is significantly larger than the predicted cost, which precisely happens when the Gaussian heuristic fails: the number of lattice points in some cylinder intersection is much bigger than the ratio between the intersection volume and the lattice co-volume. This phenomenon occurs when pruning parameters are set for a very small success probability. The likely source of this occurrence is the confinement of the searching region to a subspace. To address this, we propose a modification to the cost prediction and an update to the discussion of the cost lower bound (Aono et al. in Advances in Cryptology—CRYPTO 2018. Springer, Cham, pp 608–637, 2018). The revised lower bounds are approximately 20–30 times larger than the previous ones in cryptographically used settings.