Multivariate Cryptography
Multivariate cryptography builds signatures on the difficulty of solving systems of multivariate quadratic equations — the MQ problem, which is NP-hard. It can produce remarkably small signatures, but a turbulent history of breaks, capped by the 2022 collapse of Rainbow, places it firmly in the higher-risk, niche category. Today it survives only as candidates in the NIST signature onramp.
The MQ Problem
The core hardness assumption is the MQ problem: given a system of quadratic equations in many variables over a finite field, find a solution. In the general case this is NP-hard, and there is no known quantum algorithm that breaks it efficiently. A multivariate scheme hides an easy-to-invert quadratic map behind invertible linear transformations, so the public key is a system that looks random while the private key reveals the trapdoor structure.
Profile: Small Signatures, Large Keys
Multivariate schemes are almost exclusively signature schemes (KEMs from this family have not been practical). Their characteristic profile is:
| Property | Multivariate signatures |
|---|---|
| Signature size | Very small — among the most compact |
| Public key size | Large |
| Verification | Fast |
| Maturity | Niche; several historical breaks |
UOV and Its Variants
The Unbalanced Oil and Vinegar (UOV) family is the most durable multivariate design. It splits variables into "oil" and "vinegar" groups so that fixing the vinegar variables linearizes the system, enabling signing. UOV and its variants were resubmitted in the NIST additional-signatures onramp, where they are still being evaluated. Their appeal is short signatures and fast verification; their drawback is large public keys.
The Rainbow Lesson
Rainbow, a layered UOV variant, was a NIST finalist — and then broken by Ward Beullens in 2022, who recovered private keys for the proposed parameters in a weekend on a laptop. Around the same period, GeMSS was also significantly weakened. These breaks are a defining cautionary tale for the whole field.
Where It Stands
- Not in the core NIST PQC standards (FIPS 203/204/205).
- Third-round candidates — multivariate signature candidates such as UOV, MAYO, QR-UOV, and SNOVA have advanced to the third round of the NIST additional-signatures process; they remain under evaluation and are not yet standardized.
- Recommended posture — monitor, do not depend on. If multivariate diversity is ever needed, it will be a backup, chosen only after the onramp candidates have withstood sustained cryptanalysis.
The strategic value of the family is the same as for any non-lattice approach — diversity — but its historical fragility means it must earn trust before it can carry production load.
Standards & references
- Breaking Rainbow (Beullens, 2022) — the key-recovery attack that broke Rainbow.
- NIST PQC project — including the additional-signatures onramp where UOV candidates compete.
- Resources — full standards register
多变量密码
多变量密码把签名建立在求解多变量二次方程组的困难性之上，即 NP 难的 MQ 问题。它能产生异常小的签名，但攻破事件层出不穷，加之 2022 年 Rainbow 的崩塌，使其牢牢归入高风险小众一类。如今它仅以候选身份存活于 NIST 签名增补征集中。
MQ 问题
核心困难假设是 MQ 问题：给定有限域上一组多变量二次方程，求出一个解。一般情形下这是 NP 难的，且没有已知量子算法能高效攻破。多变量方案把一个易于求逆的二次映射隐藏在可逆线性变换之后，于是公钥呈现为一个看似随机的方程组，而私钥则揭示其中的陷门结构。
特征 签名小 密钥大
多变量方案几乎都是签名方案，该家族至今没有实用的 KEM。其典型特征如下：
| 属性 | 多变量签名 |
|---|---|
| 签名体积 | 极小 属最紧凑之列 |
| 公钥体积 | 大 |
| 验证 | 快 |
| 成熟度 | 小众 历史上多次被攻破 |
UOV 及其变体
不平衡油醋 UOV 家族是最经久不衰的多变量设计。它把变量分为油与醋两组，固定醋变量即可使方程组线性化，从而完成签名。UOV 及其变体已在 NIST 增补签名征集中重新提交，目前仍在评估。其优势在于签名短、验证快，缺点是公钥大。
Rainbow 的教训
Rainbow 是一种分层 UOV 变体，曾入围 NIST 决赛——随后于 2022 年被 Ward Beullens 攻破，他在一台笔记本电脑上用一个周末就恢复出所提议参数下的私钥。大约同一时期，GeMSS 也被显著削弱。这些事件成为整个领域标志性的警示故事。
现状
- 未纳入 NIST 核心 PQC 标准 FIPS 203/204/205。
- 第三轮候选——UOV、MAYO、QR-UOV、SNOVA 等多变量签名候选已进入 NIST 额外签名第三轮，仍处于评估阶段，尚未标准化。
- 建议姿态——保持关注，但不要依赖。若确需多变量这一路多样性，可将其作为备份，且仅在增补候选经受住持续密码分析后才予选用。
该家族的战略价值与其他非格方案一样在于多样性，但其历史上的脆弱意味着，它必须先赢得信任，才能承载生产负载。
标准与参考
- Breaking Rainbow Beullens 2022 — 攻破 Rainbow 的密钥恢复攻击论文。
- NIST PQC 项目 — 含 UOV 候选角逐的签名增补征集。
- 资源链接 — 完整标准登记册