具有秘密矩阵的LWE (反向LWE?)

Question

我想知道是否有一个具有秘密矩阵和公共种子向量的LWE版本？它是否会像流行的LWE定义一样困难？

Answer 1

LWE假设告诉您，$(\mathbf{a}，\mathbf{a}\mathbf{s}+e)$对于隐藏的随机向量$\mathbf{s}$、随机向量$\mathbf{a}$和小误差$e$都是随机的。

调用LWE假设k次，得到$(mathbf{a}、\mathbf{a}mathbf{S}_1+e_1、mathbf{a}mathbf{S}_2+e_2、\ldots、\mathbf{mathbf{_k+e_k)$与$(mathbf{a}、b_1、b_2、\ldots、b_k)$ $b_i$‘是随机值。

因此，$(mathbf{a}，\mathbf{mathbf{a}+\mathbf{a}+\mathbf{e})$与$(mathbf{a}，\mathbf{b})$是无法区分的，如果对手在区分这2种分布时具有优势$\varepsilon$，则在区分LWE样本和制服时，有一个具有优势的对手，其中$k$是向量$\mathbf{e}$的维数。