当前位置：文档之家 › 第15章 零知识证明

第15章 零知识证明

  • 格式：ppt
  • 大小：203.50 KB
  • 文档页数：26

下载文档原格式

  / 26

合集下载

离散对数零知识证明

离散对数零知识证明

离散对数零知识证明
零知识证明是指证明者可以向验证者证明某个断言是真实的，但是在这个过程中不泄露任何关于这个断言的额外信息。

离散对数零知识证明结合了这两个概念，可以用来证明一个人知道某个离散对数而不泄露这个离散对数的具体值。

在离散对数零知识证明中，通常会使用类似于费马小定理或者椭圆曲线离散对数等数学原理。

证明的过程中，证明者会向验证者展示一系列与离散对数相关的数学计算，而验证者则根据这些计算来验证断言的真实性，但是并不会得知具体的离散对数值。

离散对数零知识证明在密码学中有着重要的应用，例如在身份认证、电子现金系统和数字签名等领域。

它可以帮助确保信息的安全性和隐私性，同时也能够防止欺骗和伪造。

总的来说，离散对数零知识证明是一种重要的密码学概念，它结合了离散对数问题和零知识证明的特点，能够在信息安全领域发挥重要作用。

通过合理的数学原理和算法设计，离散对数零知识证明可以有效地保护信息的安全性和隐私性，是密码学领域中的重要研究课题之一。

信息安全-知识的零知识证明

信息安全-知识的零知识证明

我们表示知识的零知识证明是一个证明者通过使一个论述的P 满足于PoK{(a1,a2......an)|P(a1,........an)}使得一个核实者信服。

这个概念是从Camenish和Stadler上汲取过来的（修改他们的理论使得PoK代替PK）。

B、主要的架构我们把知识的零知识证明当做是在构造块以及以单独的模块来描述它们。

知识的零知识证明显示这里的非交互式证明在随机预言模块是安全的。

在这个安全的证明里，我们表示这些协议的交互式模式的使用是不需要依靠随机预言模块并且能够使零知识使用协议的正常执行，这也就意味着零知识证明的顺序执行。

当交互式的知识的零知识证明用Fiat-Shamir 启发式理论在随机预言模式下实例化和协议在同时执行时，我们的证明就因为技术的原因被瓦解了，但是我们任然将我们的证明当做是为了执行的安全儿做的启发式的证明。

构建（spk,ssk,σ）服务器在Zq集合中选择x,y,z以及使得X=g^x,Y=g^y,Z=g^z.这个服务公共秘钥是spk=(q，G，GT，g, X，Y，Z)，服务的私有秘钥是ssk=(x,y,z).服务器的状态σ是由一对集合组成。

它们初始化状态下是为NULL。

就像这样σ=（{}，{}）。

我们把第一个组件成为σ.cur以及第二个组件称为σ.next.在所有的组件中，cur=|σ.cur|,next=|σ.next|。

注册：（φ，sk）←<RegS(ssk),RegC(spk)>1、客户端选择从Zq处选择d,r.用它们来构建M=(g^d)*(Z^r)并且将他们送到服务器端。

2、这个客户端以证明着的角色以及服务器端以核实者的角色存在与知识的零知识证明。

PoK{（d,r）|M=(g^d)*(Z^r)}.如果上述证明失败，则注册失败。

3、服务器端从Zq*产生一个a值，并且使得A=g^a.然后它形成了这个注册号s=(A,B=A^y,Zb=Z^ay(=B^z),C=(A^x)*(M^axy)并且将产生的注册号返回给客户端。

九年级上册第15章知识点

九年级上册第15章知识点

九年级上册第15章知识点本章主要讲述了九年级上册的一些重要知识点，包括数学、物理、化学、生物等多个学科的内容。

下面将逐一介绍这些知识点。

一、数学知识点1. 代数方程与不等式：本节主要介绍一元一次方程、一元一次不等式以及它们的解法和应用。

2. 平面几何：该部分涵盖平面图形的性质、面积与周长的计算，以及平行线、垂直线、相交线的基本判断方法。

3. 数据与统计：学习如何收集数据、整理数据以及利用图表来进行数据分析和统计。

二、物理知识点1. 力学：介绍物体的力、速度、加速度等基本概念，以及力的合成与分解、牛顿第二定律等内容。

2. 光学：学习光的传播规律、光的反射、折射以及透镜成像原理等基础知识。

3. 热学：了解物体的热平衡、热传导、热膨胀等内容。

三、化学知识点1. 元素、化合物与混合物：学习元素、化合物和混合物的定义、区别以及各自的特点。

2. 酸碱中和反应：了解酸碱中和反应的概念、特征和应用，以及中和反应的判断方法。

3. 氧化还原反应：介绍氧化还原反应的概念、性质和应用，学习如何判断氧化还原反应并进行电荷的平衡。

四、生物知识点1. 生物的多样性：了解生物的分类，学习如何根据生物的特征进行分类以及物种的命名。

2. 生物的进化：介绍生物的进化理论，了解进化的证据和适应性进化的原理。

3. 生物的遗传与变异：学习基因的概念、遗传规律以及基因突变的原因和影响。

总结：本章内容涵盖了数学、物理、化学和生物等学科的知识点，对学生的综合素质提升至关重要。

通过学习这些知识，学生将能够更好地理解和应用所学的科学知识，并为将来的学习打下坚实的基础。

希望同学们能够认真学习、掌握这些知识点，取得优异的成绩！。

零知识证明

零知识证明

在最小泄露协议中零知识证明需要满足下述两个性质。 (1)正确性。P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。 (2)完备性。V无法欺骗P。若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。 在零知识协议中，除满足上述两个条件以外，还满足下述的第三个性质。 (3)零知识性。V无法获取任何额外的知识。 我们把性质(1)和(2)称为零知识证明的正确性和完备性，而性质(3)称为零知识性。
设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。假如某个协议向V证明P的 确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。不仅如此，如果V除了知道P能 够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。
性质
引入
顾名思义，零知识证明就是既能充分证明自己是某种权益的合法拥有者，又不把有关的信息泄露出去——即 给外界的“知识”为“零”。其实，零知识证明并不是什么新东西，早在16世纪的文艺复兴时期，意大利有两位 数学家为竞争一元三次方程求根公式发现者的桂冠，就采用了零知识证明的方法。当时，数学家塔尔塔里雅和菲 奥都宣称自己掌握了这个求根公式，为了证明自己没有说谎，又不把公式的具体内容公布出来(可能在当时数学公 式也是一种技术秘密)，他们摆开了擂台：双方各出30个一元三次方程给对方解，谁能全部解出，就说明谁掌握 了这个公式。比赛结果显示，塔尔塔里雅解出了菲奥出的全部30个方程，而菲奥一个也解不出。于是人们相信塔 尔塔里雅是一元三次方程求根公式的真正发现者，虽然当时除了塔尔塔里雅外，谁也不知道这个公式到底是个什 么样子。从这个故事，我们可以初步了解零知识证明的概念。
属性
零知识证明需要满足三个属性。 1、如果语句为真，诚实的验证者（即：正确遵循协议的验证者）将由诚实的证明者确信这一事实。 2、如果语句为假，不排除有概率欺骗者可以说服诚实的验证者它是真的。 3、如果语句为真，证明者的目的就是向验证者证明并使验证者相信自己知道或拥有某一消息，而在证明过程 中不可向验证者泄漏任何有关被证明消息的内容。 零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗者有可能通过虚假陈述骗过证明者。 换句话来说，零知识证明是概率证明而不是确定性证明。但是也存在有技术能将误差降低到可以忽略的值。 零知识的形式定义必须使用一些计算模型，最常见的是图灵机的计算模型。

零知识证明研究综述

零知识证明研究综述

DCWTechnology Analysis技术分析79数字通信世界2023.061 零知识证明的概念零知识证明是某种权益的拥有者，即知道问题的解w 的人在不泄露任何有关问题的相关信息的情况下，能证明其确实掌握有w 。

1.1 注解我们有两个角色方，证明者（简称P ）和验证者（简称V ），以及对两个角色方来说不是秘密的NP 关系R 、问题x 及答案w 这三个对象满足公式：R (x ,w )=1 （1）证明者知道问题的答案x ，他需要向验证者证明他知道问题x 以及问题的答案w ，但不泄露关于w 的任何信息。

以上描述等价于证明满足以下三个属性：（1）完备性。

此证明完成后能够让验证者确信证明者没有说谎，或者说证明者确实握有问题x 的某个解w 。

（2）合理性。

证明者不拥有x 的某个解w ，则不能令验证者相信他拥有问题x 的某个解。

（3）零知识性。

证明过程不能泄露关于w 的任何信息。

下面给出零知识证明这一概念的较为数学化的定义。

1.2 定义考虑等式R (x ,w )=1，这里x 是一个数学问题，w是该问题的未知的解，也即w 满足x 所定义的若干关系，R 是判断w 是否满足这些关系的判定程序，我们还要求R (x ,w )=1是一个NP 问题，即求解w 很难，但验证w 是该问题的解是容易的。

1.3 注解在这里，容易和困难的界定是由算法的时间复杂度决定的，即能否能在多项式时间内解决问题，即算法的时间复杂度是否低于多项式的维度。

对早期的零知识证明的协议来说，很多是必须要求证明是某种交互输入，例如下节给出的三色问题的一个零知识证明方案。

这种交互式证明是从概率角度零知识证明研究综述张正铨1，胡 森1，莫晓康 1, 2（1.中国科学技术大学，安徽 合肥 230026；2.国科创新研究院（厦门）有限公司，福建 厦门 361021）摘要：文章论述了密码学的新领域——零知识证明的概念、方法、算法、应用，以及其在区块链领域的若干应用。

零知识证明技术的实际应用与安全性分析

零知识证明技术的实际应用与安全性分析

零知识证明技术的实际应用与安全性分析零知识证明技术是一种用于验证某个声明的正确性，同时不泄露任何有关该声明的其他信息的密码学工具。

该技术可被广泛应用于许多领域，例如密码学、网络安全、隐私保护和区块链等。

本文将探讨零知识证明技术的实际应用，并分析其安全性。

一、实际应用1.密码学领域：零知识证明技术可用于验证公钥加密方案的安全性。

例如，可以证明一种加密算法的秘钥长度满足安全要求，而不泄露该算法的具体细节。

2.网络安全：在网络通信中，确保通信的安全性非常重要。

零知识证明技术可以用于验证用户的身份，从而防止恶意用户的欺骗行为。

通过使用零知识证明技术，服务器可以证明其拥有某个秘密，而不需要直接揭示该秘密。

3.隐私保护：在很多情况下，用户不希望将其个人信息披露给他人，同时又需要验证某些声明的真实性。

零知识证明技术可以满足这一需求。

例如，在数字身份验证中，用户可以使用零知识证明技术证明自己的年龄在某个范围内，而不需要透露具体的年龄。

4.区块链：区块链是一种去中心化的分布式账本技术，而零知识证明技术可以用于增强其隐私性和安全性。

通过使用零知识证明技术，参与方可以证明自己满足某个条件，而不需要公开其具体数据。

这在一些隐私敏感的应用中尤为重要，例如匿名交易和身份验证。

二、安全性分析1.完备性：零知识证明技术必须保证如果声明是正确的，那么验证者相信该声明的概率非常高。

这意味着证明者必须能够生成一个有效的证明，并将其传递给验证者。

从理论上来说，完备性要求能够通过一个无限容量的计算设备进行检查。

2.可靠性：零知识证明技术应该确保如果甲方是一个诚实的证明者，那么乙方不会被欺骗相信一个错误的声明。

也就是说，诚实的证明者不会能够通过生成错误的证明来欺骗验证者。

3.零知识性：零知识证明技术应该确保验证者不能从证明者提供的信息中获得任何与声明相关的附加信息。

也就是说，验证者在验证声明的真实性时只能得知声明的真实性，而不能获得与其相关的其他信息。

区块链技术在公共服务中的应用

区块链技术在公共服务中的应用第一章：区块链技术在公共服务概述 (2)1.1 区块链技术简介 (2)1.2 公共服务领域概述 (2)1.3 区块链技术与公共服务的结合 (3)第二章：区块链在公共安全领域的应用 (3)2.1 身份认证与信息保护 (3)2.2 数据加密与隐私保护 (4)2.3 智能合约在公共安全中的应用 (4)第三章：区块链在公共医疗领域的应用 (5)3.1 电子病历与数据共享 (5)3.2 药品追溯与防伪 (5)3.3 医疗保险与理赔 (6)第四章：区块链在公共交通领域的应用 (6)4.1 车辆管理与服务 (6)4.2 车辆保险与理赔 (6)4.3 公共交通数据共享与分析 (7)第五章：区块链在公共教育领域的应用 (7)5.1 学历证明与证书管理 (7)5.2 教育资源共享与协作 (8)5.3 教育投资与融资 (8)第六章：区块链在公共就业领域的应用 (8)6.1 求职者身份认证与信息保护 (8)6.2 招聘流程优化与合同管理 (9)6.3 劳动关系与社会保障 (9)第七章：区块链在公共资源管理领域的应用 (9)7.1 资源分配与调度 (10)7.2 公共资源交易与监管 (10)7.3 公共资源数据共享与分析 (10)第八章：区块链在环境保护领域的应用 (11)8.1 环保数据监测与管理 (11)8.2 环保项目融资与投资 (11)8.3 环保政策制定与执行 (12)第九章：区块链在公共安全监管领域的应用 (12)9.1 安全预警与处理 (12)9.2 安全信息共享与协同 (13)9.3 安全监管政策制定与执行 (13)第十章：区块链在公共基础设施领域的应用 (14)10.1 基础设施投资与融资 (14)10.2 基础设施建设与维护 (14)10.3 基础设施数据共享与分析 (14)第十一章：区块链在公共文化活动领域的应用 (15)11.1 文化活动组织与管理 (15)11.2 文化资源保护与传承 (15)11.3 文化产业投资与融资 (16)第十二章：区块链在公共服务领域的挑战与前景 (16)12.1 技术与安全挑战 (16)12.2 法律与政策挑战 (17)12.3 发展前景与趋势 (17)第一章：区块链技术在公共服务概述1.1 区块链技术简介区块链技术，作为一种新兴的分布式账本技术，近年来在全球范围内引发了广泛关注。

《零知识证明》PPT课件


过程中，B始终不能看到钥匙的样子，从而避
免了钥匙的泄露。
精选PPT
3
❖ 零知识证明实质上是一种涉及两方或更多 方的协议，即两方或更多方完成一项任务 所需采取的一系列步骤。零知识证明必须 包括两个方面，一方为证明者P，另一方 为验证者V。证明者试图向验证者证明某 个论断是正确的，或者证明者拥有某个知 识，却不向验证者透露任何有用的消息。 零知识证明目前在密码学中得到了广泛的 应用，尤其是在认证协议、数字签名方面。
精选PPT
14
❖ Goldwasser等人提出的零知识证明是交 互式的，也就是证明者和验证者之间必 须进行双向对话，才能实现零知识性， 因而称为交互零知识证明。
精选PPT
15
❖ 在交互零知识证明的研究中，目前受到关注的
有两种基本模型。一种是GMR模型，在这种模
型中，证明者具有无限的计算能力，验证者具
中心 TA 签名的有效性；
3、 验证者 B 选择一个随机整数 e Zb ，并将其发给识别者 A；
4、 识别者 A 计算 y rme mod n ，并将其发送给验证者 B；
5、 验证者 B 通过计算 X ve yb mod n 来验证身份信息的有效性。
可以看出，Guillou-Quisquater 身份认证协议的安全性与 RSA 公钥密码体
精选PPT
10
Hamilton回路零知识协议
❖ 许多计算上困难的问题可以用来构造零知识 协议。
❖ 在图论中，图 G中的回路是指始点和终点相 重合的路径，若回路通过图的每个顶点一次 且仅一次，则称图 G为哈密尔顿回路，构造 图 G的哈密尔顿回路是 NPC 问题。
精选PPT
11
❖ 假定 P知道图 G的哈密尔顿回路，并希望向 V证明这一事实，可采用如下协议：

零知识证明的定义和作用

零知识证明的定义和作用小伙伴们！今天咱来聊聊零知识证明这个挺有意思的玩意儿哈。

一、零知识证明的定义。

零知识证明呀，简单来说，就是一种特殊的证明方法。

想象一下哈，你想向别人证明你知道某个秘密，但是呢，你又不想把这个秘密具体内容透露出去，这时候零知识证明就派上用场啦。

打个比方吧，就好比你有一把神奇的钥匙，能打开一个特别的宝箱。

你想让别人知道你有这把钥匙，也就是你知道怎么打开宝箱，但你又不想把钥匙给别人看或者告诉别人钥匙长啥样。

那怎么办呢？通过零知识证明的方法，你可以在不展示钥匙的情况下，让别人相信你确实有打开宝箱的能力。

从专业一点的角度来讲呢，零知识证明是一种密码学技术。

它允许证明者在不向验证者透露任何有用信息的情况下，证明某个陈述是真实的。

就好像你在跟别人玩一个猜谜游戏，你能让对方相信你知道答案，但又不把答案直接告诉对方。

这种技术在很多领域都有很重要的应用哦。

二、零知识证明的作用。

1. 保护隐私。

这可是零知识证明一个超级重要的作用哈。

在当今这个信息爆炸的时代，隐私保护变得越来越重要啦。

比如说，你在网上进行一些交易或者登录某些平台的时候，平台可能需要验证你的身份或者确认你有没有某种权限。

传统的方法可能就需要你提供很多个人信息，像身份证号、密码啥的。

但是有了零知识证明，你就可以在不透露这些敏感信息的情况下，让平台相信你是合法的用户。

就好比你去住酒店，不用把家里的钥匙给前台看，就能证明你是这个房间的主人，是不是很酷呀？2. 增强安全性。

在网络安全方面，零知识证明也发挥着巨大的作用哦。

比如说，在区块链技术中，很多交易需要验证身份和交易的合法性。

如果使用传统的验证方法，可能会存在信息泄露的风险，黑客就有可能利用这些漏洞进行攻击。

但是零知识证明可以在不泄露交易细节的情况下，确保交易的合法性和安全性。

这就像是给你的交易上了一把隐形的锁，只有合法的人才能打开，其他人就算知道有这把锁，也不知道怎么开。

3. 提高效率。

零知识身份认证

4．零知识身份认证零知识证明（zero-knowledge proof）的思想是：证明者Peggy拥有某些知识（如某些长期没有解决的难问题的解决方法），零知识证明就是在不将该知识的内容泄露给验证者Victor的前提下，Peggy向Victor证明自己拥有该知识。

首先，我们看下面Peggy和Victor之间的一段对话：Peggy：“我可以对密文为C的消息进行解密。

”Victor：“我不相信。

请证明。

”Peggy（糟糕的回答）：“密钥是K，您可以看到消息解密成了M。

”Victor：“哈哈！现在我也知道了密钥和消息。

”这里，Peggy虽然证明了自己拥有某些知识（密钥K及明文M），却向Victor 泄露了这些知识。

一个更好的对话是：Peggy：“我可以对加密为C的消息进行解密。

”Victor：“我不相信。

请证明。

”Peggy（好的回答）：“让我们使用一个零知识协议，我将以任意高的概率证明我的知识（但是不会将关于消息的任何情况泄露给您）。

”Victor：“好”。

Peggy 和 Victor 通过该协议……可以使用洞穴例子来解释零知识，C和D之间存在一个密门，并且只有知道咒语的人才能打开。

Peggy知道咒语并想对Victor证明，但证明过程中不想泄露咒语。

图7.13 零知识洞穴步骤如下：（1）Victor站在A点；（2）Peggy一直走进洞穴，到达C点或者D点；（3）在Peggy消失在洞穴中之后，Victor走到B点；（4）Victor随机选择左通道或者右通道，要求Peggy从该通道出来；（5）Peggy从Victor要求的通道出来，如果有必要就用咒语打开密门；（6）Peggy和Victor重复步骤（1）至（5）n次。

如果Peggy不知道这个咒语，那么只能从进去的路出来，如果在协议的每一轮中Peggy都能按Victor要求的通道出来，那么Peggy所有n次都猜中的概率是1/2n。

经过16轮后，Peggy只有65536分之一的机会猜中。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
σ∈{0,1}，V将σ发送给P。 5. P收到V发送的σ后，计算z u v(mod N)，其中u为x的一个
模N的平方根，P将z发送给V。 6. 若V收到P发送的z满足z2 x y(mod ，N) 则V输出1（接受），
否则V输出0（拒绝）。
定理15.3 上面给出的程序QR是语言QR的一个关 于不诚实验证者的交互完全零知识证明系统。更 确切地说，它满足下列性质。
记作⊥，即
PrM* (x) 2 p(|x|)，其中p(n)为任一固定的
正多项式。
2）记m*(x)为一随机变量，其分布为M*(x) ≠⊥的条件下
M*(x)的条件分布，即 Pr m* (x) Pr M* (x) | M* (x) ， 0，1*
再过记程V中ie从wVP,*V的’(x随)为机共带同读输出入的x时随在机P数与以V及*交V互*从（P联收合到计的算消）息， 称为V*的观察。
1. 共同输入为两个同构的图G1=(V1，E1)和G2=(V2，E2)。设Φ为
G1到G2的同构，即Φ为从V1到V2的1-1映射，使(u,v) ∈E1，当且仅
当（
(u),
(v))
E
。
2
2. 重复执行下列3－6步n次。
3. P按等概分布随机选择V2的一个置换并构造图G’=(V’，E’)，其中
V'
V）称为是计算零知识的，若存在一正多项
式p(n)和一个多项式时间概率图灵机M，使
随机变量族 不可区分的。
与 是计算 (x,U p(|x|), P(x,U p(|x|) ) xL M(x) xL
定义15.12 一对概率图灵机（P，V）称为语言L 的隐比特证明系统，若V是多项式时间的，且满 足下列两个条件。
即验证者总是接受x ∈GI。 2)若x=（G1，G2）∈GI（G1与G2不同构），则对每个交互
图灵机B Pr(B, V)(x) 0 1/ 2
即对每一个可能的证明者B与V交互，验证者仍用V的程序 4和6，则验证者拒绝x∈GI的概率至少是1/2。 3)对每个多项式时间的交互图灵机V*，存在一个多项式时间 的与概m*率(x图)是灵相机同M分*，布当的输随入机x变=（量G（1参，看G定2）义∈15G.I6时），，Vie其wP,中V* (x，) 证明者仍用P的程序3和5。
V将σ发送给P。 5.P收到V发送的σ后，计算h=j+ σm(mod N)，其中m=log
αβ（β的以α为底的离散对数），P将h发送给V。 6.若V收到P发送的h满足 h r(mod N) ，则V输出1（接
受），否则V输出0（拒绝）。
定理15.4 上面给出的程序SM是语言SM的 一个关于不诚实验证者的交互完全零知识 证明系统。
定义 15.2 二个交互图灵机连接在一起，若一个图灵机的 识别标记为1而另一个图灵机的识别标记为0，它们的输入 带合一，开关带合一，一个图灵机的只读通信带与另一图 灵机的只写通信带合一，反之前者的只写通信带与后者的 只读通信带合一，但两个图灵机的随机带，工作带和输出 带是分开的。一对连接起来的交互图灵机在初始时刻有共 同的输入，并置开关带的内容为0。它们的联合计算程序 是一对形的有限或无限序列，其中一个形序列代表一个图 灵机的计算程序。序列中的每一对形总是有一个图灵机 （不必是同一个）工作而另一个图灵机休息。第一对形对 应于图灵机的初始状态，共同输入和开关带的内容0。若 一个图灵机停机了但开关带的内容仍与它的识别标记相等， 称这时两个图灵机都已停机了，即计算在这一时刻终止。 两个图灵机的输出由这一时刻输出带的内容决定。
其中V的输出(P,V)(x)和(B,V)(x)表示验证者是否接 受x∈L，输出1表示接受x∈L，输出0表示拒绝 x∈L。
定理15.1 语言L的成员识别问题属于NP， 当且仅当它有一个交互证明系统具有下列 两个性质。
(1)交互是单向的（从证明者到验证者）。
(2)证明者和验证者都只用确定性算法（不出 错）。
定义15.3 设A，B为连接起来的一对交互图灵机，设对每 一共同输入，它们的联合计算在有限步终止。记(A,B)(x) 为共同输入x联合计算终止时B的输出。它是在{0,1}中取值 的随机变量，即在联合计算终止时刻图灵机B的只写头在 输出带所写的二进数。由于A，B的随机输入满足随机数 约定，故(A,B)(x)为随机变量。
6. 若V收到P发送的消息，记作ψ，是Gσ到G’的同构，则V输出1 （接受），否则V输出0（拒绝）。
定理15.2 上面给出的程序GI是语言GI的一个关于不诚实验 证者的交互完全零知识证明系统。更确切地说，它满足下 列性质。
1)若x=（G1，G2）∈GI（G1与G2同构），则 Pr(P, V)(x) 1 1
NP完全类问题的交互零知识证明系统—— 图的3-着色问题
1. 共同输入为一可3-着色的图G=(V，E)。 2. 重复执行下列3－6步|E|2次。 3. 设ψ为图G的一个3-着色。P按等概分布随机选择{1,2,3}
的一个置换π，并构造(u) ( (u)),u V，即Φ为图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（拒绝）。
（三）子群成员问题
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}，
1)完全性：对每个x∈L，PrV(x, RI , I,Cer) 1 2 / 3
其中，(I,Cer) P(x, R) 为P发送给V的消息（P的输出 和V的输入），Cer称为证明书，I i1, ,i 1,2, , p(| x |) 为的指定位置集，称为泄漏的比特位置集，x为 （等集P概I上，分的V布子）的序的随列共机，同序称输列为入，泄，漏RRI=的r1r比i1,…特rrit序是为列在R在。{0指,1}定p(|x位|)中置 2)合理性：对每个x∈L和每个概率图灵机B PrV(x, RI , I,Cer) 0 2 / 3 或 PrV(x, RI , I,Cer) 1 1/ 3 其中，(I,Cer) B(x, R)是B发送给V的消息（B的输出和 V的输入）。
定义15.4 一个交互图灵机A称为有时间复杂性t : Z Z （正整数集），若它与每个交互图灵机B连接起来和对每 个共同输入x，它总是在t(|x|)步内停机（与A和B的随机输
入无关，只要满足随机数约定即可）。特别若存在一个正 多项式p(n)，使图灵机A有时间复杂性p(|x|)，则称图灵机 A是多项式时间的。
定义15.6 设（P，V）为语言L的交互证明系统（参看定义 15.5），称（P，V）为语言L的一个关于不诚实验证者的 交互完全零知识证明系统，若对每个多项式时间的交互图 灵机V*，存在一个多项式时间的概率图灵机M*，使对每 个x∈L，下面两个条件成立。
1)当M*的输入为x时，它以2-p(|x|)的概率输出一个特殊符号，
时间的概率图灵机M*，使随机变量族 ViewP,V* (x)
与 M* (x) xL 是统计接近的，即它们的变差距离
xL
(x)
1 2 0,1*
Pr
ViewxL
（15.3）
是|x|的一个可忽略函数，即对每个正多项式p(n)
及一切充分大的|x|有 (x) 1/ p(| x |) 。
E'
(u1),
( (u),
(u2 ), ,
(v)), (u, v)
(u|V2 E
|2)， 。P（将 GV’2=(Vu’，1, uE2’,)发.u给|V2V| 。）；
4. V收到P发送的图G’=(V’，E’)后，按等概分布随机选择一个 σ∈{1,2}，V将σ发送给P，要求P给出到G’的同构。
5. 若P收到V发送的σ，则P将π发送给V，否则，即σ≠2，则P将 ((u) ((u)), u V1) 发送给V。
与 是计算不可区分的 ViewP,V* (x) xL
M * ( x) xL
（参看定义6.2）。
M*称为P与V*交互的模拟器。
定义15.8 设（P，V）为语言L的交互证明系统，
称（P，V）为语言L的一个关于不诚实验证者的
交互统计（几乎完全）零知识证明系统，若对每
个多项式时间的交互图灵机V*，存在一个多项式
第15章 零知识证明
15.1 交互式零知识证明系统的定义
交互图灵机作为证明者和验证者各自的计 算模型，将他们各自的交互图灵机连接起 来联合计算就构成一问一答的交互协议。
定义15.1 一个交互图灵机是一个（确定性） 多带图灵机。它具有下列带：1）一条只读 输入带；2）一条只读随机带；3）一条读 写工作带；4）一条只写输出带；5）一条 只读通信带和一条只写通信带；6）一条仅 有一个小方格的读写开关带。
15.3 非交互零知识证明系统理论
定义15.10 一对概率图灵机（P，V）称为语言L的非交互 证明系统，若V是多项式时间的，且满足下列两个条件。
1）完全性：对每个x∈L，PrV(x, R, P(x, R)) 1 2 / 3（15.4）
其中，x为（P，V）的共同输入；R为（P，V）的共同参 考序列，它是在{0,1}p(|x|)中等概分布的随机序列，p(n)为 任一固定的正多项式；P(x,R)为P发送给V的消息（P的输 出和V的输入）。
2）合理性：对每个L和每个交互图灵机B
PrV(x, R, B(x, R)) 0 2 / 3 或PrV(x, R, B(x, R)) 1 1/ 3 (15.5)