警告：及其不可靠的密码学文章，可能很愚蠢，写到哪算哪

应用密码学（也许是整个计算机科学）中最困难的一件事就是解释为什么我们所使用的工具是正确的。我们从前人那里获得了一个珍贵的篮子，里面装满了有用的算法。对那些实践主义者来说，直接拿这些算法来用也是很合理的。但有的时候，这种做法让我们好奇为什么这些算法要这么做。我们此时不如仔细想想这些算法到底在干什么，以及在发明者想出这些算法的时候，他们脑子里又是怎么思考的。

在这一篇文章中我想聊聊签名算法，具体来说是Schnorr签名，以及一些相关的算法，比如ECDSA（椭圆曲线数字签名算法）。这些签名算法有不少有趣的性质，使得他们在密码学构造中比较特殊。了解Schnorr签名的本质也有助于理解一系列最近的工作，包括像Dilithium这样的抗量子协议——我们会在下一篇文章中讨论这个协议。

这条推特给了我写这篇文章的动机：

比起直接把Schnorr签名丢给你，我打算用一些更弯弯绕绕的方法来介绍。我们从最基本的组成部分开始（包括一个身份识别方案的基本概念），然后一点点搭建Schnorr签名的框架。

身份识别方案：最有用的砖头

如果你想理解Schnorr签名，你首先得了解的是它们根本不是真正为签名设计的，至少一开始不是。Schnorr协议最初被设计为一种交互式识别方案，可以“扁平化”为我们熟悉和喜爱的签名方案。

一个身份识别方案由用于生成包含公钥和私钥的“密钥对”的密钥生成算法以及使用这些密钥的交互协议（“识别协议”）组成。公钥代表其所有者的身份，可以分发给任何人。私钥则自然是秘密的。我们假设它是由其所有者存储的，之后所有者可以使用它来证明它“拥有”公钥。

识别协议本身在两方之间交互运行——这意味着双方将交换多个消息。我们经常将这些参与方称为“证明者”（Prover）和“验证者”（Verifier），许多旧论文曾经给他们起了可爱的名字，例如“Peggy”和“Victor”。我觉得这有点矫情，但在这次讨论中我会沿用，因为我起不出更好的名字。（译者注：这就像传统密码协议演示中的Alice和Bob，只不过那里是A和B，这里是P和V）

要开始识别协议，Victor必须获得Peggy公钥的副本。Peggy拥有她的私钥。该协议的目标是让Victor决定他是否信任Peggy：

请注意，这种“所有权证明”不需要100%完美。我们只要求它以极高的概率是正确的。粗略地说，我们要确保如果Peggy真的拥有钥匙，那么Victor将永远相信这一事实。与此同时，冒充Peggy的人——即不知道她的私钥——应该无法说服Victor，这件事发生的概率应该非常小（可以忽略不计的）。

（为什么我们允许冒充者以这种微小概率成功？事实证明，这对于任何识别协议来说基本上都是不可避免的。这是因为Peggy发送给Victor的消息大小必须是有限的，显然至少必须存在一个会让Victor接受的“成功”响应（真实的Peggy给出的消息）。因此，总会有这么一个坏人，他瞎猜一个字符串，还真猜中了。只要Peggy发送的位数相当大，那么这样一个“愚蠢”的坏人就应该几乎永远不会成功，但这个概率永远不是零。）

上面的描述几乎足以解释识别方案的安全目标，但还不够完整。如果是的话，那么就会有一个非常简单（但显然很糟糕）的协议来解决这个问题：证明者可以简单地将其私钥传输给验证者，验证者可以测试它是否与公钥匹配：

如果我们只关心在一个只有一个验证者且只需要运行协议一次的世界中证明所有权的基本问题，那么上面的协议就可以正常工作！不幸的是，在现实世界中，我们经常需要向多个不同的验证者证明身份，或者反复说服同一个验证者。上述稻草人提案的问题在于，在一次执行结束时，Victor已经知道了Peggy的私钥（就像任何其他碰巧窃听了他们通信的人一样）。这意味着Victor或任何窃听者现在都能够在以后的互动中冒充Peggy。

对于识别协议来说，这相当坏。为了解决这个问题，一个真正有用的身份识别协议应该至少添加一个额外的安全要求：在完成这个协议后，Victor（或窃听者）不应该获得向另一个验证者模仿Peggy身份的能力。上述协议显然不符合这一要求，因为Victor现在将拥有Peggy曾经拥有的所有秘密信息。

这一要求也有助于解释为什么识别协议（必然）是交互式的，或者至少是有状态的：即使Victor没有收到Peggy的密钥，他仍然可以记录Peggy在与他执行协议期间发送的任何消息。如果协议是完全非交互式的（也就是说，它只包含从Peggy到Victor的一条消息），那么Victor稍后可以向其他验证者“重播”他录制的消息，从而让那个人相信他实际上是Peggy。许多协议都遇到了这个问题，包括一些老旧的车钥匙。

这一问题的经典解决方案是将设计一种由多个交互动作组成的挑战-响应结构识别协议。在这种方法中，Victor首先向Peggy发送一些随机的“挑战”消息，然后Peggy对应地生成她的响应。如果恶意的Victor试图向不同的验证者冒充Peggy，比如说Veronica，则Veronica很可能发送不同的挑战值，因此Victor将无法使用Peggy的原始响应来回应Veronica的新挑战。

（虽然通常需要交互，但在某些情况下，我们似乎可以通过“从环境中提取挑战”来“绕过”这一要求。例如，现实世界的协议有时会将识别协议“绑定”到时间戳、交易详细信息或验证者的姓名等元数据。这并不能严格防止重播攻击——单消息协议的重播总是可能的！——但它可以帮助验证者检测并拒绝此类重播。例如，Veronica可能不会接受过时的消息。我更愿意这么说，广义上来看，这些协议仍然是交互式的。只是交互的第一步[例如，查询时钟的时间戳]现在被移到了协议之外。）

我们如何构造身份识别方案？

现在我们认识了识别方案，显而易见的问题是如何构建一个识别方案。

可能最简单的想法是使用某种单向函数作为地基。这些函数的关键特征是它们在一个方向上计算起来“容易”（例如，对于某些字符串 x ，可以非常有效地计算函数 F(x) 。）同时，单向函数很难求逆：这意味着给定某个随机输入字符串 x 的 F(x) —让我们假设 $x$ 是128位字符串—应该需要大量的计算工作才能恢复 x。

选择单向函数是因为我们有很多可用的单项函数构造，包括密码学哈希函数以及更奇特的数论构造。理论密码学家也更偏爱这一假设，因为此类函数的存在被认为是我们拥有的最“合理”的密码假设之一，这意味着它们比更奇特的假设更有可能存在。（译者注：我们现在对于单项函数“存在”以及对其的构造是基于假设的，即“我们猜测它是对的”。大部分密码学协议都基于这样或那样的假设，在此之中单向函数是人们认为“比较可能是真的”的那一种。）

问题在于，从简单的单向函数构建识别协议并不容易。一个比较容易想到的起点是Peggy通过选择随机字符串 sk （例如，128位随机字符串）来构建她的秘密密钥，然后将她的公钥计算为 pk=F(sk)。

现在要进行身份识别协议，Peggy会……嗯……好吧，目前还不清楚她会做什么。

“显而易见”的答案是Peggy将她的秘密密钥 sk 发送给Victor，然后Victor可以检查 pk=F(sk)。但由于之前提到的原因，这是坏的：只要Peggy与他进行了一次协议，Victor就可以冒充Peggy。解决这个问题可不简单。

当然，有一些聪明的解决方案，但每种解决方案都有一些限制和成本。“民间传说”[1]方法的运作方式如下：

1. Peggy没有选择一个秘密字符串，而是选择了N个不同的秘密字符串 sk1,…,sk_N 作为她的“秘密密钥”。

2. 她现在将她的“公钥”设置 为 pk=F(sk1),…,F(sk_N)。

3. 在识别协议中，Victor将向Peggy提出挑战，要求她提供Peggy字符串一个大小为 k 的子集（这里 k 比 N 小得多。）

4. Peggy将发回适当的 k 个秘密字符串列表。

5. Victor将根据Peggy公钥中的适当位置检查每个字符串。

这里的想法是，在运行该协议一次后，Victor知道了Peggy的一些但不是全部秘密字符串。如果Victor然后尝试向另一个人（例如维罗妮卡）冒充Peggy，那么维罗妮卡会选择她自己的大小为 k 的子集供Victor做出响应。如果这个子集与Victor在与Peggy互动时选择的子集相同，那么Victor就会成功：否则，Victor将无法回答维罗妮卡的挑战。通过仔细选择 N 和 k 的值，我们可以确保这种概率非常小。[2]

该提案的一个明显问题是，如果Victor能够说服Peggy与他一起多次运行该协议，它很快就会崩溃。

如果Victor可以向Peggy发送几个不同的挑战，他将了解到超过 k 个Peggy的秘密字符串。随着Victor学习的字符串数量的增加，Victor回答维罗妮卡询问的能力将显著提高：最终他几乎可以一直模仿Peggy。有一些聪明的方法可以解决这个问题，同时仍然使用简单的单向函数，但它们在带宽和计算方面往往相对“高级”并且成本高昂。（我保证会在其他文章中讨论它们。）

Schnorr

到目前为止，我们有一个动机：我们希望构建一个多用途的识别协议——从某种意义上说，Peggy可以与Victor（或其他验证者）多次运行该协议，而不会失去安全性。同时，这种方法也是高效的,Peggy不必与Victor交换大量数据或拥有大量公钥。

现在已经出现了大量的身份识别协议。Schnorr的协议甚至也不是完全原创的。“Schnorr”只恰好是我们通常用于满足这一特定要求的一类高效协议的名称。

当Twitter还不叫X的时候，我问是否有人可以用两条或更少的推文描述Schnorr协议的基本原理。我承认我正在寻找一个特定的答案，我从Chris Peikert那里得到了它：

我真的很喜欢Chris对Schnorr协议的解释，我已经迫不及待想把这个解释进一步展开了。我保证你只需要一点中学代数和一个“魔盒”就能理解它。我们稍后会揭开这个魔盒的秘密。

让我们一步一步地解开这个谜语。

首先，Chris建议Peggy必须选择“一条随机直线”。回想一下小学代数，直线的方程是 y=mx+b，其中 “m” 是直线的斜率，“b” 是其y轴截距。因此，Chris实际上要求我们选择一对随机数 (m,b)。（你可以假装这些是某个范围内的实数。但是我们会把它当做一个非常大的有限域中的元素，这将解决许多问题。）

这里我们让 “m” 作为Peggy的密钥，她会选择一次并永远保持不变。Peggy每次运行协议时都会选择一个新的随机值 “b” 。至关重要的是，Peggy会将这两个数字放入Chris的一对魔盒中，然后将它们发送给Victor。

最后，Victor的挑战是让Peggy在他选择的一个特定（随机）点 x 处计算对应的 y。这对于Peggy来说很容易，她可以使用她的线性方程计算相应的值y。现在Victor拥有一个点 (x,y)，如果Peggy回答正确的话，该点应该位于 (m,b) 定义的直线上。他只需要使用“魔盒”来验证这一事实即可。

这是整个协议：

显然这不是一个真正的协议，因为它需要魔法才能运行。话虽如此，它仍然有一些不错的功能。

关于该协议，我们可以观察到的第一件事是，如果最终检查通过了，那么Victor应该有理由相信他真的在与Peggy交谈。我在此给出一个直观的（非正式的！）论证。我们注意到，要完成协议，Peggy必须回答Victor选择的任何随机x的查询。如果Peggy或冒充Peggy的人能够以高概率对Victor可能选择的任何随机点x执行此操作，那么直观上她可以（至少在她自己的头脑中）为第二个随机点x'计算类似的响应。给定两个在同一条线上的点 (x,y)、(x′,y′)，很容易计算秘密斜率 m 。因此，能够轻松计算线上点的人几乎肯定知道Peggy的密钥。（这不是证明！这只是一种直觉。但真正的证明使用了类似的原理。[3]）（译者注：这里原为脚注2，疑为原作者笔误）

那么现在，问题回到了Victor在与Peggy运行协议后了解到了什么。

如果我们忽略协议里的魔法盒子，Victor在协议结束时“学习”的唯一东西就是碰巧位于Peggy选择的随机线上的单个点 (x,y) 。幸运的是，这并没有透露太多关于这条线的信息，特别是，它并没有透露太多关于她的私钥（斜率）的信息。原因是，对于Peggy可能选择作为关键的每个可能的斜率值m，都存在一个值b，该值生成一条与 (x,y) 相交的线。我们可以用几个不同的例子来形象地说明这一点：

如果Victor看到同一条线上两个不同的点，协议就会出问题。幸运的是，这种情况永远不会发生，因为Peggy每次运行协议时都会选择不同的线（通过选择新的b值）。（如果她忘记这样做，那将是一场可怕的灾难！）

这些魔盒的存在显然让安全性变得有些微妙，因为现在Victor可以使用“魔盒”进行各种测试，测试 m、b 的不同值，看看是否能找到匹配的线。但幸运的是，这些盒子是“魔法”的，从某种意义上说，Victor真正能做的就是测试一个点是否在线上：由于m有许多可能的值，这意味着暴力穷举将花费太长时间，不太现实。

现在，你可能会问：为什么要一条线？为什么不是一个平面，或者一个8次多项式？

答案非常简单：直线恰好是满足我们需求的最简单的数学结构之一。我们需要一个方程，我们可以“安全”地揭示一个解，而无需完全给出方程的项。高阶多项式和平面方程也具有这种功能（实际上我们可以揭示这些结构中的更多点），但每个方程都有一个更大、更复杂的方程，需要更魔法的“魔盒”。

我们如何知道“魔盒”是否足够魔法？

通常当人们学习Schnorr时，他们不会学习有关魔盒的知识。事实上，他们通常会看到一堆关于循环群的无聊细节。

这种方法的问题在于，它没有告诉我们，我们到底需要这个魔盒满足什么性质。这带来了不少问题，因为我们并不是只有一个特定的盒子可以用来实现此类协议。事实上，最好将该协议视为一个类似于程序设计中泛型的概念，可以用不同的“魔盒”来实例化。

因此：我将尝试一种不同的方法。我不会提供给你一个能被当做魔盒使用的妙妙工具，而是尝试找出我们的魔盒必须具有哪些属性。（译者注：提供一个接口（interface, trait）而非实例（concrete type））

模拟Peggy

安全的识别协议本质上有三个要求。首先，协议需要正确（Correctness）——这意味着Victor在与Peggy进行正确的互动后始终相信Peggy的身份。其次，它必须是有效的（Soundness），这意味着只有Peggy（而不是模仿者）才能说服Victor接受。

我们对上面的这两个属性进行了非正式的论证。值得注意的是，这些论点中的每一个都主要依赖于这样一个事实：我们的魔盒确实有魔法——即Victor可以可靠地“测试”Peggy提供的魔盒。有效性还要求坏人无法“拆开”Peggy的魔盒并获取她的秘密斜率 m，这对于任何单向函数都应该成立。

但这些论点并没有彻底讨论盒子必须有多安全。如果攻击者能够了解一部分的 m 和 b 呢？为了解决这些问题，我们需要考虑第三个要求。

这个要求是，Victor在与Peggy一起运行协议后，不应该学到任何除了他从Peggy的公钥中已经知道的之外的东西。这个论点确实需要我们证明这些盒子非常魔法——也就是说，除了Victor可以从黑盒测试中获得的信息之外，它们不会泄露任何有关其内部秘密的有用信息。

回想一下，我们在这里基本担心的是Victor将与Peggy一起运行该协议，可能会运行多次。在每次运行协议结束时，Victor都会学到一份“记录”。该记录的内容是1)一个包含 “b” 的魔盒，2)Victor选择的挑战值 x，以及3)Peggy回答的响应 y。我们还将假设Victor“诚实”地随机选择了值 x，因此实际上他从Peggy那里获得的只有两个有趣的值。

我们可能会问的一个问题是：假设Victor想做一些坏事，比如假装是Peggy，那么这份记录中的信息对Victor有多大用处？

理想情况下，答案应该是“一点用处都没有”。

论证这一点的巧妙方法是证明Victor可以完美地“模拟”这些笔录，甚至根本不需要与Peggy交谈。因此，论证如下：如果Victor（就他自己）可以制作一份与他从Peggy交谈中得到的记录相同的记录，那么他从Peggy那里得到真实的记录到底“学到”了什么？显然的答案是：啥都没有。

因此，让我们花点时间考虑一下Victor如何（完全由他自己）在不与Peggy交谈的情况下制作一份“假”记录。我们回顾一下上面的“魔盒”协议：

模拟记录的一个比较容易想到的（错误）想法是Victor可以首先选择一些随机值 b，并将其放入一个全新的“魔盒”中。然后他可以随机选择 x，就像在真实协议中一样。但这个简单的尝试很快就会失败：Victor将很难计算 y=mx+b，因为他不知道Peggy的秘密密钥 m。正如我们所讨论的，他最好的尝试是猜测不同的值并测试它们，这将花费很长时间（如果字段很大）。

显然这种方法行不通。但请注意，Victor不一定需要“按顺序”伪造这份记录。另一种想法是，Victor可以尝试通过以不同的顺序执行协议来制作假记录。具体来说：

1.Victor可以选择一个随机 x，就像在真实协议中一样。 2.现在他也可以随机选择值 y。请注意，对于每个 “m”，都会存在一条穿过 (x,y)的线。 3.但现在Victor遇到了一个问题：为了完成协议，他需要制作一个包含 “b” 的新盒子，使得b=y−mx。

仅根据他所掌握的信息，Victor没有很好的方法来计算 b。因此，为了满足第三个要求，我们必须要求我们的魔盒具有全新的功能。具体来说，我们可以想象有某种方法可以从现有的魔盒中“制造”出新的魔盒，使得新的魔盒包含一个计算值。这相当于反转线性方程，然后对“盒装”值执行乘法和减法，这样我们最终得到：

“好吧。”你也许会问，“这是什么东西？怎么就多出来这一个奇怪的要求？“嗯，当然是这样。但请记住，我们一开始就说了需要具有特殊功能的魔法盒子。现在我只是添加一项神奇的能力。谁能说我不能做到这一点？

回想一下，生成的记录必须与Victor从Peggy那里得到的记录在统计上相似。很容易证明文字值 (x,y,b) 在两个版本中都具有相同的分布。我们“制造的神奇盒子”的统计分布有点复杂，因为我们甚至不知道“用另一个盒子制造一个盒子”到底意味着什么？我们目前暂时只是指定制造的产品必须与真实协议中创建的产品“看起来”相同。

当然，在现实世界中这很重要。我们需要确保我们的神奇盒子对象具有必要的功能，这些功能是（1）测试给定 (x，y) 是否在某条线上，以及（2）从一个包含 “m” 的盒子和点 (x，y) 制造出一个新的包含“b”的盒子，同时确保制造的盒子与普通方法制作的魔盒相同。

如何制造一个魔盒

一个简单的想法可能是将秘密值 m 和 b 分别放入标准单向函数中，然后发送 F(m) 和 F(b) 。这显然达到了隐藏这两个值的目的：不幸的是，它不允许我们对它们做太多其他事情。

事实上，简单的单向函数的最大问题是你只能用它们做一件事。也就是说：你可以生成一个秘密 x，你可以计算单向函数 F(x)，然后你可以将 x 透露给其他人来验证。一旦你做到了这一点，秘密就“消失了”。这使得简单的单向函数功能相当有限。

但是，如果 F 是一种不同类型的单向函数，具有一些附加功能呢？

在20世纪80年代初，许多研究人员正在考虑这种单向函数。更具体地说，Tahir Elgamal等研究人员正在研究Whitfield Diffie和Martin Hellman提出的一种当时新的“候选”单向函数，用于他们的同名密钥交换协议。

（译者注：下面还是要进入“一堆关于循环群的无聊细节”，缺少相关代数知识背景的读者，可以暂时先认为这里的所有运算都是在整数上“字面意思”，不考虑群的性质。并且读者可能需要一定的代数知识来理解以下内容。）

具体来说：设 p 是定义有限域的某个大的公开素数。并让 g 成为该域中包含的具有素数阶 q 的大循环子群的“生成器”。[4]（译者注：此处原为脚注3，疑为原作者笔误。但这样子文中就没有脚注3的位置了，不知3应该放在哪里。）如果这些值选择适当，我们可以定义一个函数 F(x) 如下：

这个函数的优点在于，如果适当选择 g 和 p，则(1)很容易计算该函数（使用快速幂），但(2)求函数的逆通常来说很困难。具体来说，只要 x 是从 中选择的，从F(x) 中恢复 x 就等价于求解离散对数问题。

但这个函数最特别的地方在于它具有很好的代数性质。具体来说，给定使用上述函数计算的 F(a)和 F(b)，我们可以轻松计算  。这是因为：

类似地，给定 F(a) 和已知的标量 c，我们可以计算 ：

我们还可以将这些功能结合起来。给定 F(m),F(b) 以及 x，我们可以计算 F(y)，其中。这条神奇的性质允许我们在“隐藏”于单向函数内的值上计算线性方程，在此之后我们可以将计算结果与其他人交给我们的y进行比较：

这为我们提供了实现上一节中Chris协议所需的魔盒。最终协议如下所示：

合适的循环群也可以用某些椭圆曲线来构建，例如NISTP-256和secp256k1曲线（用于比特币中的Schnorr签名）以及EdDSA标准（在Ed25519 Edwards曲线中实现的Schnorr签名）。在椭圆曲线上幂乘被标量点乘代替，但核心原理是完全相同的。

对于大多数人来说，此时您可能已经心满意足。您可能已经接受我的主张，即这些基于“离散对数”的单向函数足以隐藏值 (m,b)，因此它们就像魔盒一样。

但你不应该满足于此！这个协议事实上还有很多问题要解决。毕竟，幂函数和模函数并不是神奇的盒子。它们是真实的“东西”，可能会泄露有关 “m” 和 “b” 的信息。尤其在多次运行协议后，Victor将了解到许多关于这些值的信息。

为了有力地说明盒子不会泄漏，我们必须使用我在之前讨论的直觉。具体来说，我们需要证明，只要给出Peggy的公钥 ，就可以在不与Peggy本人交谈的情况下“模拟”记录。回想一下，在上面的讨论中，我们使用的方法是首先选择一个随机点 (x，y)，然后“制造”一个盒子，如下所示：

在我们的设置中，这相当于直接从 和 (x,y) 计算 。我们可以这样做：

（如果更严谨一点来说，这里我们用除法作为简写来表示乘以对应的的乘法逆元。）

很容易看出，只要 (x,y) 是随机选择的，b=y−mx 就与真实协议分布相同。（译者注：这里的“很容易看出”事实上是一次性密码本的性质）在这种情况下， 也将均匀分布，因为每个b和群上的元素之间存在一对一的映射。这是这个特殊魔盒的一个极其方便的功能。因此，我们可以认为这个原语（循环群）满足我们所有的安全要求。

从身份验证协议到签名：Fiat-Shamir

虽然到目前为止这篇文章是关于身份识别协议的，但你会注意到现在使用交互式ID协议的人相对较少。在工程上，“Schnorr”这个名字几乎总是指签名方案。Schnorr签名如今非常常见：它们被用在比特币中，构成了EdDSA等方案的基础。

当然，我花这么多时间在识别协议上是有原因的。这个原因是一种叫做Fiat-Shamir启发式算法的美丽“技巧”，它使我们能够毫不费力地把三步识别协议（通常称为“西格玛协议”，基于大写希腊字母的形状）变成非交互式签名。

我们简单聊聊它是怎么做到的。

Fiat和Shamir的主要想法是，Victor在三步协议中并没有做什么事情：他的主要任务只是选择一个随机挑战。当然，如果Peggy可以自己选择一个随机挑战，也许以某种方式基于她选择的“信息”，那么她就可以完全消除与Victor互动的需要。

在这个新场景中，Peggy将自己计算整个记录，并且她可以简单地将她与自己运行的协议的记录交给Victor。假设挑战值 x 可以“紧密”绑定到一条消息，那么这就可以将诸如Schnorr识别协议之类的交互协议转换为签名方案。

一个简单的想法是获取消息 M，并将挑战计算为 x=H(M)。

当然，正如我们在上面已经看到的，这是一个非常糟糕的想法。如果允许Peggy知道挑战值 x，那么即使她不知道密钥，她也可以使用上一节中描述的方法简单地“模拟”协议执行记录。由此产生的签名将毫无价值。

因此，为了让Peggy自己选择挑战值 x，她需要一种生成 x 的策略，该策略（1）只能在她“承诺”了包含 b 的第一个魔盒后才能执行，并且（2）不允许她预测或“操控”她在此过程结束时获得的 x 值。

Fiat和Shamir的关键结论是，如果Peggy拥有足够强的哈希函数 H，她就可以做到这一点。他们的想法如下。首先，Peggy将产生她的值 b．然后，她会将其放入正常协议中的“魔盒”中（如上面实例中的 ）。最后，她将 m 和 b 对应的盒子以及一条可选的“消息” M 代入哈希函数：

最后，她按部就班地计算协议的其余部分，并将记录  交给Victor，他可以通过重新计算哈希函数来获取 x 并验证 y 来检查该记录的正确性（如原始协议中所示。）

（这种方法的一个变体是Peggy给Victor一个稍微不同的记录：这里她将 (M,x,y) 发送给Victor，Victor现在计算  并测试是否有 。这个方案的正确性留给读者思考。）

这整套逻辑成立的前提是，Peggy必须很难“操纵”这个哈希函数，使得她能找到输入和输出之间的一些对应关系。在实践中，这需要一个哈希函数，其中输入和输出之间的“关系”满足我们所说的回避性：很难找到有助于模拟协议的两个点。

在实践中，我们经常在安全证明中把哈希函数看成是随机函数，这意味着输出与输入无关。由于又长又无聊的原因，这个模型有点虚伪。无论如何我们仍然使用它。（译者注：这里应该是指随机预言机模型[Random Oracle]。这一模型经常被用来在证明中替代哈希函数，但一部分近来的研究批评这一替代不能成立。）

还有别的魔盒么？

如上所述，“魔盒Schnorr”方案的一个关键要求是盒子本身必须由某种单向函数实例化：也就是说，必须没有有效的算法可以从盒子内恢复Peggy的随机密钥，除非使用暴力穷举，或使用一些差不多昂贵的（超多项式时间）攻击。

上面给出的循环群满足了这个要求，前提是离散对数问题（DLP）在用于计算它的特定群中是困难的。假设攻击者只有一台经典计算机，我们推测该假设对于基于有限域或某些椭圆曲线构造的足够大的群成立。

但你的对手何必是一台经典计算机。我们确实该为此动动脑筋。巧的是，只要有量子计算机，离散对数问题并不是特别难解决。在量子计算机上，存在基于Shor算法求解DLP（和ECDLP）的高效量子算法。

在我的下一篇文章中，我将讨论其中一个方案，即Dilithium签名方案，并准确展示它与Schnorr签名的关系。

欲知后事如何，请看下集。

文章最初发布于To Schnorr and beyond (Part 1) – A Few Thoughts on Cryptographic Engineering (cryptographyengineering.com)，原作者为 Matthew Green。本文为翻译。

1. “民间传说”在密码学里指没人知道到底是谁第一个想到的这个方案。在这个例子中这些想法是由RalphMerkle等人在另一个语境（一次性签名）中提出来的。 ↩︎

2. 由于有 个不同的子集可供选择，只要仔细选择N和k，Veronica选择与Victor完全相同的子集（允许他正确回答她的挑战）的概率就可以变得非常小。（例如，N=128和k=30时，因此坏人Victor几乎永远不会成功。） ↩︎

3. 在真实的证明中，我们实际上依赖于一种称为“倒带”的属性。在这里我们可以声明，如果存在某种算法（更具体地说，一种高效的概率性图灵机），只要给定Peggy的公钥，就可以高概率地冒充Peggy：那么一定有可能从这个算法中“提取”Peggy的秘密值 $m$。我们依赖这样一个事实：如果我们有这样一个图灵机，我们可以（至少）运行它两次，同时输入相同的随机磁带，但指定两个不同的 x 挑战。如果这样的算法在一般情况下以一定的概率成功，那么我们应该能够获得两个不同的点 (x,y),(x’,y’) ，然后我们可以求解(m,b)。 ↩︎

4. 我在这里指定一个素数阶子群并不是因为它是绝对必要的，而是因为对于一个质数 $q$ 来说，能用  来定义这些群元素很方便。要构造这样的群，必须选择素数 q、p，使得 p=2q+1 。这保证了在由域 Fp 定义的较大群中存在 q 阶子群。（译者注：这是因为 Fp 里一个元素的阶一定是 p−1 的因子[证明留待读者自行完成]，因为 p−1=2q，任意一个子群的阶大概率要么是 2，要么是 q） ↩︎