在关于Fiat-Shamir应用于证明系统的理论弱点的系列文章中，这是第三篇也是倒数第二篇。前两篇文章分别介绍了交互式证明系统、Fiat-Shamir启发式、随机预言机以及递归证明等背景知识。

背景定位

KRS研究结果处理了一个常见情境：许多新的证明系统最初是作为交互式协议开发的，然后通过Fiat-Shamir启发式"扁平化"为非交互式证明。在交互式设置中，验证者使用真实随机性诚实地选择挑战；而在Fiat-Shamir转换中，证明者通过哈希函数 deterministic 地生成挑战。

GKR15简明证明系统

KRS论文首先考虑了2015年由Goldwasser、Kalai和Rothblum设计的特定交互式证明系统（GKR15）。这是一个在算术电路上工作的早期结果，具有许多有趣的理论特性。

GKR15方案被设计为交互式协议，包含以下步骤：

• 证明者和验证者就电路C达成一致
• 证明者向验证者发送输入和输出(x, y)
• 在第一条"承诺"消息中发送对见证w的多项式承诺
• 验证者选择随机挑战c，证明者/验证者多次交互以响应此挑战

思想实验：“弱挑战”

假设在证明系统中存在一个特殊的"弱挑战"值c*。如果作弊的证明者幸运地被挑战到这个点，即使他们"证明"的陈述完全错误，也能够提出有效响应。

在交互式设置中，诚实验证者随机选择挑战，选中弱挑战的概率极低（如2^{-256}）。在Fiat-Shamir设置中，作弊证明者需要找到哈希函数的输入来产生特定输出c*，这同样非常困难。

更复杂的攻击场景

关键观察是：电路本质上是一种计算程序。如果设计一个能够计算c*的电路，情况会如何？

考虑一个特殊电路C*：

• 作弊证明者传递w和x = (h(C*), y* = “BANANAS”)作为输入
• 使用证明系统的承诺算法计算Commitment
• 电路内部计算c* = H(h(C*), x, y*, Commitment)
• 如果c* = “BANANAS”，则设置c* = “APPLES”
• 电路输出c*

这个电路永远不能输出C*(w, x) = “BANANAS”。但是，如果实际计算C*(w, x)恰好等于Fiat-Shamir挑战c*，作弊证明者就能成功完成协议，即使他们证明的陈述完全错误。

安全影响

在交互式协议中，证明者无法预测验证者的挑战，因此没有真正的作弊杠杆。但在Fiat-Shamir世界中，考虑到这种特殊电路C*，作弊证明者可以逃脱惩罚。

虽然这个例子看起来有些牵强，但密码协议非常精细。表面无用的漏洞可能扩展为实际重要的问题。在下一篇文章中，我们将看到这种漏洞如何应用于真实的GKR15方案。