MQDSS 多变量后量子签名算法：从 5 通道识别协议到 NIST PQC 竞赛

概述

MQDSS（Multi-Quad Digital Signature Scheme）是 Ming-Shing Chen、Andreas Hulsing、Joost Rijneveld、Simona Samardjiska、Peter Schwabe 等人于 2016 年提出的多变量密码签名方案，也是 NIST 后量子密码（PQC）标准化项目第二轮候选算法之一。它的核心创新在于：

首次将多变量二次方程（MQ）困难问题直接用于构造存在性不可伪造（EUF-CMA）的数字签名方案，并通过 Fiat-Shamir 变换从 SSH（Sakumoto-Shirai-Hiwatari）5 通道识别协议导出。

本文要点

• 数学基础：MQ 问题、SSH 5 通道识别协议、Fiat-Shamir 变换
• 算法结构：KeyGen / Sign / Vf 完整公式推导
• 参数体系：MQDSS-L1（128 位安全）/ L3（192 位）/ L5（256 位）的具体参数
• 性能特征：72 字节公钥 + 64 字节私钥（极小密钥），但签名 ~40 KB
• 安全分析：Kales-Zaverucha 攻击对参数集的影响
• 国密对照：MQDSS 与国内 SM9 标识签名的异同

数学基础

MQ 问题（Multivariate Quadratic Problem）

MQDSS 的安全性核心是 MQ 问题：

给定有限域 $\mathbb{F}_q$ 上的 $m$ 个 $n$ 元二次多项式 $F = (f_1, \ldots, f_m)$ 和目标值 $y = (y_1, \ldots, y_m) \in \mathbb{F}_q^m$，求 $x \in \mathbb{F}_q^n$ 使得 $F(x) = y$。

SSH 5 通道识别协议

MQDSS 的签名协议基于 SSH（Sakumoto-Shirai-Hiwatari, CRYPTO 2011）的 5 通道识别协议：

通道1: 证明者发送 commitment  C
通道2: 验证者发送挑战      c₁ ∈ {0,...,q-1}
通道3: 证明者发送中间响应  z
通道4: 验证者发送次挑战    c₂ ∈ {0,1}
通道5: 证明者发送最终响应  s
验证:   检查一致性方程

该协议具有 Honest-Verifier Zero-Knowledge (HVZK) 性质，且 Soundness error = 1/q + 1/2（每轮约 $1/31 + 1/2 \approx 0.532$）。通过 $r$ 轮并行重复，总 soundness 降至 $(1/q + 1/2)^r$。

算法结构

1. KeyGen（密钥生成）

输入：安全参数 $\kappa$（目标安全比特数）

输出：私钥 $sk$、公钥 $pk$

步骤：

1. 随机选取种子 $s \in \{0,1\}^\kappa$
2. 使用 PRG（伪随机生成器）从 $s$ 扩展出生成函数：
   - $G_S: \{0,1\}^\kappa \to \mathbb{F}_{31}^{Flen}$  （生成多项式系数）
   - $G_K: \{0,1\}^\kappa \to \mathbb{F}_{31}^n$      （生成私钥向量）
   - $G_C: \{0,1\}^{2\kappa} \to \mathbb{F}_{31}^{r(2n+m)}$  （生成挑战参数）
3. 构建私有二次映射 $F = (f_1, ..., f_m)$，其中每个 $f_i$ 是 $n$ 个变量的稀疏二次多项式：
   $f_i(x) = \sum_{j≤k} a_{i,j,k} x_j x_k + \sum_j b_{i,j} x_j + c_i$
4. 随机选取 $\Delta \in \mathbb{F}_{31}^m$（偏移量）
5. 计算公共二次映射 $G = F + \Delta$（逐分量加法）
6. 私钥 $sk = (s, \Delta, \text{auxiliary data})$
7. 公钥 $pk = (G, \text{parameter description})$

密钥尺寸（MQDSS-L1，$\kappa=128$）：

• 公钥：$G$ 的系数压缩表示 + 描述参数 ≈ 72 字节
• 私钥：种子 $s$ (16 字节) + $\Delta$ (约 48-64 字节) ≈ 64 字节
• 总计：136 字节，远小于 ML-DSA（~2.4 KB 公钥 / ~4.8 KB 私钥）

2. Sign（签名）

输入：消息 $M$、私钥 $sk = (s, \Delta)$

步骤：

1. 计算消息哈希：$h = H(M || \rho)$，其中 $\rho$ 是随机字符串（长度 2κ）
   ← 随机化防止重放攻击
2. 对每轮 i = 1,...,r：
   a. 选取随机掩码 $a_i \in \mathbb{F}_{31}^n$
   b. 选取随机掩码 $b_i \in \mathbb{F}_{31}^m$  
   c. 计算 commitment：$C_i = \text{Com}(a_i, b_i, \rho_i)$
   d. 发送所有 $C_i$ 给验证者（此处用 H1 哈希替代）
   e. 计算挑战：$c_{1,i} = H_1(C_1,...,C_r, M) \mod 31$
   f. 计算中间响应：$z_i = a_i + c_{1,i} \cdot s$  （在 $\mathbb{F}_{31}^n$ 中）
   g. 计算辅助响应：$w_i = b_i + c_{1,i} \cdot \Delta$  （在 $\mathbb{F}_{31}^m$ 中）
   h. 选取随机位：$c_{2,i} = H_2(\text{state}) \in \{0,1\}$
   i. 若 $c_{2,i} = 1$：$s_i = z_i$；否则 $s_i = w_i$
3. 输出签名 $\sigma = (c_{1,1},...,c_{1,r}, c_{2,1},...,c_{2,r}, s_1,...,s_r)$

签名尺寸（MQDSS-L1）：约 40,952 字节（~40 KB）

3. Vf（验签）

输入：消息 $M$、公钥 $pk = G$、签名 $\sigma$

步骤：

1. 解析 $\sigma$ 为 $(c_{1,i}, c_{2,i}, s_i)_{i=1}^{r}$
2. 对每轮 i = 1,...,r：
   a. 根据 $c_{2,i}$ 重新计算 expected commitment
   b. 若 $c_{2,i} = 1$：验证 $G(s_i) \stackrel{?}{=} \text{reconstructed } C_i$
   c. 若 $c_{2,i} = 0$：验证另一组一致性方程
3. 重新计算 challenge：$c'_{1,i} = H_1(\text{all commitments}, M)$
4. 比较：若所有 $c_{1,i} == c'_{1,i}$ 且一致性方程全部通过 → 返回 True

正确性证明：

由于 $G = F + \Delta$，且签名过程保持了线性关系： $$G(s_i) = F(s_i) + \Delta = \text{commitment 的一致性方程}$$

当 $c_{2,i} = 1$ 时验证的是 $F$ 的线性部分；当 $c_{2,i} = 0$ 时验证的是 $\Delta$ 的线性部分。两者缺一不可。

参数体系

MQDSS 定义了三个安全级别（对应 NIST PQC 安全等级）：

MQDSS 官方规范

源码（Public Domain）：https://joostrijneveld.nl/papers/mqdss/

• 密钥生成：~1.8 × 10⁶ 时钟周期
• 签名：~8.5 × 10⁶ 时钟周期
• 验签：~5.8 × 10⁶ 时钟周期

安全性分析

EUF-CMA 安全性证明

MQDSS 的安全性通过以下归约链证明：

EUF-CMA 不可伪造性
    ↓ （Fiat-Shamir 变换，Don-Fehr-Majenz 2018 结果）
HVZK + Soundness 的 5 通道识别协议
    ↓ （SSH 协议的安全性）
MQ 问题（$\mathbb{F}_{31}^n, m$ 个二次方程）的困难性

关键定理（MQDSS 规范 Chapter 10）：

若 SSH 5 通道识别协议在随机预言模型下是 HVZK 且具有 soundness error $\kappa$，则 MQDSS 在 EUF-CMA 模型下是安全的，安全损失为 $O(r \cdot Q_s)$，其中 $Q_s$ 是签名查询次数。

Kales-Zaverucha 攻击（2019）

攻击原理：对 MQDSS 的并行重复结构进行"分阶段攻击"——在第一轮尝试暴力破解部分 commitment，从而减少后续轮次的搜索空间。

影响：

• L1 参数集需要 ~2⁹⁵ 次哈希调用（而非目标的 2¹²⁸）
• 解决方案：将轮数 $r$ 增加约 1.4 倍以补偿攻击优势
• 攻击不破坏 MQDSS 的设计本身，仅说明原始参数集不安全

与 ML-DSA（Dilithium）对比

国密对照

MQDSS 与国密 SM9 标识密码签名（GM/T 0044.2-2016） 有一些有趣的对比点：

• 身份绑定：SM9 的天然优势——用户身份（邮箱、手机号）即公钥，无需证书；MQDSS 仍需传统公钥管理
• 签名尺寸：SM9 的签名比 MQDSS 小约 80 倍，这对物联网设备至关重要
• 量子安全：MQDSS 是后量子安全的，SM9 在量子计算机面前脆弱

• MQDSS 优势场景：密钥管理受限的 IoT 设备、需要最小公钥尺寸的嵌入式系统
• SM9 优势场景：需要身份绑定的 PKI 替代方案、对签名尺寸敏感的应用

已知攻击与防御

总结

MQDSS 代表了后量子签名算法设计的一条独特路线：用大签名换小密钥。其核心价值在于：

• 理论贡献：首个将 MQ 问题直接用于 EUF-CMA 签名的方案，安全性有严格归约证明
• 工程价值：72 字节公钥 + 64 字节私钥，是已知后量子签名方案中最小的密钥尺寸之一
• 历史意义：虽未通过 NIST PQC 竞赛，但其设计思想（Fiat-Shamir + 多轮平行重复）影响了后续的 MAYO、QR-UOV 等算法

参考来源

• MQDSS v2.1 官方规范
• NIST IR 8309: Status Report on Round 2 of PQC Standardization
• MQDSS 主论文 (ASIACRYPT 2016, eprint 2016/708)
• Kales-Zaverucha Forgery Attack on MQDSS
• Sakumoto-Shirai-Hiwatari 5-pass IDS (CRYPTO 2011)
• GM/T 0044.2-2016 SM9 标识密码签名算法

相关实践

• ML-DSA 数字签名算法 — NIST FIPS 204 标准化方案
• SM9 标识密码签名算法（IBS） — 国密 SM9 签名算法
• Hash-Based Signatures — XMSS/LMS/SPHINCS+ 后量子签名家族
• NTRU 格密码系统 — 格密码路线的后量子方案