造格

造格解线性方程

  • 当一个多元线性方程有一个比较小的解，那么就有可能可以使用基于格的启发式方法进行求解。这种方法的思路就是，在构造出的某个格中，尝试找到一个特定的最短向量。

  • 我们所考虑的方法依赖于一个尚未被证明的假设，该假设涉及到格中小向量的分布或性质，因此这种方法本质上只是启发式，而非严格保证成功的算法。

  • 举一个简单的例子来说明一下这个通用方法。假设我们希望求解下面的线性方程：其中x,y,z,w∈Zx,y,z,w\in Z都是未知数，并且已知x,z,wx,z,w的值比较小，而yy可以是任意整数。

Ax+By+Cz=wAx+By+Cz=w

  • 注意，此时我们能将这个方程，以及两个平凡方程x=xx=x，y=yy=y，写成一个向量-矩阵方程：u⃗B=v⃗\vec{u}\mathbf{B}=\vec{v}

(x,z,y)[10A01C00B]=(x,z,w)(x,z,y) \begin{bmatrix} 1 & 0 & A\\ 0 & 1 & C\\ 0 & 0 & B \end{bmatrix}=(x,z,w)

  • 在上述矩阵B\mathbf{B}的各行向量是线性无关的，因此可以推出B\mathbf{B}构成了某个格LL的一组基，进一步就有：
    • 则就有u⃗=(x,y,z)∈Z3\vec{u}=(x,y,z)\in \Z^{3}，而目标向量v⃗=(x,y,w)\vec{v}=(x,y,w)。
    • 通过展开向量-矩阵方程就可以很清晰的看到，目标向量是基矩阵的一个整数线性组合。因此，很容易证明目标向量就在这个格上。
    • 当目标向量v⃗\vec{v}和其反向量−v⃗-\vec{v}是该格中唯一的最短向量时，我们只需要通过求解该格的最短向量问题，即可解出原线性方程（对于这样一个小规模的格，这个问题可以高效求解），一旦得到v⃗\vec{v}，就可以解出方程。
    • 进一步就可以利用u⃗B=v⃗\vec{u}\mathbf{B}=\vec{v}中的u⃗\vec{u}，从而恢复出x,y,z,wx,y,z,w的全部数值。

总结：通过上述说明，我们已知知道了造格的要点之一：目标向量必须由基矩阵通过整数线性组合。

  • 通过上面的描述，我们的非常希望目标向量v⃗\vec{v}是格L\mathbf{L}中的一个最短向量。接下来一个非常关键的点就是如何判断、证明或者是严格证明目标向量v⃗\vec{v}是否有可能成为格L\mathbf{L}中的最短向量。

    • 这题提供一个严格证明的方法：
      • 如果要证明某个格中的向量v⃗\vec{v}是最短向量，那一个非常好的证明就是类比证明a≥b,b≥a⇔a=ba≥b,b≥a\Leftrightarrow a=b。
      • 估计出格中的最短向量的上界AA，估计出格中最短向量的下界BB，并证明B≤v⃗≤AB≤\vec{v}≤A，
      • 最后如果能证明的话尽量证明出A=BA=B（可以类比证明集合相等，或者高数的夹逼准则）
    • 但是实际上可能严格证明不了，所以就给出了两个判断最短向量的标准，下面是其中一个：
      • 假设目标向量v⃗\vec{v}可能是格L\mathbf{L}中的最短向量，记上面的基向量a⃗=(1,0,A),b⃗=(0,1,C),c⃗=(0,0,B)\vec{a}=(1,0,A),\vec{b}=(0,1,C),\vec{c}=(0,0,B)
      • 那么目标向量必须比基矩阵中所有的基向量都短，也就是让L=max{x,y,z}L=max\{x,y,z\}。
      • 因此目标向量就满足∣∣v⃗∣∣≤3X||\vec{v}||≤\sqrt{3}X，那么就有X≤∣A∣,∣B∣,∣C∣X≤|A|,|B|,|C|是向量v⃗\vec{v}是最短向量的必要条件。
    • 判断最短向量的第二个标准如下：
      • 如果v⃗\vec{v}是最短向量，那么该向量就必须满足闵科夫斯基界限Minkowski's bound，也就是当格的维数dim(L)=ndim(L)=n，时其最短向量总满足∣∣v⃗∣∣≤nvol(L)13||\vec{v}||≤\sqrt{n}vol(L)^{\frac{1}{3}}，其中vol(L)=∣det(B)∣=∣B∣vol(L)=|det(B)|=|B|，
      • 运用到这里的例子就是∣∣v⃗∣∣≤3vol(L)13||\vec{v}||≤\sqrt{3}vol(L)^{\frac{1}{3}}
      • 再使用第一个判断标准就可以推出：X≤∣B∣13X≤|B|^{\frac{1}{3}}，这个条件就是目标向量v⃗\vec{v}满足闵科夫斯基界限的一个充分条件。
      • 通常情况下，如果目标向量满足闵科夫斯基界限，那么它也会满足第一个判据所给出的界，不过在某些情况下这一点不成立，所以这两个判据应当始终加以检查。
    • 当目标向量满足上面两个判据时，我们就可以确定它有可能是该格中的一个最短向量，在这一阶段，一般来说，我们只能寄希望于它确实是最短向量，并且希望能够通过求解该格的最短向量问题将其恢复出来。特别地，在以这种方式求解线性方程时，我们将依赖下面这个假设：
      • 设矩阵B\mathbf{B}是格L\mathbf{L}的一个基，v⃗∈L\vec{v}\in L。如果向量v⃗\vec{v}比矩阵B⃗\vec{B}中的所有基向量都短，并且满足这个格L\mathbf{L}闵科夫斯基界限，那么±v⃗\pm\vec{v}就是格LL中的最短向量。
      • 当上面的这一假设对某一类格（对应于某个线性方程）成立时，用来判断目标向量是否为最短向量的两个判据所给出的界，就可以作为求解该线性方程组的方法的有效界限。
      • 结合前面给出的例子：假设∣A∣≈∣B∣≈∣C∣|A|\approx |B|\approx|C|，则满足闵科夫斯基界限的向量也会比每一个基向量都要短。如果上述假设对由基矩阵BB生成的格成立，那么我们预期只要满足：X≤∣B∣13X≤|B|^{\frac{1}{3}}，就能就解任何具有相同形式（并且满足相同假设）的线性方程。
    • 在很多情况下，目标向量v⃗\vec{v}的各个分量是不平衡的。当这种情况出现的时候，就要进一步放宽上面判断方法所允许的界限。例如上述例子中，假设X,Z,WX,Z,W是x,z,wx,z,w的界，并且假设X>Z,WX>Z,W，也就是我们认为xx是x,z,wx,z,w中最大的一个。这时候可以从右侧将向量-矩阵方程乘一个对角矩阵，也就是如下：
      • 对角矩阵D=[1000XZ000XW]\mathbf{D}=\begin{bmatrix}1 & 0&0 \\0 & \frac{X}{Z} & 0 \\0 & 0& \frac{X}{W}\end{bmatrix}，右乘该对角矩阵u⃗BD=v⃗D=v′⃗\vec{u}\mathbf{B}\mathbf{D}=\vec{v}\mathbf{D}=\vec{v'}
      • 右乘后的结果：(x,y,z)[10AXW0XZCXW00BXW]=(x,zXZ,wZW)(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})
      • 右乘后就得到新的目标向量v′⃗\vec{v'}，该向量是一个由基矩阵B′\mathbf{B'}所构成的一个新的格L′\mathbf{L'}，那么这个新的目标向量的分量就被平衡了，并且满足∣∣v′⃗∣∣≤(X2+(ZXZ)2+WZW)≤3X||\vec{v'}||≤(X^2+(\frac{ZX}{Z})^{2}+\frac{WZ}{W})≤\sqrt{3}X
      • 还有vol(L′)=∣det(B′)∣=BX2ZWvol(L')=|det(B')|=\frac{BX^{2}}{ZW}，并且基向量的长度也会随之增大，因此未知量取值大小的界可以相应放宽，而目标向量仍然能够同时满足成为最短向量的两个判断依据。只要目标向量的各个分量是不平衡的，这种用于优化界限的方法就可以采用。
      • 在一些使用该技术的攻击描述中，这种优化会直接与初始格的构造过程融合在一起。
    • 同样的思想也可以应用到存在多于一个方程、且这些方程共享部分未知量的情形中。
      • 前面的例子中，假设我们知道x,yx,y还满足方程A′x+C′z+D=0A'x+C'z+D=0，其中DD是比较小的。利用这两个方程，我们可以构造出新的向量-矩阵方程。也就是将基矩阵的中间那一列替换成新方程的参数
      • 构造后的向量-矩阵方程：(x,z,y)[1A′A0C′C00B]=(x,−D,w)(x,z,y)\begin{bmatrix}1 & A' & A\\0 & C' & C\\0 & 0 & B\end{bmatrix}=(x,-D,w)，构造出来后并按照前文所述的方法，继续推导相应的界，使得目标向量有可能成为该格中的一个最短向量。
      • 同样地，如果目标向量的各个分量不平衡，我们可以通过将该方程乘以一个合适的对角矩阵，来构造一个新的格以及对应的目标向量。
      • 由于需要计算格的体积来求出闵科夫斯基界限，那么向量-矩阵方程的构造应当使得矩阵的行列式能方便地计算，通常的做法就是将矩阵构造成三角矩阵。

  • 前面都在说线性方程，现在来看看非线性方程，当已知一个非线性方程存在较小解时，可以对该问题进行线性化处理，从而使用上述方法来尝试求解新的问题例如：

    • 形如这样的方程：Ax+Bx2+Cz2=DAx+Bx^{2}+Cz^{2}=D的方程，
    • 可以通过令x′=x,y′=x2,z′=z2x'=x,y'=x^2,z'=z^{2}，将其线性化为新的方程Ax′+By′+Cz′=DAx'+By'+Cz'=D
    • 注意：其实还存在其他方法可以直接求解非线性方程，并且在某些情况下这些方法能够给出更优解的界限。例如某些情况下的Coppersmith攻击。

造格解模线性方程

  • 上面造格解线性方程这个想法，同样也可以应用到多元模线性方程中：

    • 使用相同的例子，现在我们希望找到同余式的小解：Ax+By+Cz≡w mod( N)Ax+By+Cz\equiv w~mod(~N)，其中NN是一些已知的整数。
    • 可以先将同余式转换为多元线性方程：Ax+By+Cz=w+nNAx+By+Cz=w+nN，其中nn是未知的整数。此时只是构造了一个新的线性方程（定义在整数环上），其中引入了一个新的未知量。因此我们可以直接将前面介绍的方法应用到这个新的方程中。
    • 具体来说可以构造相应的向量-矩阵形式的方程：u⃗B=v⃗\vec{u}\mathbf{B}=\vec{v}

    (x,y,z,−n)[100A010B001C000N]=(x,y,z,w)(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)(x,y,z,w)作为矩阵行生成的格中最短向量来就解。实际上，这里描述的方法可以用来说明一个广为人知的经验性理论(folklore结果)：关于如何寻找模线性方程的小解。

      • 考虑一般的多元模线性方程：a1x1+...+anxn≡0 ( mod N)a_1x_1+...+a_nx_n\equiv 0~(~mod~N)，这里所有的aia_i和NN都是已知的，并且设X1,...,Xn＞0X_1,...,X_n＞0为整数，使得∣x1∣≤X1,∣xn∣≤Xn|x_1|≤X_1,|x_n|≤X_n
      • 这个经验性结论就是：当Πi=1nXi≤N\Pi^{n}_{i=1}X_i≤N，未知量x1,...,xnx_1,...,x_n是可以被解出的。

    • 虽然这个结论多年来一直为人所知并被广泛使用，但对其的理论解释直到2008年由Hermann和May在论文Solvinglinearequations modulo divisors: Onfactoring given any bits.才写出。接下来简述一下他们两个的结果

      • 假设gcd(an,N)=1gcd(a_n,N)=1，在论文中通过将原来的模方程两边同时乘−an−1 mod( N)-a_n^{-1}~mod(~N)，将一般的模方程转换为一个等价的模方程。从而得到b1x1+...+bn−1xn−1≡xn mod( N)b_1x_1+...+b_{n-1}x_{n-1}\equiv x_n~mod(~N)，其中bi=−an−1ai mod( N),i=1,...,nb_i=-a_{n}^{-1}a_i~mod(~N),i=1,...,n
      • 再将新的线性同余方程转换为线性方程：b1n1+...+bn−1xn−1=−xn−nNb_1n_1+...+b_{n-1}x_{n-1}=-x_n-nN，其中nn是整数
      • 根据新的线性方程，可以造出一个向量-矩阵方程

      (x1,...,xn−1,n)[100…0b1010…0b2⋮⋱⋮⋮000…1bn−1000…0N]=(x1,...,xn−1,xn)(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=[NX100…00NX20⋮⋱⋮0NXn−1000…0NXn]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}

      • 此时我们的目标向量就会变成v⃗=(x1NX1,...,xn−1NXn−1,xnNXn)\vec{v}=(\frac{x_1N}{X_1},...,\frac{x_{n-1}N}{X_{n-1}},\frac{x_nN}{X_n})，此时每一个分量的界都是NN。因此就有∣∣v⃗∣∣≤nN||\vec{v}||≤\sqrt{n}N
      • 右乘一个对角矩阵后得到的新格L′L'，其体积为：vol(L′)=NΠi=1nNXi=Nn+1Πi=1n1Xivol(L')=N\Pi^{n}_{i=1}\frac{N}{X_i}=N^{n+1}\Pi^{n}_{i=1}\frac{1}{X_i}
      • 因为该新格是n维格，因此使目标向量满足闵科夫斯基界限的一个充分条件是：nN≤n(Nn+1Πi=1n1Xi)1n\sqrt{n}N≤\sqrt{n}(N^{n+1}\Pi^{n}_{i=1}\frac{1}{X_i})^{\frac{1}{n}}，或者可以更简单的表述为Πi=1nXi≤N\Pi^{n}_{i=1}X_i≤N，这就是我们想要得到的结果。
      • 注意：通过构造可知，目标向量作为最短向量的另一个判据预计也会满足。由于an−1a_n^{-1}很可能与NN大小相当，因此每一个基向量都将大于NN。同时，当XnX_n明显小于NN时，每个基向量的大小也会增大。重新标记系数和变量后，总能选择一个XnX_n，使得所有基向量都大于nN\sqrt{n}N。因此，当Πi=1nXi≤N\Pi^{n}_{i=1}X_i≤N，且之前说的假设对该格成立时，该解应该是可以被找到的。