第 15章 零知识证明
15.1 交互式零知识证明系统的定义
?交互图灵机作为证明者和验证者各自的计
算模型，将他们各自的交互图灵机连接起
来联合计算就构成一问一答的交互协议。
?定义 15.1 一个交互图灵机是一个（确定性）
多带图灵机。它具有下列带,1）一条只读
输入带； 2）一条只读随机带； 3）一条读
写工作带； 4）一条只写输出带； 5）一条
只读通信带和一条只写通信带； 6）一条仅
有一个小方格的读写开关带。
? 定义 15.2 二个交互图灵机连接在一起，若一个图灵机的
识别标记为 1而另一个图灵机的识别标记为 0，它们的输入
带合一，开关带合一，一个图灵机的只读通信带与另一图
灵机的只写通信带合一，反之前者的只写通信带与后者的
只读通信带合一，但两个图灵机的随机带，工作带和输出
带是分开的。一对连接起来的交互图灵机在初始时刻有共
同的输入，并置开关带的内容为 0。它们的联合计算程序
是一对形的有限或无限序列，其中一个形序列代表一个图
灵机的计算程序。序列中的每一对形总是有一个图灵机
（不必是同一个）工作而另一个图灵机休息。第一对形对
应于图灵机的初始状态，共同输入和开关带的内容 0。若
一个图灵机停机了但开关带的内容仍与它的识别标记相等，
称这时两个图灵机都已停机了，即计算在这一时刻终止。
两个图灵机的输出由这一时刻输出带的内容决定。
? 定义 15.3 设 A,B为连接起来的一对交互图灵机，设对每
一共同输入，它们的联合计算在有限步终止。记 (A,B)(x)
为共同输入 x联合计算终止时 B的输出。它是在 {0,1}中取值
的随机变量，即在联合计算终止时刻图灵机 B的只写头在
输出带所写的二进数。由于 A,B的随机输入满足随机数
约定，故 (A,B)(x)为随机变量。
? 定义 15.4 一个交互图灵机 A称为有时间复杂性
（正整数集），若它与每个交互图灵机 B连接起来和对每
个共同输入 x，它总是在 t(|x|)步内停机（与 A和 B的随机输
入无关，只要满足随机数约定即可）。特别若存在一个正
多项式 p(n)，使图灵机 A有时间复杂性 p(|x|)，则称图灵机
A是多项式时间的。
?? ? ZZt,
?定义 15.5 一对连接起来的交互图灵机（ P,V）称
为语言 L成员识别问题的交互（式省去）证明系统，
若 V是多项式时间的，且满足下列两个条件。
(1)完全性：对每个 x∈ L,(15.1）
(2)合理性：对每个 x∈ L和每个交互图灵机 B,B与 V
连接起来,或
（ 15.2）
?其中 V的输出 (P,V)(x)和 (B,V)(x)表示验证者是否接
受 x∈ L，输出 1表示接受 x∈ L，输出 0表示拒绝
x∈ L。
? ? 3/21)(VP(Pr ??x），
? ? 3/20)(VB(Pr ??x）,? ? 3/11)(VB(Pr ??x），
?定理 15.1 语言 L的成员识别问题属于 NP，
当且仅当它有一个交互证明系统具有下列
两个性质。
(1)交互是单向的（从证明者到验证者）。
(2)证明者和验证者都只用确定性算法（不出
错）。
? 定义 15.6 设（ P,V）为语言 L的交互证明系统（参看定义
15.5），称（ P,V）为语言 L的一个关于不诚实验证者的
交互完全零知识证明系统，若对每个多项式时间的交互图
灵机 V*，存在一个多项式时间的概率图灵机 M*，使对每
个 x∈ L，下面两个条件成立。
1)当 M*的输入为 x时，它以 2-p(|x|)的概率输出一个特殊符号，
记作 ⊥,即,其中 p(n)为任一固定的
正多项式。
2）记 m*(x)为一随机变量，其分布为 M*(x) ≠⊥ 的条件下
M*(x)的条件分布，即
再记 ViewP,V’(x)为共同输入 x时在 P与 V*交互（联合计算）
过程中从 V*的随机带读出的随机数以及 V*从 P收到的消息，
称为 V*的观察。
于是有 ViewP,V’(x)与 m*(x)是相同分布的随机变量。
M*称为 P与 V*交互的完善模拟器。
? ? |)(|* 2)(MPr xpx ????
? ? ? ? ? ? **** 10)(M|)(MPr)(Pr,,?????? ??? xxxm
?定义 15.7 设 (P,V)为语言 L的交互证明系统，
称 (P,V)为语言 L的一个关于不诚实验证者
的交互计算零知识证明系统，若对每个多
项式时间的交互图灵机 V*，存在一个多项
式时间的概率图灵机 M*，使随机变量族
与 是计算不可区分的
（参看定义 6.2）。
M*称为 P与 V*交互的模拟器。
? ? LV,P )(* ?xxV ie w ? ? L* )(M ?xx
?定义 15.8 设（ P,V）为语言 L的交互证明系统，
称（ P,V）为语言 L的一个关于不诚实验证者的
交互统计（几乎完全）零知识证明系统，若对每
个多项式时间的交互图灵机 V*，存在一个多项式
时间的概率图灵机 M*，使随机变量族
与 是统计接近的，即它们的变差距离
（ 15.3）
是 |x|的一个可忽略函数，即对每个正多项式 p(n)
及一切充分大的 |x|有 。
? ? LV,P )(* ?xxV ie w
? ? L* )(M ?xx
? ? ? ?
? ???
??????
*
*
1,0
*
V,P L,)(MPr)(Pr2
1)(
?
?? xxxV i e wx
|)(|/1)( xpx ??
?定义 15.9 设（ P,V）为语言 L的交互证明
系统，称（ P,V）为语言 L的一个关于诚实
验证者的交互计算零知识证明系统，若存
在一个多项式时间概率图灵机 M，使随机变
量族 与 是计算不可区分的
（参看定义 6.2）。
? ? LV,P )( ?xxView ? ? L)(M ?xx
15.2 交互零知识证明系统的构造
? （一）无向图的同构问题
? 1,共同输入为两个同构的图 G1=(V1,E1)和 G2=(V2,E2)。设 Φ为
G1到 G2的同构，即 Φ为从 V1到 V2的 1-1映射，使 (u,v) ∈ E1，当且仅
当 。
? 2,重复执行下列 3－ 6步 n次。
? 3,P按等概分布随机选择 V2的一个置换并构造图 G’=(V’,E’)，其中
,（ ）；
。 P将 G’=(V’,E’)发给 V。
? 4,V收到 P发送的图 G’=(V’,E’)后，按等概分布随机选择一个
σ ∈ {1,2},V将 σ 发送给 P，要求 P给出到 G’的同构。
? 5,若 P收到 V发送的 σ,则 P将 π 发送给 V，否则，即 σ ≠2，则 P将
发送给 V。
? 6,若 V收到 P发送的消息，记作 ψ,是 Gσ 到 G’的同构，则 V输出 1
（接受），否则 V输出 0（拒绝）。
2E))(),( ?vu ??（
? ?)(,),(),(V |V|21' 2uuu ??? ?? ? ?|V|212
2.,,V uuu ???
? ?2' E),()),(),((E ?? vuvu ??
)V)),(()(( 1???? uuu ??????
? 定理 15.2 上面给出的程序 GI是语言 GI的一个关于不诚实验
证者的交互完全零知识证明系统。更确切地说，它满足下
列性质。
1)若 x=（ G1,G2） ∈ GI（ G1与 G2同构），则
即验证者总是接受 x ∈ GI。
2)若 x=（ G1,G2） ∈ GI（ G1与 G2不同构），则对每个交互
图灵机 B
即对每一个可能的证明者 B与 V交互，验证者仍用 V的程序
4和 6，则验证者拒绝 x∈ GI的概率至少是 1/2。
3)对每个多项式时间的交互图灵机 V*，存在一个多项式时间
的概率图灵机 M*，当输入 x=（ G1,G2） ∈ GI时,
与 m*(x)是相同分布的随机变量（参看定义 15.6），其中，
证明者仍用 P的程序 3和 5。
? ? 11))(V,P(Pr ??x
? ? 2/10))(V,B(Pr ??x
)(*V,P xView
（二）二次剩余问题
? 1,共同输入为 N,x，其中 N为未知因子分解的 N=PQ,P,Q为
素数,x与 N互素,x∈ QR(N)
? 2,重复执行 3-6步「 logN」次（ N看作二进数表示）。
? 3,P按等概分布从 ZN*中随机选出一个 v，计算 y=v2(mod
N),P将 y发送给 V。
? 4,V 收到 P发送的 y后，按等概分布随机选择一个
σ ∈ {0,1},V将 σ 发送给 P。
? 5,P收到 V发送的 σ 后，计算,其中 u为 x的一个
模 N的平方根,P将 z发送给 V。
? 6,若 V收到 P发送的 z满足,则 V输出 1（接受），
否则 V输出 0（拒绝）。
)(m o dNvuz ??
)(m o d2 Nyxz ??
?定理 15.3 上面给出的程序 QR是语言 QR的一个关
于不诚实验证者的交互完全零知识证明系统。更
确切地说，它满足下列性质。
1)若 x∈ QR(N)，则
2)若 x∈ QR(N)，则对每个交互图灵机 B
或
3)对每个多项式时间的交互图灵机 V*，存在一个多
项式时间的概率图灵机 M*，当输入 x∈ QR(N)时，
与 m*(x)是相同分布的随机变量，其中，
证明者仍用 P的程序 3和 5。
? ? 11))(V,P(Pr ??x
? ? 2/10))(V,B(Pr ??x ? ? 2/11)(VP(Pr ??x），
)(*V,P xView
（三）子群成员问题
? 1.共同输入为 (N,l,α,β)，其中 α,β∈ ZN*,α ≠β,α 的阶
为 l。
? 2.重复执行 3－ 6步「 logN」次（ N看作二进数表示）。
? 3.P按等概分布从 {o,1,…,l -1}中随机选出一个 j，计算 r= α j
(mod N),P将 r发送给 V。
? 4.V收到 P发送的 r后，按等概分布随机选择一个 σ ∈ {0,1}，
V将 σ 发送给 P。
? 5.P收到 V发送的 σ 后，计算 h=j+ σ m(mod N)，其中 m=log
α β（ β的以 α 为底的离散对数）,P将 h发送给 V。
? 6.若 V收到 P发送的 h满足,则 V输出 1（接
受），否则 V输出 0（拒绝）。
)( m o d Nrh ??? ?
?定理 15.4 上面给出的程序 SM是语言 SM的
一个关于不诚实验证者的交互完全零知识
证明系统。
NP完全类问题的交互零知识证明系统 ——
图的 3-着色问题
? 1,共同输入为一可 3-着色的图 G=(V,E)。
? 2,重复执行下列 3－ 6步 |E|2次。
? 3,设 ψ 为图 G的一个 3-着色。 P按等概分布随机选择 {1,2,3}
的一个置换 π,并构造,即 Φ为图 G的一
个随机 3-着色（颜色的标记 1,2,3是随机的）。 P用 |V|
个保险箱，每个保险箱里放一个 Φ(u),u∈ V，将所有 |V|个
保险箱都发送给 V（验证者）。
? 4,V（验证者）按等概分布从 E中随机选出一条边 (u,v)，
将它发送给 P，要求检查 u和 v的着色。
? 5,P收到 V发送的 (u,v)后，将放有 Φ(u)和 Φ(v)的两个保
险箱的密码发送给 V。
? 6,V打开这两个保险箱，若他看到的是 {1,2,3}中两个不同
的数，则 V输出 1（接受），否则 V输出 0（拒绝）。
V) ),(()( ?? uuu ???
15.3 非交互零知识证明系统理论
? 定义 15.10 一对概率图灵机（ P,V）称为语言 L的非交互
证明系统，若 V是多项式时间的，且满足下列两个条件。
? 1）完全性：对每个 x∈ L,（ 15.4）
? 其中,x为（ P,V）的共同输入； R为（ P,V）的共同参
考序列，它是在 {0,1}p(|x|)中等概分布的随机序列,p(n)为
任一固定的正多项式； P(x,R)为 P发送给 V的消息（ P的输
出和 V的输入）。
? 2）合理性：对每个 L和每个交互图灵机 B
或 (15.5)
? 其中,表示验证者接受 L,
表示验证者拒绝 L。
? ? 3/21)),(P,,(VPr ??RxRx
? ? 3/20)),(B,,(VPr ??RxRx ? ? 3/11)),(B,,(VPr ??RxRx
1)),(B,,(V ?RxRx 0)),(B,,(V ?RxRx
?定义 15.11 一个语言 L的非交互证明系统
（ P,V）称为是计算零知识的，若存在一
正多项式 p(n)和一个多项式时间概率图灵机
M，使随机变量族 与
是计算不可区分的。 ? ? L|)(||)(| ),(P,,( ?xxpxp UxUx
? ? L)(M ?xx
?定义 15.12 一对概率图灵机（ P,V）称为语言 L
的隐比特证明系统，若 V是多项式时间的，且满
足下列两个条件。
1)完全性：对每个 x∈ L,
其中,为 P发送给 V的消息（ P的输出
和 V的输入）,Cer称为证明书,
为的指定位置集，称为泄漏的比特位置集,x为
（ P,V）的共同输入,R=r1,…r t是在 {0,1}p(|x|)中
等概分布的随机序列,为 R在指定位置
集 I上的子序列，称为泄漏的比特序列。
2)合理性：对每个 x∈ L和每个概率图灵机 B
或
其中,是 B发送给 V的消息（ B的输出和
V的输入）。
? ? 3/21),,,(VPr ??C erIRx I
),(P),( RxC e rI ?
? ? ? ?|)(|,,2,1,,1 xpiiI ?? ?? ?
?iiI rrR ?1?
? ? 3/20),,,(VPr ??C erIRx I ? ? 3/11),,,(VPr ??C erIRx I
),(B),( RxC e rI ?
?定义 15.13 一个语言 L的隐比特证明系统
（ P,V）称为是计算零知识的，若存在一
个多项式时间概率图灵机 M，使随机变量族
与 是计
算不可区分的。
? ? ? ? LL ),,,()),(P,,( ?? ? xIxI C erIRxRxRx ? ?)(M ?xx
构造一个语言 L的非交互证明系统（ P’,V’）
? 1,共同输入 x∈ {0,1}n。
? 2,共同参考序列为 s={s1,…,s m}，其中每个 si∈ {0,1}n。
? 3,证明者（记作 P’）的程序。
1)对每个 i∈ {1,…,m},计算 。
2)向 P要 。
3)输出 （ P’ 发送给 V’的消息），其中，,
。
? 4,验证者（记作 V’）的程序
1) 输入 P’输出的 后，对每个 ij∈ I，检验 是否
成立。若发现有一个不成立，则 V’停止和拒绝。
2) 计算,记 。
3) 向 V要输出 作为 V’的输出，即 V’接受当且仅当 V接
受。
))(( 1 ii sfbr ??
),(),,,(P 1 C erIrrx m ??
),,( IpCerI ? ??iiI,,1 ??
）－ ?? ppsfsfp iiI ?? 111 ())()(( 1 ?? ?
),,( IpCerI )(
ji pfs j ?
?,,1),( ??? ipbr ii ),,( 1 ?rrr ??
),,,(V C erIrx
语言 HC的隐比特零知识证明系统
? 1,共同输入 = G=(V,E)HC，其中 |V|=n。
? 2,共同参考序列看作一个 n3× n3矩阵 M，其元素为 1的概率为 n-5，元
素为 0的概率为 1-n-5。
? 3,证明者（记作 P）的程序。设 C为 G中的一个哈密尔顿圈。
1) 证明者考察矩阵 M，分如下两种情况。
? 情况一,M为有用。记 H为 M中的哈密尔顿 n× n子矩阵,CH为 H对应
的哈密尔顿圈。
2）证明者泄漏 M中除 H以外的所有 n6-n2个元素。
3）证明者计算出 (Φ1,Φ2)，其中 Φ1为 V到 H的行的 1-1映射,Φ2为 V
到 H的列的 1-1映射，使 G中的哈密尔顿圈 C上的边映射到 H中的元素 1，
即将任一有序顶点对 (u,v),u,v∈ V，映射到 H的 Φ1(u)行 Φ2(v)列的元
素。若 (u.v) ∈ C，则 H的 Φ1(u)行 Φ2(v)列的元素为 1，即映射
(Φ1,Φ2)是 C到 CH的一个同构。
4）证明者泄漏所有 (u,v) ∈ E对应的 H的 Φ1(u)行 Φ2(v)列的个元素。
5）证明者输出 (I,Cer),MI（ P发送给 V（验证者）的消息），其中，
Cer= (Φ1,Φ2), I为 P泄漏的 M中所有 n6-|E|个元素的位置,MI为 P
泄漏的 M中所有 n6-|E|个元素，都是 0。
? 情况二,M不为有用。
6）证明者只输出（ I,MI）（没有 Cer），其中 I为 M的所有 n6个元
素的位置,MI=M。
? 4,验证者（记作 V）的程序。
1）验证者输入证明者发送的（ I,Cer,MI），检查 M中除了 Φ1(u)
行 Φ2(v)的元素,(u,v) ∈ E外，其它元素是否都包含在 MI中，且都
为 0，若是则接受，否则拒绝。
2) 验证者输入 M，检查 M是否为有用，若不为有用则接受，否则拒
绝。
?定理 15.5 若单向置换存在，则每个 NP类语
言存在一个非交互零知识证明系统。
小结
?本章主要介绍了交互零知识证明系统和非
交互零知识证明系统的一些基本知识。
15.1 交互式零知识证明系统的定义
?交互图灵机作为证明者和验证者各自的计
算模型，将他们各自的交互图灵机连接起
来联合计算就构成一问一答的交互协议。
?定义 15.1 一个交互图灵机是一个（确定性）
多带图灵机。它具有下列带,1）一条只读
输入带； 2）一条只读随机带； 3）一条读
写工作带； 4）一条只写输出带； 5）一条
只读通信带和一条只写通信带； 6）一条仅
有一个小方格的读写开关带。
? 定义 15.2 二个交互图灵机连接在一起，若一个图灵机的
识别标记为 1而另一个图灵机的识别标记为 0，它们的输入
带合一，开关带合一，一个图灵机的只读通信带与另一图
灵机的只写通信带合一，反之前者的只写通信带与后者的
只读通信带合一，但两个图灵机的随机带，工作带和输出
带是分开的。一对连接起来的交互图灵机在初始时刻有共
同的输入，并置开关带的内容为 0。它们的联合计算程序
是一对形的有限或无限序列，其中一个形序列代表一个图
灵机的计算程序。序列中的每一对形总是有一个图灵机
（不必是同一个）工作而另一个图灵机休息。第一对形对
应于图灵机的初始状态，共同输入和开关带的内容 0。若
一个图灵机停机了但开关带的内容仍与它的识别标记相等，
称这时两个图灵机都已停机了，即计算在这一时刻终止。
两个图灵机的输出由这一时刻输出带的内容决定。
? 定义 15.3 设 A,B为连接起来的一对交互图灵机，设对每
一共同输入，它们的联合计算在有限步终止。记 (A,B)(x)
为共同输入 x联合计算终止时 B的输出。它是在 {0,1}中取值
的随机变量，即在联合计算终止时刻图灵机 B的只写头在
输出带所写的二进数。由于 A,B的随机输入满足随机数
约定，故 (A,B)(x)为随机变量。
? 定义 15.4 一个交互图灵机 A称为有时间复杂性
（正整数集），若它与每个交互图灵机 B连接起来和对每
个共同输入 x，它总是在 t(|x|)步内停机（与 A和 B的随机输
入无关，只要满足随机数约定即可）。特别若存在一个正
多项式 p(n)，使图灵机 A有时间复杂性 p(|x|)，则称图灵机
A是多项式时间的。
?? ? ZZt,
?定义 15.5 一对连接起来的交互图灵机（ P,V）称
为语言 L成员识别问题的交互（式省去）证明系统，
若 V是多项式时间的，且满足下列两个条件。
(1)完全性：对每个 x∈ L,(15.1）
(2)合理性：对每个 x∈ L和每个交互图灵机 B,B与 V
连接起来,或
（ 15.2）
?其中 V的输出 (P,V)(x)和 (B,V)(x)表示验证者是否接
受 x∈ L，输出 1表示接受 x∈ L，输出 0表示拒绝
x∈ L。
? ? 3/21)(VP(Pr ??x），
? ? 3/20)(VB(Pr ??x）,? ? 3/11)(VB(Pr ??x），
?定理 15.1 语言 L的成员识别问题属于 NP，
当且仅当它有一个交互证明系统具有下列
两个性质。
(1)交互是单向的（从证明者到验证者）。
(2)证明者和验证者都只用确定性算法（不出
错）。
? 定义 15.6 设（ P,V）为语言 L的交互证明系统（参看定义
15.5），称（ P,V）为语言 L的一个关于不诚实验证者的
交互完全零知识证明系统，若对每个多项式时间的交互图
灵机 V*，存在一个多项式时间的概率图灵机 M*，使对每
个 x∈ L，下面两个条件成立。
1)当 M*的输入为 x时，它以 2-p(|x|)的概率输出一个特殊符号，
记作 ⊥,即,其中 p(n)为任一固定的
正多项式。
2）记 m*(x)为一随机变量，其分布为 M*(x) ≠⊥ 的条件下
M*(x)的条件分布，即
再记 ViewP,V’(x)为共同输入 x时在 P与 V*交互（联合计算）
过程中从 V*的随机带读出的随机数以及 V*从 P收到的消息，
称为 V*的观察。
于是有 ViewP,V’(x)与 m*(x)是相同分布的随机变量。
M*称为 P与 V*交互的完善模拟器。
? ? |)(|* 2)(MPr xpx ????
? ? ? ? ? ? **** 10)(M|)(MPr)(Pr,,?????? ??? xxxm
?定义 15.7 设 (P,V)为语言 L的交互证明系统，
称 (P,V)为语言 L的一个关于不诚实验证者
的交互计算零知识证明系统，若对每个多
项式时间的交互图灵机 V*，存在一个多项
式时间的概率图灵机 M*，使随机变量族
与 是计算不可区分的
（参看定义 6.2）。
M*称为 P与 V*交互的模拟器。
? ? LV,P )(* ?xxV ie w ? ? L* )(M ?xx
?定义 15.8 设（ P,V）为语言 L的交互证明系统，
称（ P,V）为语言 L的一个关于不诚实验证者的
交互统计（几乎完全）零知识证明系统，若对每
个多项式时间的交互图灵机 V*，存在一个多项式
时间的概率图灵机 M*，使随机变量族
与 是统计接近的，即它们的变差距离
（ 15.3）
是 |x|的一个可忽略函数，即对每个正多项式 p(n)
及一切充分大的 |x|有 。
? ? LV,P )(* ?xxV ie w
? ? L* )(M ?xx
? ? ? ?
? ???
??????
*
*
1,0
*
V,P L,)(MPr)(Pr2
1)(
?
?? xxxV i e wx
|)(|/1)( xpx ??
?定义 15.9 设（ P,V）为语言 L的交互证明
系统，称（ P,V）为语言 L的一个关于诚实
验证者的交互计算零知识证明系统，若存
在一个多项式时间概率图灵机 M，使随机变
量族 与 是计算不可区分的
（参看定义 6.2）。
? ? LV,P )( ?xxView ? ? L)(M ?xx
15.2 交互零知识证明系统的构造
? （一）无向图的同构问题
? 1,共同输入为两个同构的图 G1=(V1,E1)和 G2=(V2,E2)。设 Φ为
G1到 G2的同构，即 Φ为从 V1到 V2的 1-1映射，使 (u,v) ∈ E1，当且仅
当 。
? 2,重复执行下列 3－ 6步 n次。
? 3,P按等概分布随机选择 V2的一个置换并构造图 G’=(V’,E’)，其中
,（ ）；
。 P将 G’=(V’,E’)发给 V。
? 4,V收到 P发送的图 G’=(V’,E’)后，按等概分布随机选择一个
σ ∈ {1,2},V将 σ 发送给 P，要求 P给出到 G’的同构。
? 5,若 P收到 V发送的 σ,则 P将 π 发送给 V，否则，即 σ ≠2，则 P将
发送给 V。
? 6,若 V收到 P发送的消息，记作 ψ,是 Gσ 到 G’的同构，则 V输出 1
（接受），否则 V输出 0（拒绝）。
2E))(),( ?vu ??（
? ?)(,),(),(V |V|21' 2uuu ??? ?? ? ?|V|212
2.,,V uuu ???
? ?2' E),()),(),((E ?? vuvu ??
)V)),(()(( 1???? uuu ??????
? 定理 15.2 上面给出的程序 GI是语言 GI的一个关于不诚实验
证者的交互完全零知识证明系统。更确切地说，它满足下
列性质。
1)若 x=（ G1,G2） ∈ GI（ G1与 G2同构），则
即验证者总是接受 x ∈ GI。
2)若 x=（ G1,G2） ∈ GI（ G1与 G2不同构），则对每个交互
图灵机 B
即对每一个可能的证明者 B与 V交互，验证者仍用 V的程序
4和 6，则验证者拒绝 x∈ GI的概率至少是 1/2。
3)对每个多项式时间的交互图灵机 V*，存在一个多项式时间
的概率图灵机 M*，当输入 x=（ G1,G2） ∈ GI时,
与 m*(x)是相同分布的随机变量（参看定义 15.6），其中，
证明者仍用 P的程序 3和 5。
? ? 11))(V,P(Pr ??x
? ? 2/10))(V,B(Pr ??x
)(*V,P xView
（二）二次剩余问题
? 1,共同输入为 N,x，其中 N为未知因子分解的 N=PQ,P,Q为
素数,x与 N互素,x∈ QR(N)
? 2,重复执行 3-6步「 logN」次（ N看作二进数表示）。
? 3,P按等概分布从 ZN*中随机选出一个 v，计算 y=v2(mod
N),P将 y发送给 V。
? 4,V 收到 P发送的 y后，按等概分布随机选择一个
σ ∈ {0,1},V将 σ 发送给 P。
? 5,P收到 V发送的 σ 后，计算,其中 u为 x的一个
模 N的平方根,P将 z发送给 V。
? 6,若 V收到 P发送的 z满足,则 V输出 1（接受），
否则 V输出 0（拒绝）。
)(m o dNvuz ??
)(m o d2 Nyxz ??
?定理 15.3 上面给出的程序 QR是语言 QR的一个关
于不诚实验证者的交互完全零知识证明系统。更
确切地说，它满足下列性质。
1)若 x∈ QR(N)，则
2)若 x∈ QR(N)，则对每个交互图灵机 B
或
3)对每个多项式时间的交互图灵机 V*，存在一个多
项式时间的概率图灵机 M*，当输入 x∈ QR(N)时，
与 m*(x)是相同分布的随机变量，其中，
证明者仍用 P的程序 3和 5。
? ? 11))(V,P(Pr ??x
? ? 2/10))(V,B(Pr ??x ? ? 2/11)(VP(Pr ??x），
)(*V,P xView
（三）子群成员问题
? 1.共同输入为 (N,l,α,β)，其中 α,β∈ ZN*,α ≠β,α 的阶
为 l。
? 2.重复执行 3－ 6步「 logN」次（ N看作二进数表示）。
? 3.P按等概分布从 {o,1,…,l -1}中随机选出一个 j，计算 r= α j
(mod N),P将 r发送给 V。
? 4.V收到 P发送的 r后，按等概分布随机选择一个 σ ∈ {0,1}，
V将 σ 发送给 P。
? 5.P收到 V发送的 σ 后，计算 h=j+ σ m(mod N)，其中 m=log
α β（ β的以 α 为底的离散对数）,P将 h发送给 V。
? 6.若 V收到 P发送的 h满足,则 V输出 1（接
受），否则 V输出 0（拒绝）。
)( m o d Nrh ??? ?
?定理 15.4 上面给出的程序 SM是语言 SM的
一个关于不诚实验证者的交互完全零知识
证明系统。
NP完全类问题的交互零知识证明系统 ——
图的 3-着色问题
? 1,共同输入为一可 3-着色的图 G=(V,E)。
? 2,重复执行下列 3－ 6步 |E|2次。
? 3,设 ψ 为图 G的一个 3-着色。 P按等概分布随机选择 {1,2,3}
的一个置换 π,并构造,即 Φ为图 G的一
个随机 3-着色（颜色的标记 1,2,3是随机的）。 P用 |V|
个保险箱，每个保险箱里放一个 Φ(u),u∈ V，将所有 |V|个
保险箱都发送给 V（验证者）。
? 4,V（验证者）按等概分布从 E中随机选出一条边 (u,v)，
将它发送给 P，要求检查 u和 v的着色。
? 5,P收到 V发送的 (u,v)后，将放有 Φ(u)和 Φ(v)的两个保
险箱的密码发送给 V。
? 6,V打开这两个保险箱，若他看到的是 {1,2,3}中两个不同
的数，则 V输出 1（接受），否则 V输出 0（拒绝）。
V) ),(()( ?? uuu ???
15.3 非交互零知识证明系统理论
? 定义 15.10 一对概率图灵机（ P,V）称为语言 L的非交互
证明系统，若 V是多项式时间的，且满足下列两个条件。
? 1）完全性：对每个 x∈ L,（ 15.4）
? 其中,x为（ P,V）的共同输入； R为（ P,V）的共同参
考序列，它是在 {0,1}p(|x|)中等概分布的随机序列,p(n)为
任一固定的正多项式； P(x,R)为 P发送给 V的消息（ P的输
出和 V的输入）。
? 2）合理性：对每个 L和每个交互图灵机 B
或 (15.5)
? 其中,表示验证者接受 L,
表示验证者拒绝 L。
? ? 3/21)),(P,,(VPr ??RxRx
? ? 3/20)),(B,,(VPr ??RxRx ? ? 3/11)),(B,,(VPr ??RxRx
1)),(B,,(V ?RxRx 0)),(B,,(V ?RxRx
?定义 15.11 一个语言 L的非交互证明系统
（ P,V）称为是计算零知识的，若存在一
正多项式 p(n)和一个多项式时间概率图灵机
M，使随机变量族 与
是计算不可区分的。 ? ? L|)(||)(| ),(P,,( ?xxpxp UxUx
? ? L)(M ?xx
?定义 15.12 一对概率图灵机（ P,V）称为语言 L
的隐比特证明系统，若 V是多项式时间的，且满
足下列两个条件。
1)完全性：对每个 x∈ L,
其中,为 P发送给 V的消息（ P的输出
和 V的输入）,Cer称为证明书,
为的指定位置集，称为泄漏的比特位置集,x为
（ P,V）的共同输入,R=r1,…r t是在 {0,1}p(|x|)中
等概分布的随机序列,为 R在指定位置
集 I上的子序列，称为泄漏的比特序列。
2)合理性：对每个 x∈ L和每个概率图灵机 B
或
其中,是 B发送给 V的消息（ B的输出和
V的输入）。
? ? 3/21),,,(VPr ??C erIRx I
),(P),( RxC e rI ?
? ? ? ?|)(|,,2,1,,1 xpiiI ?? ?? ?
?iiI rrR ?1?
? ? 3/20),,,(VPr ??C erIRx I ? ? 3/11),,,(VPr ??C erIRx I
),(B),( RxC e rI ?
?定义 15.13 一个语言 L的隐比特证明系统
（ P,V）称为是计算零知识的，若存在一
个多项式时间概率图灵机 M，使随机变量族
与 是计
算不可区分的。
? ? ? ? LL ),,,()),(P,,( ?? ? xIxI C erIRxRxRx ? ?)(M ?xx
构造一个语言 L的非交互证明系统（ P’,V’）
? 1,共同输入 x∈ {0,1}n。
? 2,共同参考序列为 s={s1,…,s m}，其中每个 si∈ {0,1}n。
? 3,证明者（记作 P’）的程序。
1)对每个 i∈ {1,…,m},计算 。
2)向 P要 。
3)输出 （ P’ 发送给 V’的消息），其中，,
。
? 4,验证者（记作 V’）的程序
1) 输入 P’输出的 后，对每个 ij∈ I，检验 是否
成立。若发现有一个不成立，则 V’停止和拒绝。
2) 计算,记 。
3) 向 V要输出 作为 V’的输出，即 V’接受当且仅当 V接
受。
))(( 1 ii sfbr ??
),(),,,(P 1 C erIrrx m ??
),,( IpCerI ? ??iiI,,1 ??
）－ ?? ppsfsfp iiI ?? 111 ())()(( 1 ?? ?
),,( IpCerI )(
ji pfs j ?
?,,1),( ??? ipbr ii ),,( 1 ?rrr ??
),,,(V C erIrx
语言 HC的隐比特零知识证明系统
? 1,共同输入 = G=(V,E)HC，其中 |V|=n。
? 2,共同参考序列看作一个 n3× n3矩阵 M，其元素为 1的概率为 n-5，元
素为 0的概率为 1-n-5。
? 3,证明者（记作 P）的程序。设 C为 G中的一个哈密尔顿圈。
1) 证明者考察矩阵 M，分如下两种情况。
? 情况一,M为有用。记 H为 M中的哈密尔顿 n× n子矩阵,CH为 H对应
的哈密尔顿圈。
2）证明者泄漏 M中除 H以外的所有 n6-n2个元素。
3）证明者计算出 (Φ1,Φ2)，其中 Φ1为 V到 H的行的 1-1映射,Φ2为 V
到 H的列的 1-1映射，使 G中的哈密尔顿圈 C上的边映射到 H中的元素 1，
即将任一有序顶点对 (u,v),u,v∈ V，映射到 H的 Φ1(u)行 Φ2(v)列的元
素。若 (u.v) ∈ C，则 H的 Φ1(u)行 Φ2(v)列的元素为 1，即映射
(Φ1,Φ2)是 C到 CH的一个同构。
4）证明者泄漏所有 (u,v) ∈ E对应的 H的 Φ1(u)行 Φ2(v)列的个元素。
5）证明者输出 (I,Cer),MI（ P发送给 V（验证者）的消息），其中，
Cer= (Φ1,Φ2), I为 P泄漏的 M中所有 n6-|E|个元素的位置,MI为 P
泄漏的 M中所有 n6-|E|个元素，都是 0。
? 情况二,M不为有用。
6）证明者只输出（ I,MI）（没有 Cer），其中 I为 M的所有 n6个元
素的位置,MI=M。
? 4,验证者（记作 V）的程序。
1）验证者输入证明者发送的（ I,Cer,MI），检查 M中除了 Φ1(u)
行 Φ2(v)的元素,(u,v) ∈ E外，其它元素是否都包含在 MI中，且都
为 0，若是则接受，否则拒绝。
2) 验证者输入 M，检查 M是否为有用，若不为有用则接受，否则拒
绝。
?定理 15.5 若单向置换存在，则每个 NP类语
言存在一个非交互零知识证明系统。
小结
?本章主要介绍了交互零知识证明系统和非
交互零知识证明系统的一些基本知识。
