关于陈算法的再更新

Nigel Smart 4月18日更新

Dave Archer 问了我一些与 BGV 式 FHE 相关的问题, 所以我决定要更详细地说明一下。对于 BGV 和噪声方程的描述, 我参考了 Gentry、 Halevi 和我自己相对较旧的论文 (下面称为 GHS 论文)，其中用 BGV 以求值 AES 电路。然而 GHS 只考虑明文模 $p=2$ ，这些公式对其他明文空间的扩展是在 Costache 和我自己的另一篇论文（下面称为 CS 论文）中完成的。

我使用这些论文是因为这些是我最了解的论文，因此使用它们进行快速而粗略的分析会更快。更多的现代论文，具有更精调的噪声方程，将会有类似的分析，因此总体结论应该大致相同。

GHS/CS 和也许更现代的论文之间的主要区别在于, GHS 中密钥是用固定的汉明权重给出的, 而更现代的论文是对密钥进行拒绝采样, 以获得具有低标准范数的密钥。对于这两种方法, 可以假设它们都产生具有相同低标准范数的密钥，只是以不同的方式。

• 标准范数界为我们提供了噪声项标准范数的高概率界, 粗略地说（除了GHS 中称为环常数的，一个从 erfc 函数得到小常数 ）与上面给出的 $\beta$ 值相同。因此,在下文中, 我们将假设标准范数界对应于 $10 \cdot \beta$ , 这相当于 $2^{-80}$ 左右的错误概率。这可以变得更精确, 但同样对整体分析几乎没有改变。

回想一下之前的要点:

• 如果 $\beta$ 很小, 则需要大量 LWE 样本数 $m$ 才能使攻击起作用, 而在 BGV 中, 公钥就有一个非常小的 $\beta$ 值, 即 $\beta=\sqrt{8 \pi}$ 。

• 但回想一下与Vadim Lyubasevksy的讨论。为了生成这些额外的样本, 本身会增加噪声值 $\beta$ 。

在 GHS/CS 论文中, 给出了用于生成新加密的噪声公式, 毕竟了解 BGV 如何运行以给出这些公式至关重要。

公钥加密方法生成的密文的噪声项具有以 $B_{\text {clean }}$ 为界的标准范数。粗略地说, 有

$$ B_{\text {clean }}=O(p \cdot \ell) . $$

但是我们可以进行一次模数切换来得到密文, 密文模数较小 $q$ , 其噪声项的标准范数以 $2 B_{\text {scale }}$ 为界。粗略地说，有

$$ B_{\text {scale }}=O(p \cdot \sqrt{\ell}) . $$

这里大O中隐含的常量是个小整数 (想想 50 或更少)。当进行模数切换时, 可以使用的最小模数大约是 $4 \cdot B_{\text {scale }}$ 的大小。

这将得到如下参数的 BGV 方案

• $\beta \approx 2 \cdot 50 p \sqrt{\ell} / 10=10 p \sqrt{\ell}=O(p \cdot \sqrt{\ell})$

• $q \approx 400 p \sqrt{\ell}=O(p \cdot \sqrt{\ell})$ 即 $\alpha$ 值将是大约 $1 / 40$ 的常量。

回想一下，攻击的复杂性至少为 $O\left(\beta^2\right)$ ，因此我们的复杂性至少为 $O\left(p^2 \cdot \ell\right)$ 。

要点五：具有大明文模数的 BGV（例如在 SPDZ 协议中使用的）似乎不受攻击影响。

4月19日更新

作者连夜发布了论文的更新：

Note:  Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.

注：  4 月 18 日更新：算法第 9 步包含一个错误，我不知道如何修复。有关详细信息，请参阅第 3.5.9 节（第 37 页）。我真诚地感谢Hongxun Wu和Thomas Vidick （独立地）在今天发现了这个错误。现在，一个用于解决具有多项式模噪比的 LWE 的多项式时间量子算法的说法不再成立。我将论文的其余部分保留原样（在步骤 8 中添加了对操作的说明），希望像Complex Gaussian和windowed QFT这样的思想可以在量子计算中找到其他应用，或者以其他方式解决 LWE。

所以格领域里的恐慌似乎结束了。

真的结束了吗？