区块链原理 / 系统课时

用交互式协议验证秘密知识

用交互式协议验证秘密知识

如何让验证者相信你掌握某个秘密,却不把秘密直接交给对方?交互式证明通过承诺、随机挑战和响应完成验证。本篇使用经典的 Schnorr 身份识别协议,计算一次完整交互,并分析作弊概率、重复验证的效果和隐私边界。

学习目标

  • 理解承诺、挑战、响应各自承担的安全职责。
  • 使用小整数完成一次 Schnorr 交互式证明并验证结果。
  • 计算重复挑战的作弊概率,辨别知识证明与零知识性质的适用条件。

从公开关系定义要证明的秘密

假设证明者 Alice 知道秘密整数 xx,但只公开与它有关的值 yy。验证者 Bob 希望确认 Alice 掌握满足指定数学关系的 xx,而不是让 Alice 直接说出它。

在 Schnorr 协议中,双方事先约定素数 pp、素数阶 qq,以及模 pp 下阶为 qq 的元素 gg。公开关系为:

y=gx mod py=g^x\bmod p

Alice 的秘密是 xx,公开信息是 pp、qq、gg、yy。Bob 只需验证 Alice 是否能正确回应临时随机挑战。

为了便于手工计算,采用以下教学参数:

参数 数值 作用
pp 23 模运算使用的素数
qq 11 子群的素数阶,且整除 p−1p-1
gg 2 模 23 下阶为 11 的生成元
xx 4 Alice 保存的秘密
yy 16 公开值,24 mod 23=162^4\bmod23=16

实际使用时必须选择经过验证的密码学参数;这里的数字很小,攻击者可以穷举秘密,完全不具备实际安全性。

承诺、挑战与响应如何配合

一次完整交互分为三轮消息。

  1. 承诺:Alice 随机选择一次性整数 rr,计算 t=gr mod pt=g^r\bmod p,只发送 tt。
  2. 挑战:Bob 在规定集合中均匀随机选择 cc,发送给 Alice。挑战必须在收到承诺之后生成。
  3. 响应:Alice 计算 s=(r+cx) mod qs=(r+cx)\bmod q,发送 ss。Bob 检查 gs mod pg^s\bmod p 是否等于 (t⋅yc) mod p(t\cdot y^c)\bmod p。

Schnorr 交互式证明三轮消息时序图

为什么验证公式成立?因为 s≡r+cx(modq)s\equiv r+cx\pmod q,而 gg 的阶为 qq,所以:

gs≡gr+cx=gr(gx)c=t⋅yc(modp)g^s\equiv g^{r+cx}=g^r(g^x)^c=t\cdot y^c\pmod p

承诺固定了 Alice 在看到挑战前的选择;挑战使她无法只针对预知的问题准备答案;响应则把临时随机数与秘密联系起来。即使 Bob 保存了完整交互记录,也不会直接收到 xx。

手工完成一次成功验证

继续使用上述教学参数。Alice 选择 r=3r=3,Bob 随机抽到挑战 c=2c=2。

首先计算承诺:

t=23 mod 23=8t=2^3\bmod23=8

Alice 收到挑战后计算响应:

s=(3+2×4) mod 11=0s=(3+2\times4)\bmod11=0

Bob 不需要知道 x=4x=4,只用公开信息、承诺与响应完成验证。

验证项目 计算 结果
左侧 20 mod 232^0\bmod23 1
右侧 (8×162) mod 23(8\times16^2)\bmod23 1
判定 左侧等于右侧 接受

这里响应为 0 是合法情况,并不意味着秘密为 0。响应属于模 qq 的整数集合,因此有效范围是 0 到 10。

如果 Alice 在相同承诺和挑战下错误地发送 s=1s=1,验证左侧将变成 2,而右侧仍为 1,Bob 应当拒绝。

实际实现还必须校验公开参数及群成员资格,并检查承诺 tt 和响应 ss 的取值范围,不能只比较等式就直接接受任意输入。

随机挑战如何限制作弊

假设攻击者不知道 xx,却希望 Bob 接受证明。攻击者可以预先选择一个目标挑战 c∗c^* 和响应 s∗s^*,反向构造承诺:

t=gs∗(yc∗)−1 mod pt=g^{s^*}(y^{c^*})^{-1}\bmod p

该承诺可以通过其预设挑战的检查,但攻击者无法控制 Bob 随后随机抽到的挑战。当挑战从 0 到 10 均匀抽取时,预先猜中目标挑战的概率为 1/111/11。

更严格地说,对于固定承诺,若攻击者能针对两个不同挑战给出有效响应,就可以利用响应差值提取秘密:

x=(s1−s2)(c1−c2)−1 mod qx=(s_1-s_2)(c_1-c_2)^{-1}\bmod q

由于 q=11q=11 为素数且两个挑战不同,差值的模逆元存在。这一性质称为特殊可靠性,是 Schnorr 知识证明的重要依据。

当独立重复交互 kk 次、每次均重新生成承诺并抽取挑战时,理想协议模型下,不知道见证的作弊者全部通过的概率最多为:

Pcheat≤(111)kP_{\mathrm{cheat}}\leq\left(\frac{1}{11}\right)^k
独立交互次数 作弊成功概率上界
1 约 9.09%
3 约 0.0751%
5 约 0.000621%

上述概率是针对合法群参数、均匀独立挑战及协议模型的可靠性分析,不表示这个 23 模数的教学实例已经安全。小群允许攻击者直接枚举离散对数,甚至得到真实秘密。

真实密码学部署通常使用具有足够大挑战空间及可靠离散对数难题假设的成熟曲线或群,并选用经过审查的协议实现,不靠反复执行小整数示例保障安全。

不泄露秘密与零知识的边界

交互中没有直接发送秘密,并不足以证明协议具有零知识性质。还需要论证验证者所见消息能够在不知道秘密的情况下模拟出来,从而不额外暴露秘密信息。

对于诚实验证者 Schnorr 协议,可以先随机选择挑战 cc 和响应 ss,再构造:

t=gs(yc)−1 mod pt=g^s(y^c)^{-1}\bmod p

由此得到的 (t,c,s)(t,c,s) 与诚实执行时的交互记录具有相同分布。这里的关键条件是挑战由诚实验证者均匀随机生成,且模拟器可以先选挑战再构造记录;因此证明的是诚实验证者零知识,不能直接把该论证扩展为任意恶意验证者下的零知识。

还要区分三个容易混淆的结论:

  • 完整性:Alice 确实知道合法秘密并正确执行协议时,Bob 会接受。
  • 知识可靠性:不知道秘密的攻击者难以持续通过随机挑战;满足条件的两个不同挑战响应可用于提取秘密。
  • 零知识:验证过程除证明关系成立之外,不应泄露关于秘密的额外知识,需要独立的模拟论证。

交互式协议还存在转述攻击风险:恶意中间人可能实时转发 Alice 与 Bob 的消息,让 Bob 接受,却不曾自己知道秘密。因此,单次成功验证不能自动证明连接对端的身份,也不能代替会话绑定、身份认证和抗中继机制。

例如,将证明用于登录时,应使用经过安全分析的身份识别协议,并把服务端身份、会话上下文和挑战新鲜性纳入认证设计。不能把一个未经约束的交互记录直接当成可复用的登录凭证。

用两个问题检查是否真正理解

第一题:保持公开参数不变,Alice 选择新的 r=5r=5,Bob 发出 c=3c=3。计算可得 t=25 mod 23=9t=2^5\bmod23=9,s=(5+3×4) mod 11=6s=(5+3\times4)\bmod11=6。验证左侧 26 mod 23=182^6\bmod23=18,右侧 (9×163) mod 23=18(9\times16^3)\bmod23=18,因此接受。

第二题:某系统连续证明三次,却复用同一个随机数 rr。这种设计不安全。若两个挑战分别为 c1=2c_1=2、c2=3c_2=3,响应为 s1=0s_1=0、s2=4s_2=4,观察者可以计算 x=(0−4)(2−3)−1 mod 11=4x=(0-4)(2-3)^{-1}\bmod11=4,恢复秘密。

交互式证明的可信度来自承诺先行、挑战随机、响应可验证,以及对群参数和随机数的严格约束。理解这些条件后,才能进一步判断如何将交互改造为非交互式证明,以及改造后哪些安全性质需要重新论证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用交互式协议验证秘密知识

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通