Fiat-Shamir启发式

Fiat-Shamir可以将交互式证明转换为非交互式证明。

交互式证明

以下使用基于离散对数的Sigma协议作为示例：

假设有参与者Alice（证明者）和Bob（验证者）,Alice想向Bob证明她知道某个秘密值sk.

1. Setup: Alice生成公私钥对(pk, sk)，并将公钥pk发送给Bob。
2. Commit: Alice选择随机数r，计算承诺值t = g^r，并将t发送给Bob。
3. Challenge: Bob选择随机挑战c，并将c发送给Alice。
4. Response: Alice计算响应值s = r + c * sk，发送s给Bob。
5. Verify: Bob验证等式g^s = t * pk^c是否成立。如果成立，Bob接受证明，否则拒绝。

非交互式证明

1. Setup: Alice生成公私钥对(pk, sk)，并将公钥pk发送给Bob。
2. Commit: Alice选择随机数r，计算承诺值t = g^r。
3. Challenge: Alice使用哈希函数H计算挑战c = H(t, pk)。
4. Response: Alice计算响应值s = r + c * sk。
5. Proof: Alice将证明(t, s)发送给Bob。
6. Verify: Bob计算挑战c = H(t, pk)，并验证等式g^s = t * pk^c是否成立。如果成立，Bob接受证明，否则拒绝。

为什么有效

Fiat-Shamir启发式的有效性基于以下几点：

• 随机性：哈希函数H的输出在理论上是不可预测的，类似于Bob随机选择挑战c。这确保了Alice无法预先计算出有效的响应s。
• 绑定性：一旦Alice计算出t，她就无法更改它，因为H(t, pk)会生成一个固定的挑战c。这防止了Alice在知道挑战后调整她的响应。
• 不可伪造性：如果Alice不知道私钥sk，她无法计算出有效的响应s，因为这需要知道sk来满足验证方程。