批评greeneggs · 2016-12
“But if you click on v1, you can still access the original paper (incorrect, in this case).”
声称给出量子算法求解一类格上有界距离解码问题(后被撤回)
利用此前引入的格的标准形式 SysNF(基向量满足某种互素条件)对格做“平滑”分析,设计出一个量子算法,声称能高效求解有界距离解码问题的一个变体:给定格 L、向量 v 以及 a、b,判定 v 到 L 的距离是在 [a/2, a] 内还是至多为 b。摘要指出,若能把参数改进到 a = b = λ₁(L)/√n,就会推翻 LWE 密码体制抗量子攻击的一个安全假设。
评论者主要拿它当“声称量子攻破 LWE 的论文后来被撤回”的例子,也提醒点开 v1 仍能看到原来有错误的版本。
先读 Shor 算法,了解量子算法如何解决格相关问题背后的数论问题,再读这篇声称给出格问题量子算法的论文。
量子算法求解隐含周期结构问题的代表,目标论文类似地声称利用量子变换解格问题
读看量子傅里叶变换与周期查找的思路,不必深究数论细节
声称给出格上有界距离解码变体的量子算法(后被撤回)
读看 SysNF 的平滑分析和算法声称的参数范围,同时留意该结论后来被撤回
“But if you click on v1, you can still access the original paper (incorrect, in this case).”
“there was that paper around Thanksgiving last year (which did get retracted) claiming to partially quantum break LWE.”