零知识证明 — 数字签名的起源
在密码学中，了解数字签名工作原理的最好方法是了解它的起源。因此，让我们花点儿时间简要介绍一下零知识证明(ZKP)，然后重新讨论数字签名。 想象一下，Peggy 想向 Victor 证明自己拥有一些信息。例如，Peggy 想证明她知道某个群元素的离散对数。换句话说，对于一个给定的 Y 以及群生成元 g，Peggy 想要证明她知道一个 x， 满足 $$ Y = {g^x} $$ 当然，最简单的解决方案是 Peggy 把 x(称为见证)发送给 Victor。这就是一个简单的知识证明，但如果 Peggy 不想让 Victor 得到这个 x，这个方案就不适用了。
在密码学中，我们最感兴趣的是不会将证据泄露给验证者的知识证明，这种证明称为零知识证明。
交互式零知识证明
我们将从被攻破的协议中逐步构建一个 ZKP，并演示 Peggy 如何证明自己知道 x 而不透露 x。
密码学中处理这类问题的典型方法是使用一些随机值来“隐藏”见证(例如，通过加密)。但我们所做的不仅仅是隐藏: 我们还想证明这个见证确实存在。要做到这一点，我们需要一种代数方法来隐藏见证。
一个简单的解决方案是将随机生成的值 k 与见证相加: $$ s = k + x $$ 然后，Peggy 可以将隐藏了见证的 s 和随机值 k 一起发送给 Victor。
为了判断 Peggy 是否真的知道见证，Victor 可以检查 Peggy 给他的值是否与他所知道的相符，Victor 可以检查下面两个数字是否相等: $$ g^s = g^{k+x} = {g^x}{g^k} $$ $$ Y{g^k} = {g^x}{g^k} $$
这个方案的思想是，只有知道见证 x 的人才能构造出满足这个等式的“盲”证据 s。因此，这是知识的证明。但这个方案存在一个问题，显然它是不安全的! 事实上，由于隐藏见证 x 的等式只有一个未知项(x 本身)，因此 Victor 仅通过移项就可以求出 x 值: $$ x = s - k $$
为了解决这个问题，Peggy 可以把随机值 k 隐藏起来! Peggy 将随机值 k 隐藏在 g 的指数中（关键 🤔），以确保 Victor 的等式仍然有效。 $$ R = g^k $$ 这样一来，Victor 就无法获得 k 的值, 也就无法恢复 x 的值。不过他依然可以验证 Peggy 是否知道 x 的值! $$ g^s = g^{k+x} = {g^x}{g^k} $$ $$ YR = {g^x}{g^k} $$
我们的方案有一个问题，那就是 Peggy 可以作弊。她可以在不知道 x 的情况下让 Victor 相信她知道 x! 她所要做的就是颠倒她计算证明的步骤。Peggy 首先生成一个随机值 s，然后根据 s 计算 R 值: $$ R = \frac{g^s}{Y} $$
而 Victor 验证计算时，$ YR = g^s $ 确实成立，因此相信 Peggy 拥有见证 x。(这种使用逆运算来计算一个值的技巧也用于密码学中的许多攻击。)
如果要确保 ZKP 方案是可靠的，Victor 必须能够确保 Peggy 通过 R（k） 来计算 s，而不是通过 s 计算 R。为此，Victor 使协议具有交互性。
-
1.Peggy 必须对随机值 k 做出承诺，以确保 Peggy 以后无法更改 k 的值。
-
2.在收到 Peggy 的承诺后，Victor 在协议中引入了他自己的一些随机数。他生成一个随机值 c(称为挑战)，并将其发送给 Peggy。
-
3.然后，Peggy 可以根据随机值 k 和挑战 c 计算她隐藏了见证 x 的承诺。
由于 Peggy 在没有 Victor 的挑战 c 的情况下无法执行最后一步操作，而 Victor 在没有看到随 机值 k 的承诺的情况下不会将挑战 c 发送给 Peggy，因此 Peggy 不得不使用 k 来计算 s。
最后构成的协议称为 Schnorr 身份识别协议，Schnorr 身份识别协议是一个交互式 ZKP，它满足了完备性(Peggy 可以证明她知道一些见证 x)、 可靠性(Peggy 不知道见证 x 时无法证明她知道 x)、零知识性(Victor 对见证 x 一无所知)。
所谓的交互式 ZKP 方案通常包含 3 个步骤(承诺、挑战和证明)，在文献中通常被称为 Sigma 协议，有时写成 Σ (Sigma 的希腊字母表示方法)协议。那么这与数字签名有什么关系呢?
非交互式零知识证明
上述的交互式 ZKP 的问题在于它是交互式的，而现实世界中人们通常不希望协议是交互式 的。交互式协议增加了一些不可忽略的开销，因为它需要双方发送多条消息(通过网络)，并在参与双方不同时在线时会增加无法限制的延迟。因此，应用密码学领域几乎不使用交互式 ZKP。
但这并不说明之前的讨论毫无意义! 1986 年，Amos Fiat 和 Adi Shamir 提出了一项技术，该 技术可以轻松地将交互式 ZKP 转换为非交互式 ZKP。这项技术(称为 Fiat-Shamir 启发式或 Fiat-Shamir 转换)的关键是让证明者以他们无法控制的方式自己计算挑战。
这项技术的实现方法是，由证明者计算发送和接收的所有消息的哈希值，这个哈希值可以视为交互式协议中的挑战。如果哈希函数的输出与随机数无法区分(即哈希函数的输出看起来是随机的)，那么它可以成功地模拟验证者的角色。
Schnorr 在上面的基础之上注意到任何信息都可以计算哈希值! 例如，对一条消息计算哈希值。这样一来，我们得到的不仅是一个能证明我们知道某个见证 x 的证据，还是对一个与证据相关联(指在密码学上的关联)的消息的承诺。
换句话说，如果证据是正确的，那么只有知道见证(此处见证成为签名密钥)的人才能对该消息做出承诺。那就是签名! 数字签名就是非交互式 ZKP。将 Fiat-Shamir 转换应用于 Schnorr 身份识别协议， 我们就可以得到 Schnorr 签名方案。
总而言之，Schnorr 签名本质上是两个值，R 和 s，其中 R 是对某个秘密随机值的承诺(通常称秘密值为 nonce，因为它需要对每个签名都是唯一的)，s 是通过承诺 R、私钥(见证 x)和消息(挑战)计算的值。
参阅资料
推荐阅读