非平衡油和醋，第一部分

介绍

虽然目前正在进行的 PQC 签名第二次入门中讨论了许多方案，但 Unbalanced Oil and Vinegar (UOV) 既是最有力的竞争者之一，也是一个非常奇特的方案。在这个分为三部分的博客系列中，我们将仔细研究它。

在之前的博客文章中，我研究了如何从大量有效签名中恢复 UOV 公钥。那篇博客文章刻意遗漏了很多关于实际方案的细节，例如为什么它被认为是安全的，或者私钥实际上是如何工作的。

它属于一个更大的多元方案家族，这个家族最出名的是它的大部分成员都被破解了，论文标题从相当枯燥的“油和醋签名方案的密码分析”到非常容易模因的“破解彩虹只需要一台笔记本电脑上的一个周末”。有趣的是，对于一个有这么多被破解方案的领域来说，Unbalanced Oil and Vinegar 到目前为止经受住了时间的考验。在第一部分中，我们将尝试理解为什么底层的难题，多元二次方程，是困难的。

什么解多项式方程

如果你想缩短这篇博文的阅读时间，你可以直接阅读最后一节，关于为什么这个问题是 NP 完全的。它独立于博文的其余部分，而且我认为更容易理解。然而，这样做会错过对求解多项式方程组的意义的一些更深层次的理解。

如果你参加过任何形式的初等教育，你可能已经学过“求解”二次方程的公式，$ax^2 + bx + c = 0$ 是 $\frac{-b\pm\sqrt{b^2-4ac}}{2a}$。事实上，在德国高中，我们称这个公式为“午夜公式”，因为它表示如果你的数学老师在午夜把你叫醒，问你如何解二次方程，你应该毫不犹豫地背诵出来。这种方法被称为“用根式求解”。它通过用域运算和一个特殊函数 $\sqrt[n]{a}$ 来表示多项式的根，从而求解多项式方程，该函数返回 $X^n - a = 0$ 的单个正实数解。

然而，一个问题很快就开始出现，甚至在我们的多项式变成多元之前（即单变量，即只有一个变量）：它不起作用。虽然存在三次和四次单变量多项式方程的公式，其中包含激动人心的历史，涉及大量的戏剧和零知识证明，但是，对于一个同样沉浸在非常不同的戏剧中，但没有零知识证明的历史，不存在五次多项式的公式。就像，可以证明没有办法只使用有理数域上的域运算和根式来求解五次多项式方程。（也没有办法在有限域上这样做，但由于完全不同的原因，有趣的是，这也与同一个伽罗瓦有关）。

如果你退一步看，这并不令人惊讶。毕竟，就像我上面所说的那样，根式所代表的仅仅是假设你已经有一种方法可以解出一个完全不同的多项式方程，然后通过引入像实数（呸）这样定义不明确的概念来使它变得奇怪。

那么我们（作为代数学家）所说的解一个（单变量）多项式方程是什么意思？首先我们需要区分可约多项式和不可约多项式。如果多项式是可约的，那么因式分解会给你新的多项式，并且任何因子的每个解都是原始多项式的解。但是，如果多项式是不可约的，我们只是，有点，什么也不做，只是假设 $x$ 是一个解，并尝试用该解来表达事物。

特别是对于 UOV，我们关心的是 有理解，即本身是基域一部分的解。值得庆幸的是，尽管上面说了这么多，但这些总是定义明确的，即使你没有公式：它们只是我们多项式的线性因子的根。当涉及到寻找有理解时，好消息并没有止步于此：因式分解多项式（在有限域和有理数上，以及在所有其他类型的域上，例如 $\mathbb{Q}_p((\zeta))$)是一个多项式复杂度的问题，因此存在有效的算法来计算任何单变量多项式的因式分解，并通过扩展来找到有理解。如果你是德国高中生，在阅读完本节后，你正式可以回答“这很复杂”，然后翻身，在你的老师在半夜叫醒你时好好休息一晚。

Gröbner 基

到目前为止，我们可以解单变量多项式方程了。但是，正如“多元密码学”这个领域的名字所暗示的那样，我们真正感兴趣的是多元多项式，即具有多个变量的多项式。我们还需要解方程组，即同时求解多个方程。在这里，我们首先遇到了多元多项式的一些非常奇怪的地方，通过观察多元单项式。

虽然单变量单项式，即 $X^n$ 形式的表达式，是一个完全良序的，即所有单项式都通过可除性相互比较，并且存在最小的单项式 (1)，但多元单项式的情况并非如此：我们仍然通过可除性获得一个自然的偏序（例如，$X^3Y^5$ 可被 $X^2Y^3$ 整除，因此大于 $X^2Y^3$)，但并非所有单项式都能再比较（例如，$X^3Y^5$ 既不能被 $X^2Y^6$ 整除，也不能整除 $X^2Y^6$)。这很快就成了一个问题，例如带余数的除法不再是定义明确的。

然而，我们可以通过将现有的偏序（顺便说一句，这是一个格，它与格密码学的格无关，而 ML-KEM 及其同类产品的格是一个阶，它与被称为阶的比较对象无关。数学家 非常 不擅长命名事物。）扩展为全序来解决这个问题。扩展阶的最简单方法是使用词典序，我们首先比较第一个变量的次数，如果相等，则比较第二个变量，依此类推，直到找到不同的次数，然后确定哪个单项式更大（例如，$X^3Y^5$ 大于 $X^2Y^6$，但小于 $X^3Y^6$)。这不是唯一可能的顺序，而且顺序的选择稍后会变得非常重要。

选择了顺序之后，我们现在可以继续重新定义带余数的除法，方法是取除数的首项单项式，检查它是否整除被除数的首项单项式，如果是，则将被除数减去除数的适当倍数。我们可以对整个除数集重复这样做，以得到一个余数，但我们会注意到这些除数的顺序很重要，而且一般来说，我们的带余数除法算法失去了它在单变量情况下拥有的许多好的属性。

输入 Gröbner 基。这些是特殊的多项式集，对于这些多项式集，带余数的除法至少恢复了它们在单变量情况下拥有的部分有用属性。特别是，当使用 Gröbner 基时，余数是所有多项式的环以多项式集生成的理想为模的规范代表。我们为什么要关心这个？事实证明，取模运算与所有多项式同时消失的集合之间存在相当密切的关系，即多元多项式组的解，称为 零点定理。你只需要知道它有多重要，因为我们没有从希尔伯特的原始德语翻译它。这里的细节远远超出了这篇博文（正如你可能已经注意到的，当我开始谈论生成理想等等时，没有警告读者他们需要交换代数才能继续进行的话），并且谢天谢地，对于理解基础知识来说不是必需的。

然而，对于我们这些特别对有理解感兴趣的人来说，更深入地研究一下词典序的 Gröbner 基是什么样子是很有价值的：

给定一个多项式方程组（维数为 0，不用担心，虽然这是一个技术问题），关于词典序的 Gröbner 基是一组等价的多项式方程（即，一个的每个解都是另一个的解），它特别具有 $(f_1, f_2, \dots, f_n)$ 的形式，$f_n$ 是 $Xm$ 中的单变量，$f{n-1}$ 是 $Xm, X{m-1}$ 中的二元，等等。

特别是，给定这样一个 Gröbner 基，我们可以通过求解最后一个多项式（它是单变量的）来找到有理解，取每个零点，部分地评估倒数第二个多项式以获得另一个单变量多项式，求解它，依此类推。请注意，这个算法本身可能已经是指数级的：没有任何东西能保证我们在分解了大量的单变量多项式后，任何给定的零点最终都会得到一个有效的解，但实际上这通常不是问题。

寻找 Gröbner 基

然而，真正的问题是 找到 首先要找到的 Gröbner 基。事实上，这个问题非常复杂和有趣，我决定写一篇完整的博文来讨论它，以防你没有注意到到目前为止我还没有真正谈论 UOV，并且直到第二部分才会真正提及该方案，除了作为所有这些的驱动因素。

因此，让我们最终看一下查找 Gröbner 基的算法，Buchbergers 算法（这个算法有一些小的改进，称为 F4 和 F5，但它们并没有彻底改变事情）。该算法非常简单，可以在这里完整地写出来：

buchberger(多项式集 S) ->
多项式列表 S'
  对于 S 中的每一对 (p1, p2)：
    设 m1 为 p1 的首项单项式
    设 m2 为 p2 的首项单项式
    设 m 为 m1 和 m2 的最小公倍数
    计算 p = m/m1 p1 - m/m2 p2
    用商和余数将 p 约化为 S
    如果 p != 0，则将 p 添加到 S
  用 S 约化 S 的每个元素而不使用它
  如果循环没有添加任何新的多项式，则返回 S

这个算法太棒了！请注意，按照它的编写方式，甚至不清楚它是否会终止，更不用说它有什么复杂度了。“最简单”的论证我知道为什么它会终止，是这样的：如果我们看一下由 S 的首项单项式生成的理想，那么我们在每次循环迭代中添加的元素 p，要么会有一个新的首项单项式（否则它会被约化），这个首项单项式还不是这个理想的一部分，要么它会约化为 0 并且不会被添加。因此，对于每次循环迭代，这个首项单项式的理想会严格增长。但是多项式环是 Noetherian 的，因此，每个严格升高的理想链最终都会终止。在那时，该算法返回。虽然这证明了 Buchberger 算法总是会终止，但它通过调用交换代数最奇怪的属性之一来实现这一点，并且它没有给出可以用来确定运行时复杂度的建设性证明。人们可以通过更仔细地处理来计算运行时复杂度，并且计算出了像 $O(d^{2^n})$ 这样的奇妙的术语，它表示最终基中多项式的次数，所以是的，这可能需要一段时间，甚至仅仅写下基也不是一件容易的事。事实上，在实践中，在时间复杂度变得相关之前，正是 Buchberger 算法的空间复杂度摧毁了获得解的所有希望。

然而，代数几何学家如此渴望 Gröbner 基，以至于他们会继续为他们当前的宠物问题运行该算法，而不仅仅是基于希望。事实证明，希望并非总是错位的。我之前提到过单项式序，事实证明 Gröbner 基的计算非常敏感地取决于人们选择的单项式序。在一个顺序中会耗尽内存的问题可能会在另一个顺序中在几秒钟内完成。你还可以改变你用哪个集合何时约化哪个多项式，并提出各种有趣的分布式计算问题，这些问题将极大地影响该算法的运行时。很好的是，一旦你有了一个 Gröbner 基，你也可以非常有效地计算其他 Gröbner 基，所以没有什么能阻止我们首先在更有效的分级词典序中计算 Gröbner 基，然后廉价地切换到所需的词典序。

这是多元密码学的最大弱点。在格密码学具有从最坏情况到平均情况的良好约化的情况下，多元密码学具有非常困难的最坏情况问题，但是一个非常难以控制的平均情况。事实上，它非常挑剔，以至于作者通常只会说明他们在尝试找到 Gröbner 基时花费了多少 RAM，因为没有更好的方法来估计运行时。

多元二次方程求解是 NP 完全的

现在到本博客文章的最后一节，也是承诺的独立章节，展示了求解多元二次方程是 NP 完全的。我们通过将问题简化为 SAT，布尔可满足性来做到这一点。为了简洁起见，我们仅对 $\mathbb{F}_2$ 上的多元多项式，即具有 2 个元素的域，进行此操作，但是显示它适用于所有其他域并没有实质性的不同。

我们这样做，是通过观察一个特定的多元多项式：$f(X, Y) = XY + 1$。

由于我们的域只有两个元素，我们可以快速检查 $f$ 的评估结果：$f(0, 0) = 1, f(0, 1) = 1, f(1, 0) = 1, f(1, 1) = 0$。换句话说，如果我们将 0 与 false 相关联，将 1 与 true 相关联，则 f 等于 NAND。众所周知，每个布尔电路都可以仅使用 NAND 门来表示，而连接门与链接函数调用是相同的，而函数调用又与替换多项式相同。这意味着每个布尔表达式都等于一个多元多项式，其度数受电路深度的指数限制。为了回到二次多项式系统，我们现在为每个度数高于平方的变量 X 引入一个新的辅助变量 Y，方法是将多项式 $X^2 - Y$ 添加到我们的多项式系统中。这使我们可以再次将多项式的次数减半，并且一起采用，我们得到了一个多项式有界的二次方程组（如果我们同时执行这两个步骤，我们就永远不会以非法的方式爆炸多项式的次数）。这会将 SAT 简化为 MVQ。另一方面，给定一个可能的解，只需通过评估二次多项式即可简单地完成验证，该操作本身是时间上的多项式，因此 MVQ 属于 NP，使其成为 NP 完全的。

但请记住，这仅适用于通用的多元二次方程组，并且不能证明我们将在下一部分中讨论的 UOV 甚至是hard的最坏情况，更不用说它对平均情况复杂性做出的陈述了。

• 标签 密码学

• 原文链接： keymaterial.net/2024/12/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～