格密码入门
造格
造格解线性方程
-
当一个多元线性方程有一个比较小的解，那么就有可能可以使用基于格的启发式方法进行求解。这种方法的思路就是，在构造出的某个格中，尝试找到一个特定的最短向量。
-
我们所考虑的方法依赖于一个尚未被证明的假设，该假设涉及到格中小向量的分布或性质，因此这种方法本质上只是启发式，而非严格保证成功的算法。
-
举一个简单的例子来说明一下这个通用方法。假设我们希望求解下面的线性方程：其中$x,y,z,w\in Z$都是未知数，并且已知$x,z,w$的值比较小，而$y$可以是任意整数。
$$
Ax+By+Cz=w
$$
- 注意，此时我们能将这个方程，以及两个平凡方程$x=x$，$y=y$，写成一个
向量-矩阵方程：$\vec{u}\mathbf{B}=\vec{v}$
$$
(x,z,y)
\begin{bmatrix}
1 & 0 & A\
0 & 1 & C\
0 & 0 & B
\end{bmatrix}=(x,z,w)
$$
- 在上述矩阵$\mathbf{B}$的各行向量是线性无关的，因此可以推出$\mathbf{B}$构成了某个格$L$的一组基，进一步就有：
- 则就有$\vec{u}=(x,y,z)\in \Z^{3}$，而目标向量$\vec{v}=(x,y,w)$。
- 通过展开
向量-矩阵方程就可以很清晰的看到，目标向量是基矩阵的一个整数线性组合。因此，很容易证明目标向量就在这个格上。 - 当目标向量$\vec{v}$和其反向量$-\vec{v}$是该格中唯一的最短向量时，我们只需要通过求解该格的最短向量问题，即可解出原线性方程（对于这样一个小规模的格，这个问题可以高效求解），一旦得到$\vec{v}$，就可以解出方程。
- 进一步就可以利用$\vec{u}\mathbf{B}=\vec{v}$中的$\vec{u}$，从而恢复出$x,y,z,w$的全部数值。
总结：通过上述说明，我们已知知道了造格的要点之一：目标向量必须由基矩阵通过整数线性组合。
-
通过上面的描述，我们的非常希望目标向量$\vec{v}$是格$\mathbf{L}$中的一个最短向量。接下来一个非常关键的点就是如何判断、证明或者是严格证明目标向量$\vec{v}$是否有可能成为格$\mathbf{L}$中的最短向量。
- 这题提供一个严格证明的方法：
- 如果要证明某个格中的向量$\vec{v}$是最短向量，那一个非常好的证明就是类比证明$a≥b,b≥a\Leftrightarrow a=b$。
- 估计出格中的最短向量的上界$A$，估计出格中最短向量的下界$B$，并证明$B≤\vec{v}≤A$，
- 最后如果能证明的话尽量证明出$A=B$（可以类比证明集合相等，或者高数的夹逼准则）
- 但是实际上可能严格证明不了，所以就给出了两个判断最短向量的标准，下面是其中一个：
- 假设目标向量$\vec{v}$可能是格$\mathbf{L}$中的最短向量，记上面的基向量$\vec{a}=(1,0,A),\vec{b}=(0,1,C),\vec{c}=(0,0,B)$
- 那么目标向量必须比基矩阵中所有的基向量都短，也就是让$L=max{x,y,z}$。
- 因此目标向量就满足$||\vec{v}||≤\sqrt{3}X$，那么就有$X≤|A|,|B|,|C|$是向量$\vec{v}$是最短向量的必要条件。
- 判断最短向量的第二个标准如下：
- 如果$\vec{v}$是最短向量，那么该向量就必须满足闵科夫斯基界限
Minkowski's bound，也就是当格的维数$dim(L)=n$，时其最短向量总满足$||\vec{v}||≤\sqrt{n}vol(L)^{\frac{1}{3}}$，其中$vol(L)=|det(B)|=|B|$， - 运用到这里的例子就是$||\vec{v}||≤\sqrt{3}vol(L)^{\frac{1}{3}}$
- 再使用第一个判断标准就可以推出：$X≤|B|^{\frac{1}{3}}$，这个条件就是目标向量$\vec{v}$满足闵科夫斯基界限的一个充分条件。
- 通常情况下，如果目标向量满足闵科夫斯基界限，那么它也会满足第一个判据所给出的界，不过在某些情况下这一点不成立，所以这两个判据应当始终加以检查。
- 如果$\vec{v}$是最短向量，那么该向量就必须满足闵科夫斯基界限
- 当目标向量满足上面两个判据时，我们就可以确定它有可能是该格中的一个最短向量，在这一阶段，一般来说，我们只能寄希望于它确实是最短向量，并且希望能够通过求解该格的最短向量问题将其恢复出来。特别地，在以这种方式求解线性方程时，我们将依赖下面这个假设：
- 设矩阵$\mathbf{B}$是格$\mathbf{L}$的一个基，$\vec{v}\in L$。如果向量$\vec{v}$比矩阵$\vec{B}$中的所有基向量都短，并且满足这个格$\mathbf{L}$闵科夫斯基界限，那么$\pm\vec{v}$就是格$L$中的最短向量。
- 当上面的这一假设对某一类格（对应于某个线性方程）成立时，用来判断目标向量是否为最短向量的两个判据所给出的界，就可以作为求解该线性方程组的方法的有效界限。
- 结合前面给出的例子：假设$|A|\approx |B|\approx|C|$，则满足闵科夫斯基界限的向量也会比每一个基向量都要短。如果上述假设对由基矩阵$B$生成的格成立，那么我们预期只要满足：$X≤|B|^{\frac{1}{3}}$，就能就解任何具有相同形式（并且满足相同假设）的线性方程。
- 在很多情况下，目标向量$\vec{v}$的各个分量是不平衡的。当这种情况出现的时候，就要进一步放宽上面判断方法所允许的界限。例如上述例子中，假设$X,Z,W$是$x,z,w$的界，并且假设$X>Z,W$，也就是我们认为$x$是$x,z,w$中最大的一个。这时候可以从右侧将
向量-矩阵方程乘一个对角矩阵，也就是如下：- 对角矩阵$\mathbf{D}=\begin{bmatrix}1 & 0&0 \0 & \frac{X}{Z} & 0 \0 & 0& \frac{X}{W}\end{bmatrix}$，右乘该对角矩阵$\vec{u}\mathbf{B}\mathbf{D}=\vec{v}\mathbf{D}=\vec{v’}$
- 右乘后的结果：$(x,y,z)\begin{bmatrix}1 & 0&\frac{AX}{W} \0 & \frac{X}{Z} & \frac{CX}{W} \0 & 0& \frac{BX}{W}\end{bmatrix}=(x,z\frac{X}{Z},w\frac{Z}{W})$
- 右乘后就得到新的目标向量$\vec{v’}$，该向量是一个由基矩阵$\mathbf{B’}$所构成的一个新的格$\mathbf{L’}$，那么这个新的目标向量的分量就被平衡了，并且满足$||\vec{v’}||≤(X^2+(\frac{ZX}{Z})^{2}+\frac{WZ}{W})≤\sqrt{3}X$
- 还有$vol(L’)=|det(B’)|=\frac{BX^{2}}{ZW}$，并且基向量的长度也会随之增大，因此未知量取值大小的界可以相应放宽，而目标向量仍然能够同时满足成为最短向量的两个判断依据。只要目标向量的各个分量是不平衡的，这种用于优化界限的方法就可以采用。
- 在一些使用该技术的攻击描述中，这种优化会直接与初始格的构造过程融合在一起。
- 同样的思想也可以应用到存在多于一个方程、且这些方程共享部分未知量的情形中。
- 前面的例子中，假设我们知道$x,y$还满足方程$A’x+C’z+D=0$，其中$D$是比较小的。利用这两个方程，我们可以构造出新的
向量-矩阵方程。也就是将基矩阵的中间那一列替换成新方程的参数 - 构造后的
向量-矩阵方程：$(x,z,y)\begin{bmatrix}1 & A’ & A\0 & C’ & C\0 & 0 & B\end{bmatrix}=(x,-D,w)$，构造出来后并按照前文所述的方法，继续推导相应的界，使得目标向量有可能成为该格中的一个最短向量。 - 同样地，如果目标向量的各个分量不平衡，我们可以通过将该方程乘以一个合适的对角矩阵，来构造一个新的格以及对应的目标向量。
- 由于需要计算格的体积来求出闵科夫斯基界限，那么
向量-矩阵方程的构造应当使得矩阵的行列式能方便地计算，通常的做法就是将矩阵构造成三角矩阵。
- 前面的例子中，假设我们知道$x,y$还满足方程$A’x+C’z+D=0$，其中$D$是比较小的。利用这两个方程，我们可以构造出新的
- 这题提供一个严格证明的方法：
-
前面都在说线性方程，现在来看看非线性方程，当已知一个非线性方程存在较小解时，可以对该问题进行线性化处理，从而使用上述方法来尝试求解新的问题例如：
- 形如这样的方程：$Ax+Bx^{2}+Cz^{2}=D$的方程，
- 可以通过令$x’=x,y’=x^2,z’=z^{2}$，将其线性化为新的方程$Ax’+By’+Cz’=D$
- 注意：其实还存在其他方法可以直接求解非线性方程，并且在某些情况下这些方法能够给出更优解的界限。例如某些情况下的
Coppersmith攻击。
造格解模线性方程
-
上面造格解线性方程这个想法，同样也可以应用到多元模线性方程中：
- 使用相同的例子，现在我们希望找到同余式的小解：$Ax+By+Cz\equiv w~mod(~N)$，其中$N$是一些已知的整数。
- 可以先将同余式转换为多元线性方程：$Ax+By+Cz=w+nN$，其中$n$是未知的整数。此时只是构造了一个新的线性方程（定义在整数环上），其中引入了一个新的未知量。因此我们可以直接将前面介绍的方法应用到这个新的方程中。
- 具体来说可以构造相应的
向量-矩阵形式的方程：$\vec{u}\mathbf{B}=\vec{v}$
$$
(x,y,z,-n)
\begin{bmatrix}
1&0&0&A\
0&1&0&B\
0&0&1&C\
0&0&0&N
\end{bmatrix}=(x,y,z,w)
$$-
构造之后就可以尝试将$(x,y,z,w)$作为矩阵行生成的格中最短向量来就解。实际上，这里描述的方法可以用来说明一个广为人知的经验性理论(folklore结果)：关于如何寻找模线性方程的小解。
- 考虑一般的多元模线性方程：$a_1x_1+…+a_nx_n\equiv 0~(~mod~N)$，这里所有的$a_i$和$N$都是已知的，并且设$X_1,…,X_n＞0$为整数，使得$|x_1|≤X_1,|x_n|≤X_n$
- 这个经验性结论就是：当$\Pi^{n}_{i=1}X_i≤N$，未知量$x_1,…,x_n$是可以被解出的。
-
虽然这个结论多年来一直为人所知并被广泛使用，但对其的理论解释直到
2008年由Hermann和May在论文Solvinglinearequations modulo divisors: Onfactoring given any bits.才写出。接下来简述一下他们两个的结果- 假设$gcd(a_n,N)=1$，在论文中通过将原来的模方程两边同时乘$-a_n^{-1}~mod(~N)$，将一般的模方程转换为一个等价的模方程。从而得到$b_1x_1+…+b_{n-1}x_{n-1}\equiv x_n~mod(~N)$，其中$b_i=-a_{n}^{-1}a_i~mod(~N),i=1,…,n$
- 再将新的线性同余方程转换为线性方程：$b_1n_1+…+b_{n-1}x_{n-1}=-x_n-nN$，其中$n$是整数
- 根据新的线性方程，可以造出一个
向量-矩阵方程
$$
(x_1,…,x_{n-1},n)
\begin{bmatrix}
1&0&0&\dots&0&b_1\
0&1&0&\dots&0&b_2\
\vdots&&\ddots&&\vdots&\vdots\
0&0&0&\dots&1&b_{n-1}\
0&0&0&\dots&0&N
\end{bmatrix}
=(x_1,…,x_{n-1},x_n)
$$- 此时我们将这个
向量-矩阵方程右乘一个对角矩阵
$$
D=
\begin{bmatrix}
\frac{N}{X_1}&0&0&\dots&0\
0&\frac{N}{X_2}&&&0\
\vdots&&\ddots&&\vdots\
0&&&\frac{N}{X_{n-1}}&0\
0&0&\dots&0&\frac{N}{X_n}
\end{bmatrix}
$$- 此时我们的目标向量就会变成$\vec{v}=(\frac{x_1N}{X_1},…,\frac{x_{n-1}N}{X_{n-1}},\frac{x_nN}{X_n})$，此时每一个分量的界都是$N$。因此就有$||\vec{v}||≤\sqrt{n}N$
- 右乘一个对角矩阵后得到的新格$L’$，其体积为：$vol(L’)=N\Pi^{n}{i=1}\frac{N}{X_i}=N^{n+1}\Pi^{n}{i=1}\frac{1}{X_i}$
- 因为该新格是n维格，因此使目标向量满足闵科夫斯基界限的一个充分条件是：$\sqrt{n}N≤\sqrt{n}(N^{n+1}\Pi^{n}{i=1}\frac{1}{X_i})^{\frac{1}{n}}$，或者可以更简单的表述为$\Pi^{n}{i=1}X_i≤N$，这就是我们想要得到的结果。
- 注意：通过构造可知，目标向量作为最短向量的另一个判据预计也会满足。由于$a_n^{-1}$很可能与$N$大小相当，因此每一个基向量都将大于$N$。同时，当$X_n$明显小于$N$时，每个基向量的大小也会增大。重新标记系数和变量后，总能选择一个$X_n$，使得所有基向量都大于$\sqrt{n}N$。因此，当$\Pi^{n}_{i=1}X_i≤N$，且之前说的假设对该格成立时，该解应该是可以被找到的。
wechat