第3章 密码学的复杂性理论基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第3章,密码学的复杂性理论基础,1,密码技术和算法复杂性,计算复杂性：研究密码分析对于计算量的需求和密码分析的困难程度，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性：,算法复杂性；,问题复杂性。,密码协议、方案和体制的安全性证明：零知识证明理论。,2,问题（,problem,）,即需要回答的一般性提问:,它通常含有若干个参数。,对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。,当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（,instance,）。,3,算法（,algorithm,）,即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。,算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。,当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。,当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（,resolvable,），否则称该问题不可解（,unresolvable,）。,4,算 法 复 杂 性,即度量该算法所需的计算能力，包括：,时间复杂性,T,（,time complexity,）；,空间复杂性,S,（,space complexity,）；,随机位数目；,信道带宽；,数据总量；,5,算 法 复 杂 性,计算复杂性的表示符号为“,O,”,（称为“大,O,”），表示计算复杂性的数量级,好处：,使算法复杂性度量与处理器的运行速度和指令运行时间无关；,明确地揭示了输入的数据长度对算法复杂性的影响。,6,算 法 复 杂 性,算法的分类及其运行时间,运算次数,宇宙年龄的,类别,复杂性,时间,多项式,常数,1,1,微妙,线性,1,秒,二次,11.6,天,三次,32,000,年,指数,7,问 题 复 杂 性,研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。,8,图灵机,图灵机是一种具有无限读写存储带的有限状态机，可以被当作一个实际可用的计算模型。,确定性图灵机。,非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。,9,问题分类,易处理的（,tractable,）：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为“多项式时间可解类”，记为,P。,非确定性图灵机上能够在多项式时间内得到处理的问题被称为“非确定性多项式时间可解问题”，简称,NP,问题。,NP,问题的全体被称为“非确定性多项式时间可解类”，记为,NP。,10,NP,问题,意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。,NP,完全问题：指,NP,中的任何一个问题都可以通过多项式时间转化为该问题。,NP,完全问题的全体被记为,NPC。,NP Hard,问题,?,11,零知识证明,证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。,实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。,12,零知识“洞穴”,13,零知识“洞穴”,（,1,）,V,站在,A,处；,（,2,）,P,走进洞穴，到达,C,处或,D,处；,（,3,）当,P,消失在洞穴中时，,V,走到,B,处；,（,4,）,V,呼叫,P,，要求,P,：（,a,）从左通道出来；或者（,b,）从右通道出来；,（,5,）,P,答应,V,的呼叫，并在有必要的情况下用咒语打开,C,与,D,之间的秘密之门；,（,6,）重复步骤（,1,）,（,5,）次。,14,基本的零知识协议过程,假设,P,知道一部分信息，并且该信息是一个难题的解法：,（,1,）,P,用自己的信息和一个随机数将这个难题转变为与之同构的新难题，然后用自己的信息和这个随机数这个新难题；,（,2,）,P,利用位承诺方案提交对于这个新难题的解法；,（,3,）,P,向,V,透漏这个新难题，,V,无法通过新难题得到关于原难题或其解法的任何信息；,（,4,）,V,要求,P,：（,a,）证明新、旧难题同构；或者（,b,）公布,P,在（,2,）中提交解法并证明该解法的确为新难题的解法；,（,5,）,P,答应,V,的要求；,（,6,）重复步骤（,1,）,（,5,）次。,15,交互与非交互,交互零知识证明：证明者和验证者之间必须进行交互。由,Goldwasser,等人在,20,世纪,80,年代初提出,GMR,模型；,FFS,模型。,非交互零知识证明：用一个短随机串代替交互过程并实现了零知识证明。,20,世纪,80,年代末，,Blum,等人进一步提出,成员（或定理）的非交互零知识证明系统；,知识（或身份）的非交互零知识证明系统。,16,交互图灵机,交互图灵机指的是一个具有一条只读输入带、一条工作带、一条随机带、一条只读通信带和一条只写通信带的图灵机。其中，随机带上包含一条无限长的随机比特序列，并且只能从左向右读入。“一个交互图灵机投一个硬币”指该图灵机从自己的随机带上读取,1bit。,17,交互协议,即满足以下两个条件的有序图灵机（,A,B,），其中，,A,具有无限的计算能力，,B,具有多项式时间的计算能力：,（,a,）,A,与,B,共享同一输入带；,（,b,）,B,的只写通信带是,A,的只读通信带，同时，,B,的只读通信带是,A,的只写通信带。,18,GMR,模型,假设证明者具有无限的计算能力，并且验证者具有多项式时间的计算能力。,对于输入,I,和语言,L,，判断,IL,是否成立。,由于这一过程向验证者泄露了,1b,信息（即,IL,），所以基于,GMR,模型的零知识证明并非真正的零知识证明。这种交互零知识证明通常被称为“成员（或定理）的零知识证明（,zero knowledge proofs of membership or theorem,）。,19,FFS,模型,假设证明者与验证者具有多项式时间的计算能力。,证明者向验证者证明的不是,IL,成立与否，而是证明自己知道输入,I,关于语言,L,的状况。由于在这个证明过程中，验证者相信这个证明，但是又无法得知任何信息（包括,IL,是否成立）。,基于,FFS,模型的零知识证明是真正的零知识证明。这种交互零知识证明通常被称为“知识（或身份）的零知识证明（,zero knowledge proofs of knowledge or identity,）”。,20,成员（或定理）的非交互零知识证明系统,两个阶段,预处理阶段：建立证明者和验证者所拥有的某些共同信息及其各自拥有的秘密信息，允许证明者和验证者进行交互。,定理证明阶段：证明者选择并向验证者证明自己所知道的定理，这个阶段是非交互的。,21,