给定一个格子$ L $，向量$ v $和数字$ b = {\ lambda} _1（L ）/ n ^ {17} $，$ a = {\ lambda} _1（L）/ n ^ {13} $决定$ v $与$ L $的距离是否在$ [a / 2，a ] $或最多$ b $，其中$ {\ lambda} _1（L）$是$ L $的最短非零向量的长度
此外，他们指出
将这些参数改进为$ a = b = {\ lambda} _1（L）/ \ sqrt {n} $将使“错误学习”的安全假设之一无效。 （LWE）抵御量子攻击的密码系统。基于加密。这些假设的主要区别在于参数/使用的分布的选择。
我的问题是，是否有人知道所提出的算法打破了其中的多少种或哪类LWE类型的假设？
#1 楼
如评论中所述，该论文存在严重缺陷，已被撤回：请参阅https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ和第（3）部分http://www.scottaaronson.com/blog/?p=2996评论
$ \ begingroup $
感谢@Chris。拥有这个主题的真正专家总是很高兴！
$ \ endgroup $
– Yeehda Lindell
16-11-25在13:48
#2 楼
作者自己指出，这并没有打破加密中使用的基于格的假设。引用：晶格问题近年来受到了极大的关注，这主要是因为其代数结构允许构造密码基元，最终导致“错误学习”（LWE）加密。 Regev [Reg09]提出的方案。我们的算法尚未使LWE抵御量子攻击的安全性假设无效。为此，必须提高算法的性能，以解决$ gapBDD _ {\ gamma_1，\ gamma_2} $为$ \ gamma_1 = \ gamma_2 = \ sqrt {n} $的情况，这等于说要解决$ gapSVP _ {\ tilde O（\ sqrt {n}）} $。我们指出，即使实现这种算法也不会“破坏” LWE本身。要做到这一点-人们将不得不找到一种将gapCVP完整版求解为多项式因子的量子算法。我们认为，这样的任务需要在此处建议的方法中添加新技术：请参阅下一项。
此外：
我们的建议该算法无法解决带间隙CVP的完整版本，并且还需要一个额外的保证，即输入向量至少“有点接近”晶格。我们认为这不是证明的伪像，而是进入方案的核心：至关重要的是，如果考虑相邻晶格点并测试其内积w.r.t.一些向量$ v $，那么这些向量将具有与该向量相似的内积。只有在$ v $“接近”对偶晶格的情况下才会发生这种情况，对偶晶格的极端是$ v \ in NL ^ * $，在这种情况下，这两个内积的定义均为0。因此，我们认为v $将需要一个完全不同的方案。作为这种差异的另一个示例，我们注意到gapCVP的实例（例如gapBDD的实例）还包括两个数字$ a，b $，其中$ b / a = poly（n）$，而我们是
要求区分向量是否在距$ L $的距离内最多a $ a或至少$ b $内。但是，对于gapBDD，知道这两个数字都是$ \ lambda_1 $的相对分数，就会产生一些有关输入晶格的最短向量的长度的隐式信息。加密等方案本身不受影响。此外，作者认为这是一个根本不同的问题。但是，此结果很有可能引起大量研究，以查看是否可以扩展。
=================== =============================
对此进行更新； LWE似乎一切正常！
评论
$ \ begingroup $
我完全同意他们不会违反“标准LWE”。这样我就能弄清楚自己了。但是，例如，独奏攻击可用于以“过度拉伸”的非标准LWE类型假设来破坏某些FHE方案。
$ \ endgroup $
– mephisto
16年11月23日在15:28
$ \ begingroup $
是的，看来这种攻击实际上可能破坏了FHE和多线性映射方案（或至少非常接近）。这可能很快就会发现。
$ \ endgroup $
– Yeehda Lindell
16年11月23日在20:08
#3 楼
除非我误解了定义，否则如果噪声很小，定义1中的问题的算法（即它们的主要结果）实际上足以攻击决策LWE。他们需要一个点始终靠近晶格的承诺这一事实似乎并不成问题。决策LWE问题mod q，其中样本的维度为n，并且每个坐标中的噪声为高斯，且具有标准偏差s，可以转换为以下决策问题：给定一个随机晶格$维度为$ 2n $的L $（其中“随机”是由决策LWE引起的特定分布），给定的目标小于距离$ s \ cdot \ sqrt {2n} $的距离（实际上，那里应该是一个接近于$ 1 $的小常数，乘以前面的上限，但是为了简单起见，我们忽略它），从$ L $开始，或者它在$ \ mathbb {Z} ^ {2n} / L的均匀随机陪集中$。在后一种情况下，到$ L $的距离与覆盖半径成正比-因此距离很远。 （我应该提到，有多种方法可以将决策LWE映射到不同维度的晶格，但为简单起见，让我们继续使用上述映射。）
因此，这是在定义1中使用oracle解决此问题的方法。设置$ b = s \ cdot \ sqrt {2n} $和$ a = b \ cdot n ^ 4 $（他们需要这种关系）在$ a $和$ b $之间）。我们需要做的第一件事是弄清楚如果将随机晶格（与在决策LWE实例中生成的随机晶格）和随机目标相加，则该oracle的输出是什么。请注意，不满足目标接近晶格的承诺，但是算法仍必须输出某些内容。通过向输出的随机目标生成随机目标，我们可以了解输出（或输出的分布）是什么。如果它输出的结果不同于目标距晶格$
这些参数完全超出了当前建议的范围（那些没有被LLL破坏的参数效率极低），但是当然它们可以改善。此外，他们的描述是针对在最坏情况下工作的算法-启发式地，它可能会表现更好。如果这个$ n ^ {17} $达到$ n ^ 5 $，一些合理的事情可能会开始崩溃。如果降至线性，则加密/签名可能会受到影响。
不过，我认为要做的第一件事是等到量子算法的一些专家对本文进行验证。如果他们同意这是正确的，那么事情将会变得有趣。
评论
$ \ begingroup $
我从SPDZ论文（ePrint 2012/642）中找到了一个示例，该论文采用了BGV级别的FHE方案。作为参数集之一，它们在表6中设置$ s = 3.2 $，$ n = 2 ^ {15} $和$ q \ approx 2 ^ {526} $-$ 2 ^ {546} $。 $ \ sqrt {q} / n ^ {16} = 2 ^ {526/2-15 \ cdot 16} = 2 ^ {263-240}> s = 3.2 $这种SPDZ的极端情况将被量子破坏攻击，如果算法正确。
$ \ endgroup $
– xagawa
16 Nov 24在7:44
$ \ begingroup $
虽然这个答案实际上确实回答了我的问题，但我认为将Chris答案标记为当前正确答案很重要，这样读者可以直接看到当前看来该论文有缺陷。仍然感谢您的好回答。
$ \ endgroup $
– mephisto
16-11-25在23:00
评论
从我实验室中进行基于格加密的人员的反应来看，我说基本上“基于LWE的用于加密的假设”均不受此结果的影响-但我自己对此并不了解。 br />所提出的算法似乎存在错误：groups.google.com/forum/#!msg/cryptanalytic-algorithms/…