非线性修改器的多变量签名技术解析

# 非线性修改器的多变量签名技术解析 ## 1. 引言 数字签名方案基于非线性多变量方程组已存在许久。多变量密码学虽有性能优势，如短签名、快速验证，但因攻击途径多，一直是有风险的领域。近期密码分析技术发展，使部分多变量方案受攻击，NIST 后量子标准化进程中的多变量候选方案大多受损。本文介绍的 Q 修改器与过往研究的修改器不同，它本质非线性，能创建新映射，且与原映射有隐藏二次关系，可借助原结构完成求逆。 ## 2. 求逆过程与复杂度 ### 2.1 求逆效率 对于函数 F(·, w) 的求逆过程，由于它是三角映射的求逆，效率很高。总共在有限域 Fq 中需要 $m^3 + 2\binom{m + 2}{3}+ m^2(\ell + 1)^2 + m\ell$ 次乘法。 ## 3. 安全分析 ### 3.1 Q 核攻击 在通用使用 Q 修改器时，存在注入映射 $M : F_q^m \to F_q^{m(\ell + 1)}$，使得对于所有 $1 \leq i \leq m$，有 $MP_iM^T = 0_{m \times m}$。同时，由于 F 中不存在 $z_{ik}z_{jk}$ 形式的单项式，也存在注入映射 $M' : F_q^\ell \to F_q^{m(\ell + 1)}$，使得对于所有 $1 \leq i \leq m$，有 $M'P_iM'^T = 0_{\ell \times \ell}$。 这样就会得到两种情况： - 一个包含 $m^3$ 个齐次二次方程的系统，涉及 M 的 $m^2(\ell + 1)$ 个未知系数。 - 一个包含 $m\ell^2$ 个齐次二次方程的系统，涉及 $M'$ 的 $m\ell(\ell + 1)$ 个未知系数。 这些系统可以通过 Gröbner 基方法求解。采用混合方法，即猜测 k 个变量并求解系统，会得到以下两种情况： - 一个包含 $m^3$ 个方程、$m^2(\ell + 1) - k$ 个变量的系统。 - 一个包含 $m\ell^2$ 个方程、$m\ell(\ell + 1) - k$ 个变量的系统。 设 $d_{sr}$ 和 $d'_{sr}$ 分别表示这些系统的半正则度。对于足够大的 q，这些值由以下级数展开式中第一个非正系数的次数给出： $S(t) = \frac{(1 - t^2)^{m^3}}{(1 - t)^{m^2(\ell + 1) - k}}$，$S'(t) = \frac{(1 - t^2)^{m\ell^2}}{(1 - t)^{m\ell(\ell + 1) - k}}$。 假设这些系统是半正则的，攻击复杂度为 $O\left(q^k \binom{m^2(\ell + 1) - k + d_{sr}}{d_{sr}}^\omega\right)$ 或 $O\left(q^k \binom{m\ell(\ell + 1) - k + d'_{sr}}{d'_{sr}}^\omega\right)$。 ### 3.2 直接攻击 直接攻击尝试将公钥直接作为二次函数求逆。通常会使用基于 XL 或 F4 的多项式系统求解器。由于 Q 修改方案的公钥是欠定的，可以采用文献中的约简过程，将公钥转换为一个包含 $m - \ell - 1$ 个方程、$m - \ell - 1$ 个变量的系统。然后采用混合方法，猜测 k 个变量的值。对于包含 $m - \ell - 1$ 个方程、$m - \ell - 1 - k$ 个变量的系统，其半正则度 $d_{sr}$ 是级数 $S(t) = \frac{(1 - t^2)^{m - \ell - 1}}{(1 - t)^{m - \ell - 1 - k}}$ 中第一个非正系数的次数。假设从公钥导出的系统是半正则的，直接攻击的复杂度为 $O\left(q^k \binom{m - \ell - 1 - k + d_{sr}}{d_{sr}}^\omega\right)$。 ### 3.3 秩攻击 STS 密码系统易受各种秩攻击。但 Q 修改由于引入涉及所有变量的项，在域足够大时，通常使所有映射满秩，所以 QSTS 无秩缺陷。C∗ 方案在扩展域 E 上有秩缺陷，但由于添加了 $x_iz_{jk} - x_jz_{ik}$ 和 $z_{ij}z_{rs} - z_{is}z_{rj}$ 形式的抵消项，不存在低秩的 E 组合公二次形式。特别是，不存在线性注入映射 $M : F_q^m \to F_q^{m(\ell + 1)}$，使得 $P \circ M$ 是 C∗ 公钥，所以 QC∗ 对秩攻击安全。 ### 3.4 差分攻击 C∗ 方案及其高次类似方案易受差分攻击。需要验证 Q 变换能否防止此类攻击。满足 E - 代数上差分对称的映射只有 C∗ 单项式映射的分量倍数。所以只有当存在线性注入映射 M 使得 $P \circ M$ 是分量 C∗ 时，攻击才可能。但由于二次替换，不存在这样的注入映射。 ### 3.5 选择消息攻击 在 QC∗ 方案中，为高效求逆需存储线性化方程，导致私钥较大。若实现者选择少量 w 值并仅存储相应线性化方程，会有风险。 - **极端情况：w 为常数**：攻击者收集 O(m) 个签名，发现签名的线性张成是 m 维的。通过对该 m 维空间的基向量矩阵进行行约简，可计算线性嵌入 $\rho : F_q^m \to F_q^{(\ell + 1)m}$。将此映射与公钥复合，可恢复底层方案实例，如 C∗。行约简还能揭示通过输入变换分解后的 w 的常数值。 - **w 有 k 个值（k 较小）**：选择消息攻击最多揭示签名空间的 k 个不同 m 维子空间。基矩阵会揭示通过变换分解后的 w 的不同值。随着 k 趋近于 $q^\ell$，这些 m 维子空间会有非平凡交集。因此，使用更多 w 值可增强方案对选择消息攻击的抗性。而且，QC∗ 和 QSTS 仅提供通用不可伪造性，实际实现不仅需要支持大量 w 值，还需如 SSH 变换的 EUF - CMA 变换。 ## 4. 参数选择与性能 ### 4.1 参数选择 为实现对上述攻击的安全防护，限制攻击是直接攻击。根据安全分析中的复杂度估计，在 $q = 2^8$ 的所有实际参数情况下，经典最优攻击采用混合方法，$k = 3$。使用线性代数指数 $\omega = 2.8$，当 $m = 44$ 且 $\ell = 3$ 时，可实现 151 位安全，达到 NIST 一级安全标准。 ### 4.2 性能比较 为公平比较，在 Magma 计算机代数系统中实现了 QC∗、QSTS 和 UOV 方案的简单概念验证。测量结果表明，Q 修改方案的性能在各变体间非常一致，且优于 UOV 方案的实现。具体性能数据如下表所示： | 方案 | q | m | ℓ | # Eqs | # Vars | sig. (B) | PK (B) | sign (ms) | ver. (ms) | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | Q - schemes | $2^8$ | 44 | 3 | 44 | 176 | 176 | 677600 | 0.6 | 2.9 | | UOV | $2^8$ | N/A | N/A | 44 | 176 | 176 | 677600 | 3.7 | 2.9 | ### 4.3 安全分析流程图 ```mermaid graph TD; A[安全分析] --> B[Q核攻击]; A --> C[直接攻击]; A --> D[秩攻击]; A --> E[差分攻击]; A --> F[选择消息攻击]; B --> B1[构建方程系统]; B --> B2[Gröbner基求解]; B --> B3[复杂度计算]; C --> C1[公钥转换]; C --> C2[猜测变量]; C --> C3[复杂度计算]; D --> D1[判断秩缺陷]; D -- ```