LWE的加解密

Question

对于https://asecuritysite.com/public/lwe_ring.pdf#page=9，有人能解释一下LWE的加密和解密是如何工作的吗？

当我在https://summerschool-croatia.cs.ru.nl/2015/Lattice-based%20crypto.pdf#page=29上做更多的阅读时，有人告诉我，解密时我们得到了q/2 M + r e。如果我们可以通过r e绑定q/4，那么我们就可以通过检查它是否更接近0或q/2来检索M。我可以问一下，r e与q/4的结合有多大帮助？

在类似文档的第33页，关于α的假设的目的是什么？如何推导出这一假设的表达式及其对应的概率？

Answer 1

有人告诉我解密的时候我们得到了qM/2 + r e。如果我们可以通过r e绑定q/4，那么我们就可以通过检查它是否更接近于0或q/2来检索M。我可以问一下，r e与q/4的结合有多大帮助？

在这种情况下，M要么是0，要么是1，我们在解密时实际收到的是一个值d=qM/2+re\mod q。假设例如，q=10,000，那么

• qM/2将为0(对应于M=0)或
• 它将是5000 (对应于M=1)。

如果我们能确定|re|\le 2499那么

• 在M=1的情况下，我们的解密只能在[2501,7499]和
• 在这种情况下，M=0我们只能位于[0,2499]和[7501,9999]的范围内。

这些范围不重叠，因此M的恢复是明确的。

在类似文件的第33页，关于\alpha的假设的目的是什么？如何推导出这一假设的表达式及其对应的概率？

在这些幻灯片中，选择\alpha作为\mathbf e系数采样的离散高斯的标准差。同样，基于独立的硬币翻转，\mathbf r系数被认为是0或1.这意味着\mathbf r\cdot\mathbf e值是近似m/2离散高斯样本的和，每个样本都有标准差\alpha q，因此我们期望该值分布大致为高斯和标准偏差\sqrt{m/2}\alpha q。通过选择\alpha=o(1/\sqrt m\log n)，\mathbf r\cdot\mathbf e的标准差将是o(q/\sqrt{\log n})，因此观察绝对值大于q/4的概率将以观察\sqrt{\log n}/o(1)-standard偏差外的高斯值的概率为界。然后应用高斯分布的标准尾部估计来给出发生这种事件的概率的有界n^{-1/o(1)}。