●定理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 |)