Fiat-Shamir

Fiat-Shamir 将交互式转化为非交互式如何体现？

Fiat-Shamir 启发式（Fiat-Shamir heuristic）是一种将交互式零知识证明协议转化为非交互式零知识证明协议的方法。它通过使用哈希函数来模拟交互式协议中的挑战，从而消除实际的交互过程。以下是 Fiat-Shamir 启发式的详细步骤和原理。

交互式零知识证明协议

以 Fiat-Shamir 协议为例，这是一个典型的交互式零知识证明协议，证明者（Prover）希望向验证者（Verifier）证明其知道某个秘密值 $x$，使得 $y = x^2 \mod n$，而不泄露 $x$ 的值。

交互式协议步骤

1. 证明者生成承诺：

• 证明者选择一个随机数 $r$。
• 计算 $v = r^2 \mod n$。
• 将 $v$ 发送给验证者。

2. 验证者生成挑战：

• 验证者选择一个随机挑战 $e \in \{0, 1\}$。
• 将 $e$ 发送给证明者。

3. 证明者生成响应：

• 如果 $e = 0$，证明者发送 $r$ 给验证者。
• 如果 $e = 1$，证明者发送 $s = r \cdot x \mod n$ 给验证者。

4. 验证者验证响应：

• 如果 $e = 0$，验证者检查 $v \stackrel{?}{=} r^2 \mod n$。
• 如果 $e = 1$，验证者检查 $v \cdot y \stackrel{?}{=} s^2 \mod n$。

Fiat-Shamir 启发式

为了将上述交互式协议转化为非交互式协议，Fiat-Shamir 启发式使用哈希函数 $H$ 来生成挑战 $e$，从而消除验证者的交互。

非交互式协议步骤

1. 证明者生成承诺：

• 证明者选择一个随机数 $r$。
• 计算 $v = r^2 \mod n$。

2. 证明者生成挑战：

• 证明者计算挑战 $e$ 为 $e = H(m \| v)$，其中 $m$ 是要证明的消息，$v$ 是承诺值。

3. 证明者生成响应：

• 如果 $e = 0$，证明者计算响应 $z = r$。
• 如果 $e = 1$，证明者计算响应 $z = r \cdot x \mod n$。

4. 证明者发送证明：

• 证明者将 $(v, e, z)$ 发送给验证者。

5. 验证者验证证明：

• 验证者计算挑战 $e' = H(m \| v)$。
• 如果 $e' \neq e$，验证失败。
• 如果 $e = 0$，验证者检查 $v \stackrel{?}{=} z^2 \mod n$。
• 如果 $e = 1$，验证者检查 $v \cdot y \stackrel{?}{=} z^2 \mod n$。

总结

Fiat-Shamir 启发式通过使用哈希函数 $H$ 来生成挑战 $e$，从而消除了交互过程。具体步骤如下：

1. 证明者生成承诺并计算哈希值作为挑战。
2. 证明者根据挑战生成响应。
3. 证明者将承诺、挑战和响应发送给验证者。
4. 验证者通过重新计算哈希值和验证响应来验证证明的正确性。

这种方法将交互式协议转化为非交互式协议，使得证明过程更加高效和实用，特别是在分布式系统和区块链应用中。

Schnorr 协议在 Fiat-Shamir 启发式中的推导

好的，我们可以通过 Schnorr 协议来详细推导这个证明过程。Schnorr 协议是一个典型的零知识证明协议，它可以用来证明一个人知道某个离散对数而不泄露任何关于这个离散对数的信息。以下是 Schnorr 协议在 Fiat-Shamir 启发式中的推导步骤：

设定

• 公钥参数：
  • 大素数 $p$ 和 $q$，其中 $q$ 是 $p-1$ 的因子。
  • 生成元 $g$，它是模 $p$ 的一个阶为 $q$ 的元素。
• 证明者的秘密：私钥 $x$。
• 证明者的公钥：$y = g^x \mod p$。
• 消息：$m$ 是要证明的消息。

证明者的步骤

1. 生成承诺：

   • 证明者选择一个随机数 $r$，其中 $r \in \mathbb{Z}_q$。
   • 计算承诺值 $v = g^r \mod p$。

2. 生成挑战：

   • 证明者计算挑战 $e$ 为 $e = H(m \| v)$，其中 $H$ 是一个安全的哈希函数。

3. 生成响应：

   • 证明者计算响应 $z$ 为 $z = r + e \cdot x \mod q$。

4. 发送证明：

   • 证明者将 $(v, z)$ 发送给验证者。

验证者的步骤

1. 接收证明：

   • 验证者接收到 $(v, z)$。

2. 生成挑战：

   • 验证者计算挑战 $e$ 为 $e = H(m \| v)$。

3. 验证响应：

   • 验证者检查以下等式是否成立： $$g^z \stackrel{?}{=} v \cdot y^e \mod p$$

推导证明的正确性

我们需要证明验证者的验证步骤是正确的，即如果证明者确实知道私钥 $x$，那么验证者的检查一定会通过。

证明者的计算

1. 计算承诺：

$$v = g^r \mod p$$

2. 计算挑战：

$$e = H(m \| v)$$

3. 计算响应：

$$z = r + e \cdot x \mod q$$

验证者的验证

验证者需要验证以下等式：

$$g^z \stackrel{?}{=} v \cdot y^e \mod p$$

将 $z$ 的表达式代入左边：

$$g^z = g^{r + e \cdot x} \mod p$$

利用指数的性质，我们可以将其拆分为：

$$g^z = g^r \cdot g^{e \cdot x} \mod p$$

因为 $y = g^x \mod p$，所以：

$$g^z = g^r \cdot (g^x)^e \mod p$$ $$g^z = g^r \cdot y^e \mod p$$

而 $v = g^r \mod p$，所以：

$$g^z = v \cdot y^e \mod p$$

这正是验证者需要验证的等式。因此，如果证明者确实知道私钥 $x$，那么验证者的验证步骤一定会通过。

总结

通过上述推导，我们可以看到，在 Schnorr 协议中，验证者和证明者使用相同的哈希函数和相同的输入生成相同的挑战 $e$。验证者通过检查 $g^z \stackrel{?}{=} v \cdot y^e \mod p$ 来验证证明者的响应 $z$ 的正确性。这确保了证明者确实知道私钥 $x$ 而不泄露任何关于 $x$ 的信息。