• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >On the Closest Vector Problem with a Distance Guarantee
【24h】

On the Closest Vector Problem with a Distance Guarantee

机译：具有距离保证的最近向量问题

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n/sqrt{log n}), improving on the previous best of O(n^{1.5}) due to Lag arias, Lenstra, and Schnorr {hkzbabai}. We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(sqrt{n/log n}) due to Aharonov and Regev {AharonovR04}. To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio {LiuLM06} gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+eps)gamma approximate CVP to gamma approximate CVP where the target is at distance at most 1+1/eps times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun {DadushK13}. As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice {MR04}. We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde{Omega}(sqrt{n}) factor larger.
机译：我们为预处理的近似最接近向量问题（CVPP）的搜索版本提出了一种新的高效算法。我们的算法实现了O（n / sqrt {log n}）的近似因子，由于滞后咏叹调，Lenstra和Schnorr {hkzbabai}而使O（n ^ {1.5}）的先前最佳值得到了改善。我们还出乎意料地证明，只有预处理建议的O（n）个向量才足以解决问题（O（n）的近似系数稍差）。我们注意到，相对于CVPP的决策版本，这仍然有很大的差距，由于Aharonov和Regev {AharonovR04}，其中最著名的近似因子是O（sqrt {n / log n}）。为了获得这些结果，我们展示了减少到仅限于靠近晶格的目标点的相同问题，并更有效地减少了较难的问题，即预处理的有界距离解码（BDDP）。将这两种归约方法与Liu，Lyubashevsky和Micciancio {LiuLM06}的先前最著名的BDDP算法相结合，便得出了主要结果。在不进行预处理的CVP设置中，我们还从（1 + eps）gamma近似CVP减小到gamma近似CVP，其中目标的最大距离是最小距离（最短非视点的长度）的1 + 1 / eps -零向量），它依赖于Dadush和Kun {DadushK13}的晶格稀疏化技术。作为我们的最终也是最大的技术贡献，我们提出了一种更有效的LLM算法变体（在运行时和预处理建议方面均是如此），并通过改进的分析表明，它可以解码远距离成比例的距离。对偶晶格{MR04}的平滑参数的倒数。我们证明了它永远不会小于LLM解码半径，并且可以达到更大的波浪号{Omega}（sqrt {n}）系数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号