第15章零知识证明
第15章 零知识证明
151交互式零知识证明系统的定义 交互图灵机作为证明者和验证者各自的计 算模型,将他们各自的交互图灵机连接起 来联合计算就构成一问一答的交互协议 ●定义15.1一个交互图灵机是一个(确定性) 多带图灵机。它具有下列带:1)一条只读 输入带;2)一条只读随机带;3)一条读 写工作带;4)一条只写输出带;5)一条 只读通信带和一条只写通信带;6)一条仅 有一个小方格的读写开关带
15.1 交互式零知识证明系统的定义 ⚫交互图灵机作为证明者和验证者各自的计 算模型，将他们各自的交互图灵机连接起 来联合计算就构成一问一答的交互协议。 ⚫定义15.1 一个交互图灵机是一个（确定性） 多带图灵机。它具有下列带：1）一条只读 输入带；2）一条只读随机带；3）一条读 写工作带；4）一条只写输出带；5）一条 只读通信带和一条只写通信带；6）一条仅 有一个小方格的读写开关带
●定义15.2二个交互图灵机连接在一起,若一个图灵机的 识别标记为1而另一个图灵机的识别标记为0,它们的输入 昃机的只写信帚合’,反前者的只考通信带与后者的 只读通信带 但两个图灵机的随机带,工作带和输出 营是分开的=对连搖起来的交互图灵机在初始卧裂有共 是一对形的有限或无限序列,其中一个形序列代表一个图 灵机的计算程序。序列中的每一对形总是有一个图灵机 不必是同…个)工作而 个图灵机休息。,第一对形对 应于图灵机的初始状态,共同输入和开关带的内容0。若 个图灵机停机了但开关带的内容仍与它的识别标记相等, 两个图灵机的输出由这一时刻输出带的内容决。到终止 称这时两个图灵机都已停机了:,即 在这
⚫ 定义 15.2 二个交互图灵机连接在一起，若一个图灵机的 识别标记为1而另一个图灵机的识别标记为0，它们的输入 带合一，开关带合一，一个图灵机的只读通信带与另一图 灵机的只写通信带合一，反之前者的只写通信带与后者的 只读通信带合一，但两个图灵机的随机带，工作带和输出 带是分开的。一对连接起来的交互图灵机在初始时刻有共 同的输入，并置开关带的内容为0。它们的联合计算程序 是一对形的有限或无限序列，其中一个形序列代表一个图 灵机的计算程序。序列中的每一对形总是有一个图灵机 （不必是同一个）工作而另一个图灵机休息。第一对形对 应于图灵机的初始状态，共同输入和开关带的内容0。若 一个图灵机停机了但开关带的内容仍与它的识别标记相等， 称这时两个图灵机都已停机了，即计算在这一时刻终止。 两个图灵机的输出由这一时刻输出带的内容决定
定义15.3设A,B为连接起来的一对交互图灵机,设对每 一共同输入,它们的联合计算在有限步终止。记A,B)(x) 为共同输入x联合计算终止时B的输出。它是在{0,1}中取值 的随机变量,即在联合计算终止时刻图灵机B的只写头在 输出带所写的二进数。由于A,B的随机输入满足随机数 约定,故(A,B)(x)为随机变量。 定义154一个交互图灵机A称为有时间复杂性t:z+→Z+ (正整数集),若它与每个交互图灵机B连接起来和对每 个共同输入X,它总是在(x)步内停机(与A和B的随机输 入无关,只要满足随机数约定即可)。特别若存在一个正 多项式p(n),使图灵机A有时间复杂性p(),则称图灵机 A是多项式时间的
⚫ 定义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是多项式时间的。 + → + t : Z Z
●定义155一对连接起来的交互图灵机(P,V)称 为语言L成员识别问题的交互(式省去)证明系统, 若Ⅴ是多项式时间的,且满足下列两个条件。 (1)完全性:对每个x∈L, (151) (2)合理性:对每个X∈L科球壁图捷稅B,B与V 连接起来, 或 Pr{(B,x)=0}≥2/3(1592N)x)=≤1/3 ●其中V的输出(P,v)()和(B,)(xX)表示验证者是否接 受x∈L,输出1表示接受x∈L,输出0表示拒绝 X∈L
⚫ 定义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。 Pr(P，V）(x) =1 2/3 Pr(B，V）(x) = 0 2/3 Pr(B，V）(x) =11/3
●定理151语言L的成员识别问题属于NP, 当且仅当它有一个交互证明系统具有下列 两个性质 (1)交互是单向的(从证明者到验证者) (2)证明者和验证者都只用确定性算法(不出 错)
⚫定理15.1 语言L的成员识别问题属于NP， 当且仅当它有一个交互证明系统具有下列 两个性质。 (1)交互是单向的（从证明者到验证者）。 (2)证明者和验证者都只用确定性算法（不出 错）
定义156设(P,V)为语言L的交互证明系统(参看定义 155),称(P,V)为语言的一个关于不诚实验证者的 夯高宾全零架识诞明系终:着对每多项霜时间怕交图 个X∈L,下面两个条件成立。 1)当M的输入为刈时;,它以2的概率输出一个特殊符 记作⊥,即PM(x)=12,其中p(n)为任一固定的 正多项式。 2)记m*(∞)为一随机变量,其分布为M*x)≠⊥的条件下 Mt)条件分布,即Pv7(x)=a)=PrMx=aiM(x)≠}a∈o 再记eWv(X)为共同输入对时在P与∨交互(联合计算) 过程中从∨的随机带读出的随机数以及V从P收到的消息, 称为V的观察 于是有vewp(x)与m*(x)是相同分布的随机变量。 M*称为P与V交互的完善模拟器
⚫ 定义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*交互的完善模拟器。 * (| |) Pr M ( ) 2 p x x − =⊥ * * * * Pr m (x) = = Pr M (x) = | M (x) ⊥ ， 0，1
●定义157设P,V为语言L的交互证明系统, 称(P,V)为语言L的一个关于不诚实验证者 的交互计算零知识证明系统,若对每个多 项式时间的交互图灵机V,存在一个多项 式时间的概率图灵机M*,使随机变量族 pery(x)b与M(x)}是计算不可区分的 (参看定义6.2)。 M称为P与V交互的模拟器
⚫定义15.7 设(P，V)为语言L的交互证明系统， 称(P，V)为语言L的一个关于不诚实验证者 的交互计算零知识证明系统，若对每个多 项式时间的交互图灵机V*，存在一个多项 式时间的概率图灵机M*，使随机变量族 与 是计算不可区分的 （参看定义6.2）。 M*称为P与V*交互的模拟器。 P,V L * ( ) x View x L * M ( ) x x
定义15.8设(P,V)为语言L的交互证明系统, 称(P,V)为语言L的一个关于不诚实验证者的 交互统计(几乎完全)零知识证明系统,若对每 个多项式时间的交互图灵机V,存在一个多项式 时间的概率图灵机M,使随机变量族e"ry(x) 与M(x)是统计接近的,即它们的变差距离 2 Prkiewpy.(x)=a)(M(x)=axEL (15.3 a∈0, 是风的一个可忽略函数,即对每个正多项式p(n 及一切充分大的×有△(x)<1/mx)
⚫ 定义15.8 设（P，V）为语言L的交互证明系统， 称（P，V）为语言L的一个关于不诚实验证者的 交互统计（几乎完全）零知识证明系统，若对每 个多项式时间的交互图灵机V*，存在一个多项式 时间的概率图灵机M*，使随机变量族 与 是统计接近的，即它们的变差距离 （15.3） 是|x|的一个可忽略函数，即对每个正多项式p(n) 及一切充分大的|x|有 。 P,V L * ( ) x View x L * M ( ) x x = = − = * * 0,1 * P,V Pr ( ) Pr M ( ) , L 2 1 ( ) x View x x x (x) 1/ p(| x |)
●定义159设(P,V)为语言L的交互证明 系统,称(P,V)为语言的一个关于诚实 验证者的交互计算零知识证明系统,若存 在一个多项式时间概率图灵机M,使随机变 量族a(x)与Mx是计算不可区分的 (参看定义62)
⚫定义15.9 设（P，V）为语言L的交互证明 系统，称（P，V）为语言L的一个关于诚实 验证者的交互计算零知识证明系统，若存 在一个多项式时间概率图灵机M，使随机变 量族 与 是计算不可区分的 （参看定义6.2）。 P,V L ( ) x View x L M( ) x x