重放攻击和LWE

Question

只是个小问题。由于在LWE中错误相当小，重播攻击是否有问题？我的意思是，如果我们使用Regev 1的典型方案加密一个向量m，但是这个向量被发送了1000次，那么一个窃听者可以执行一个简单的投票方案来近似原始消息。我失去了什么吗？

参考文献：

1 Regev，Oded.关于格，有错误的学习，随机线性码和密码学。ACM杂志(JACM) 56.6 (2009)：1-40。

Answer 1

通过查看加密程序，您将看到在每次加密时使用向量\vec a_i's的不同和，因此，每个密文都有以下形式

(\vec a, ~\vec a\cdot \vec s + e + \frac{p}{2} \cdot m)

使用不同的术语\vec a \in \mathbb{Z}_p^n和e \in \mathbb{Z}。

请注意，两个密文具有相同的术语\vec a的概率已经在1/p^n (指数级小)附近，而看到具有相同对(\vec a, e)的密文的可能性甚至更小。因此，你的攻击不起作用。

关于

与LWE

的关系

你说你“不想破坏LWE"，但在LWE问题很难的假设下，这个计划是CPA安全的。因此，即使您没有试图直接解决LWE问题，您的攻击也会为我们提供解决LWE问题的算法(因为您的攻击满足CPA安全游戏，因为您只使用加密预言)。这基本上就是本文的引理5.4所指出的：

...如果存在区分0和1加密的多项式时间算法W，则存在一个区分A_{\vec s,\chi} LWE分布和U 均匀分布的区分器Z。