在Kyber，MLWE是如何用于密钥生成的？

Question

我一直在读关于克里斯托·凯伯的文章，我读到在密钥生成过程中，公钥pk是使用秘密密钥s计算的，其方式是将误差e添加到随机矩阵A &秘密密钥s的内积中。

有人说，攻击者试图从公钥中破解密钥需要解决Module-LWE问题，这在计算上是很困难的。

我的问题是MLWE是如何用于生成公钥的&是什么使得它变得如此困难，以至于攻击者无法强行破解秘密密钥s。

Answer 1

在Kyber中，矩阵A具有特殊的结构。具体来说，在Kyber512中，它的形式是

\begin{pmatrix}N_{1,1}&N_{1,2}\\ N_{2,1}&N_{2,2}\end{pmatrix}

在Kyber768中，它的形式

\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}\\ N_{2,1}&N_{2,2}&N_{2,3}\\ N_{3,1}&N_{3,2}&N_{3,3}\end{pmatrix}

在Kyber1024中，它的形式是

\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}&N_{1,4}\\ N_{2,1}&N_{2,2}&N_{2,3}&N_{2,4}\\ N_{3,1}&N_{3,2}&N_{3,3}&N_{3,4}\\ N_{4,1}&N_{4,2}&N_{4,3}&N_{4,4}\end{pmatrix}

其中，每个N_{i,j}都是形式的负反比矩阵。

\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{511}\\ -c_{511} & c_0 & c_1 &\ldots & c_{510}\\ -c_{510} & -c_{511} & c_0 &\ldots & c_{509}\\ \vdots & & &\ddots &\vdots\\ -c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}.

这个矩阵的特殊形式意味着矩阵的乘法。

\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{255}\\ -c_{255} & c_0 & c_1 &\ldots & c_{254}\\ -c_{254} & -c_{255} & c_0 &\ldots & c_{253}\\ \vdots & & &\ddots &\vdots\\ -c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}\begin{pmatrix} \ell_{255}\\ \ell_{254}\\ \vdots\\ \ell_0\end{pmatrix}=\begin{pmatrix} r_{255}\\ r_{254}\\ \vdots\\ r_0\end{pmatrix}.

当乘法执行模(c_0+c_1X+\cdots c_{255}X^{255})(\ell_0+\ell_1X+\cdots+\ell_{255}X^{255})=r_0+r_1X+\cdots+r_{255}X^{255}时，与乘法X^{256}+1是一致的。

这意味着在Kyber512中，A\mathbf s+\mathbf e表达式同样可以被认为代表环\mathbb Z[X]/\langle q, X^{256}+1\rangle上的下列矩阵方程

\begin{pmatrix} n_{1,1}(X) & n_{1,2}(X)\\ n_{2,1}(X) & n_{2,2}(X)\end{pmatrix}\begin{pmatrix}s_1(X)\\ s_2(X)\end{pmatrix}+\begin{pmatrix}e_1(X)\\ e_2(X)\end{pmatrix}

( Kyber768和Kyber1024有类似的表达式)。这是一个带有错误问题的模块学习，有两个样本(分别在Kyber768和Kyber1024的情况下分别为3和4)。我们认为，答案向量的分量在统计上与我们环的一致元素是无法区分的。

要“蛮力”一种解决方案，人们可以尝试s_1(X)和s_2(X)的所有可能值，看看当乘以A时，它们是否产生了接近公钥的答案。在Kyber512中，s_i(X)的系数都来自范围-3,-2,-1,0,1,2,3，这为私钥提供了7^{512}的可能性。打破Kyber512是“只”意味着要像蛮力一样难--强制使用128位的密钥，而这其中有2^{128}的可能性。即使我们在排气方面很聪明，关键空间也比安全要求所允许的要大得多。