Schnorr

Schnorr 协议是一个经典的零知识证明协议，旨在证明证明者（Prover）知道某个秘密信息（比如离散对数），而不会泄露任何关于该信息的实际内容。Schnorr 协议本质上是一个互动证明协议，用于验证者确认证明者是否知道某个秘密 $w$，而不暴露该秘密。

1. 问题背景和设定

Schnorr 协议常用于证明离散对数问题的知识。假设我们有以下公钥参数：

• $p$ 是一个大素数。
• $q$ 是 $p-1$ 的一个因子。
• $g$ 是一个生成元，属于模 $p$ 的群 $F_p^*$。
• $y = g^w \mod p$，其中 $w$ 是一个秘密离散对数（即我们想要证明的秘密）。

问题：给定公钥 $(p, q, g, y)$，证明者希望向验证者证明她知道某个离散对数 $w$，使得 $g^w = y \mod p$。

2. Schnorr 协议流程

Schnorr 协议是一个互动证明协议，由以下四个步骤组成：

步骤 1：初始化

• 公钥 $(p, q, g, y)$ 被公开，证明者拥有秘密 $w$，即离散对数 $w$ 满足 $g^w = y \mod p$。
• 验证者没有关于 $w$ 的任何信息，但知道公共参数 $(p, q, g, y)$。

步骤 2：承诺阶段（Commitment）

• 证明者选择一个随机数 $r$（该随机数的选择确保了证明的“零知识性”），计算 $t = g^r \mod p$。
• 证明者将计算结果 $t$ 发送给验证者。这个过程称为“承诺”，因为证明者通过 $t$ 向验证者承诺某个值，而这个值是与 $r$ 和 $w$ 密切相关的。

步骤 3：挑战阶段（Challenge）

• 验证者生成一个随机挑战值 $c$，通常是从某个预定义的范围（比如 $c \in \mathbb{Z}_q$）中选择的。
• 验证者将这个挑战值 $c$ 发送给证明者。

步骤 4：响应阶段（Response）

• 证明者计算响应值 $s = r + c \cdot w \mod q$，并将 $s$ 发送给验证者。
  • $r$ 是她在承诺阶段选择的随机数。
  • $c$ 是验证者在挑战阶段发送的随机数。
  • $w$ 是证明者要证明她知道的秘密离散对数。

步骤 5：验证阶段（Verification）

• 验证者验证以下条件是否成立：

  $$g^s \stackrel{?}{\equiv} t \cdot y^c \mod p$$

  如果等式成立，则证明者通过 Schnorr 协议成功证明她知道离散对数 $w$。否则，证明是无效的。

3. 数学背景和验证

Schnorr 协议的安全性依赖于离散对数问题的困难性，即给定 $g, y$ 和 $p$，没有有效的算法可以高效地计算出 $w$，即 $y = g^w \mod p$ 的解。

让我们看看为什么验证阶段的条件成立的数学推导：

1. 在承诺阶段，证明者发送了 $t = g^r \mod p$。
2. 在响应阶段，证明者发送了 $s = r + c \cdot w \mod q$。
3. 在验证阶段，验证者检查条件：

   $$g^s \stackrel{?}{\equiv} t \cdot y^c \mod p$$

   将 $s = r + c \cdot w$ 代入：

   $$g^{r + c \cdot w} = g^r \cdot g^{c \cdot w} \mod p$$

   由于 $g^{r} \equiv t \mod p$，以及 $y = g^w \mod p$，可以得到：

   $$g^{r + c \cdot w} = g^r \cdot (g^w)^c = t \cdot y^c \mod p$$

   因此，验证者验证的条件 $g^s \equiv t \cdot y^c \mod p$ 成立。

Schnorr例子

参数设置：

• $p = 23$ （模数，素数）
• $g = 5$ （生成元）
• $w = 6$ （秘密离散对数）
• $y = g^w \mod p$ （公钥，证明者的公开信息）
• 证明者和验证者之间的协议。

步骤 1: 计算公钥 $y$

证明者知道她的秘密 $w = 6$，她计算公钥 $y$：

$$y = g^w \mod p = 5^6 \mod 23 = 15625 \mod 23 = 8$$

因此，证明者的公钥是 $y = 8$。

步骤 2: 承诺阶段

证明者选择一个随机数 $r = 4$，然后计算承诺值 $t$：

$$t = g^r \mod p = 5^4 \mod 23$$

首先计算 $5^4 \mod 23$：

$$5^2 = 25 \mod 23 = 2$$

$$5^4 = (5^2)^2 = 2^2 = 4 \mod 23$$

因此，承诺值是 $t = 4$。

步骤 3: 挑战阶段

验证者生成一个随机挑战值 $c = 3$。

步骤 4: 响应阶段

证明者计算响应 $s$：

$$s = r + c \cdot w \mod (p-1) = 4 + 3 \cdot 6 \mod 22 = 4 + 18 \mod 22 = 22 \mod 22 = 0$$

因此，响应值是 $s = 0$。

步骤 5: 验证阶段

验证者需要验证以下条件：

$$g^s \equiv t \cdot y^c \mod p$$

我们将进行验证：

1. 计算 $g^s \mod p = 5^0 \mod 23$：

$$g^s \mod p = 5^0 \mod 23 = 1$$

2. 计算 $t \cdot y^c \mod p = 4 \cdot 8^3 \mod 23$：

   先计算 $8^3 \mod 23$：

$$8^2 = 64 \mod 23 = 18$$

$$8^3 = 8 \cdot 18 = 144 \mod 23 = 6$$

然后计算 $t \cdot y^c \mod p$：

$$4 \cdot 6 = 24 \mod 23 = 1$$

最终结果

我们得到：

$$g^s \mod p = 1 \quad \text{与} \quad t \cdot y^c \mod p = 1$$

因为 $g^s \mod p = t \cdot y^c \mod p$，所以验证通过，证明者成功地证明她知道离散对数 $w$。