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