矩阵A重复的LWE

Question

考虑下面的带有错误的学习版本。

您可以获得(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)或(A, u_1, u_2, \ldots, u_k)，其中

• A是一个m \times n矩阵，它的条目来自于字段\mathbb{Z}_q --条目是随机均匀采样的。
• u_1, u_2, \ldots, u_k是m \times 1，每个条目都是从字段\mathbb{Z}_q随机而来的。
• 每个e_1、e_2、\ldots、e_k都是一个m \times 1高斯噪声矢量。
• 每个s_1, s_2, \ldots, s_k都是一个n \times 1秘密字符串。

你被告知要区分这两种情况。

假设标准LWE很难，这个问题也很难吗？

通常，对每个LWE样本采样一个不同的矩阵A。这里，我们有相同的矩阵A，但k不同的秘密。这对环境有什么改变吗？

Answer 1

您还没有完全说明这个问题，但我假设它是为了区分所构造的集合和\mathbf s_k值。

在LWE的常用公式中，我们给出了对应于不同n-long向量的m样本。它们可以组合成一个m\times n矩阵A，以便“标准”LWE决策问题是将(A,A\mathbf s_1+\mathbf e_1)与(A,\mathbf u_1)区分开来。

如果存在这样的问题，对手可以为\mathbf s_j、\mathbf e_j和\mathbf u_k生成自己的j=2,\ldots k，并通过将两个输入组合到决策LWE和它们自己的输入( \{(A,A\mathbf s_1+\mathbf e_1,A\mathbf s_2+\mathbf e_2,\ldots A\mathbf s_K+\mathbf e_k),(A,\mathbf u_1,\ldots,\mathbf u_k)\}和\{(A,A\mathbf s_1+\mathbf e_1,\mathbf u_2,\ldots,\mathbf u_k),(A,\mathbf u_1,A\mathbf s_2+\mathbf e_2,\ldots,A\mathbf s_K+\mathbf e_k)\} )来创建问题的两个假定实例。如果有一种解决问题的方法，那么在第一种情况下，它应该用\mathbf s_1来区分集合，从而解决原来的决策LWE。有一个问题是，如果给出无效的输入，求解器的行为如何，但是同样，我们应该能够用优势来区分。