密码学中的多元二次方程（MQ, Multivariate Quadratic Problem）问题与对应的Unbalanced Oil and Vinegar （UOV） 及其变体的攻击思路思考

在考虑要进行逆向的多元二次函数 \(P(x)\) 之前，可以先考虑另外一个特殊的多元二次函数 \(F(x)\) 其中F 拥有和 P 一样的shape. 但是问题是，求解F的逆运算，即试图求解 \(x=F^{-1}(y)\) 并非一个NP hard 问题。

倘若找到了这么一个函数F, 那么只要我们通过一些方式把这个F混淆成一个P的难度，问题也就解决了。 换句话说：

1. 使得私有的人士（即进行签名的人）求解的是F的逆运算。
2. 使得公有的人（即进行验证的人）求解的是P的正运算。
3. 使得试图破解的人（即攻击者，也就是我）求解的是P的逆运算。

如果能够达到三点，尤其是找到一个合适的trapdoor F 使得混淆之后F无法被还原或者找到，一切就ok了。

那么问题来了：怎么构造这个trapdoor, 又怎么进行混淆呢？

先考虑第二个问题，因为简单。

假设

\[\mathbf{P} = \mathbf{T} \circ \mathbf{F} \circ \mathbf{S}\]

其中 S T 是两个仿射变换。 降低求逆问题的难度的思路便是将此处的F改为一个特殊的trapdoor，即很容易逆向运算的特殊二次型。然后再将此处的S和T两个函数构建为普普通通的可逆的线性变换以进行混淆来遮盖住这里的trapdoor, 使得得到的P和寻常的P没有 significant difference, 那么这样一切就非常完美了。这就是所有试图通过MQ来构建密码学协议的算法的做法。

注：这里的 \(\circ\) 就是指的经典矩阵乘法，反映在函数层面就是一个函数的复合操作，即 \(P(x)=T(F(S(x)))\).

好了，现在已经知道 S 和 T 是对输入空间x和输出空间y的仿射变换，即二者都是分别包含一个可逆矩阵乘法矩阵（来旋转）和一个常数向量（来平移）的东西。 现在的核心点回到了：如何去设计这个中间的trapdoor, 即 F 函数。

Before diving into the design of \(F\), we can now summarize the whole procedure again:

公钥就是三个矩阵乘在一起的结果，即这个P函数。

• 私钥就是这个S, F, T 三个子函数。
• 签名的过程就是：对于一条message y, 逆运算T, 然后F, 然后S, 得到signature x 并发布出去。
• 验证的过程就是： 正向运算 P(x) 看是否等于 y.
• 攻击这个密码学系统的思路就是：如何根据P,根据一定量的x y pair, 能够推断出 S F T
• 设计这个密码学系统的关键就是：如何构建这个F函数，使得

首先记 \(y'=F_k(x)=x^TF_k\cdot x\).

我们现在所探究的问题是：如何设计矩阵 \(F_k\in \mathbb{F}_q^{n\times n}\) 使得 当给出 \(m\) 个上述公式之后在已知所有 \(F_K\) 的前提下上述公式可逆求。

为此，UOV设计了一种包含oil和vinegar的思路:

首先，由于输入空间（x的空间）远远大于输出空间，即n>m， 所以UOV在物理意义上将这n维分成两部分，即一个m维表示油（代表很重要，与输出一一对应），还有一个n-m维度，作为醋（代表没那么重要用来打掩护）：由此输入向量x本质上是oil vector \(\mathbf{o}\) 与vinegar向量 \(\mathbf{v}\) 的拼接： \[{\bf x}=[{\bf v};{\bf o}]\].

如此，那么其实二次型矩阵（作为一个对称矩阵，对称是因为交叉项在实数空间表现为矩阵（也就是系数）的对称性）也可以拆解为四个子矩阵： \[\mathbf{F}_k = \begin{bmatrix} \mathbf{V}_k & \mathbf{M}_k \\ \mathbf{M}_k^T & \mathbf{O_k} \end{bmatrix}\]

其中：

• $\mathbf{V}_k ∈ \mathbb{F}_q^{v × v}$：Vinegar 与 Vinegar 相互作用的系数矩阵（\(\boldsymbol{v}^T \mathbf{V}_k \boldsymbol{v}\)）。
• $\mathbf{M}_k ∈ \mathbb{F}_q^{v × m}$：Vinegar 与 Oil 交叉作用的系数矩阵（\(\boldsymbol{v}^T \mathbf{M}_k \boldsymbol{o}\)）。
• $\mathbf{O}_k ∈ \mathbb{F}_q^{m × m}$： Oil 与 Oil 相互作用的系数矩阵（\(\boldsymbol{o}^T \mathbf{O}_k \boldsymbol{o}\)）。

然后UOV设计这里的油与油的作用的系数矩阵，也就是 \({\bf O}_k\) 是一个0矩阵，也就是不存在这个二次项。

这就代表： 对于一个n维向量，里面有m个维度是完全线性的，非二次型的。

这也就代表：对这一部分的向量逆运算就跟一个线性运算的逆运算是一样的，没有丝毫难度。

这就是UOV设计trapdoor的核心思路：维持输出空间大小的 “线性运算” 并隐藏在二次型之中。