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

《第3章 密码学的复杂性理论基础.ppt》由会员分享，可在线阅读，更多相关《第3章 密码学的复杂性理论基础.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 密码学的复杂性理论基础密码学的复杂性理论基础 1密码技术和算法复杂性密码技术和算法复杂性 计算复杂性计算复杂性：研究密码分析对于计算量的需求和密码：研究密码分析对于计算量的需求和密码分析的困难程度分析的困难程度，从而得出这些密码技术和算法在现，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性：有可行的条件下是否具有足够的安全性：算法复杂性；算法复杂性；问题复杂性。问题复杂性。密码协议、方案和体制的安全性证明：零知识证明理密码协议、方案和体制的安全性证明：零知识证明理论。论。2问题（问题（problem）即需要回答的一般性提问即需要回答的一般性提问:它通常含有若干个参

2、数。它通常含有若干个参数。对于一个问题进行描述应该包括两方面的内容：必对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。述该问题的答案（或解）应该满足的性质。当问题的所有参数都有了确定的取值时，我们称得当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（到了该问题的一个实例（instance）。）。3算法（算法（algorithm）即求解某个问题的一系列具体步骤（通常被理解为求即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。解所需的通用计算

3、程序）。算法总是针对具体问题而言的，求解一个问题的算算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。法通常不止一个。当某个算法能够回答一个问题的任何实例时，我们当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。称该算法能够回答这个问题。当一个问题至少有一个能够回答该问题的算法时，当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（我们称该问题可解（resolvable），否则称该问题不），否则称该问题不可解（可解（unresolvable）。）。4算算 法法 复复 杂杂 性性 即度量该算法所需的计算能力即度量该算法所需的计算能力，包括：，包括：时间复杂

4、性时间复杂性T（time complexity）；）；空间复杂性空间复杂性S（space complexity）；）；随机位数目；随机位数目；信道带宽；信道带宽；数据总量；数据总量；5算算 法法 复复 杂杂 性性 计算复杂性的表示符号为计算复杂性的表示符号为“O”（称为（称为“大大O”），），表示计算复杂性的数量级表示计算复杂性的数量级 好处：好处：使算法复杂性度量与处理器的运行速度和指令运使算法复杂性度量与处理器的运行速度和指令运行时间无关；行时间无关；明确地揭示了输入的数据长度对算法复杂性的影明确地揭示了输入的数据长度对算法复杂性的影响。响。6算算 法法 复复 杂杂 性性算法的分类及其运行

5、时间算法的分类及其运行时间 运算次数宇宙年龄的类别类别复复杂杂性性时间时间多多项项式式常数常数 11微妙微妙线线性性1秒秒二次二次11.6天天三次三次32,000年年指数指数7问问 题题 复复 杂杂 性性 研究问题的内在复杂性，即在图灵机上解决最难的问研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。题实例所需的最小时间和空间条件。8图灵机图灵机 图灵机是一种具有无限读图灵机是一种具有无限读-写存储带的有限状态机，可以写存储带的有限状态机，可以被当作一个实际可用的计算模型被当作一个实际可用的计算模型。确定性图灵机。确定性图灵机。非确定性图灵机非确定性图灵机：能够进行

6、猜测。求解一个问题分：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。两个阶段：猜测阶段和验证阶段。9问题分类问题分类易处理的（易处理的（tractable）：确定性图灵机上能够在多项：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为式时间内得到处理的问题。称易处理问题的全体为“多项式时间可解类多项式时间可解类”，记为，记为P。非确定性图灵机上能够在多项式时间内得到处理的问非确定性图灵机上能够在多项式时间内得到处理的问题被称为题被称为“非确定性多项式时间可解问题非确定性多项式时间可解问题”，简称，简称NP问题。问题。NP问题的全体被称为问题的全体被称为“非确定性多

7、项式时间可非确定性多项式时间可解类解类”，记为，记为NP。10NP问题问题 意义：能够通过非确定性的多项式时间算法对许多对意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。称密钥算法和所有公钥算法进行攻击。NP完全问题完全问题：指：指NP中的任何一个问题都可以通过多中的任何一个问题都可以通过多项式时间转化为该问题项式时间转化为该问题。NP完全问题的全体被记为完全问题的全体被记为NPC。NP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。11零知识证明零知识证明 证明者能够在不向验证者提供任何有用的信息的情况证明者能够在不向验证者提供任何有用的信息的情况

8、下，使验证者相信某个论断是正确的。下，使验证者相信某个论断是正确的。实质上是一种涉及两方或更多方的协议，即两方或更实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。多方完成一项任务所需采取的一系列步骤。12零知识零知识“洞穴洞穴”13零知识零知识“洞穴洞穴”（1）V站在站在A处；处；（2）P走进洞穴，到达走进洞穴，到达C处或处或D处；处；（3）当）当P消失在洞穴中时，消失在洞穴中时，V走到走到B处；处；（4）V呼叫呼叫P，要求，要求P：（：（a）从左通道出来；或者（）从左通道出来；或者（b）从右通道出来；从右通道出来；（5）P答应答应V的呼叫，并在有必要的情况

9、下用咒语打开的呼叫，并在有必要的情况下用咒语打开C与与D之间的秘密之门；之间的秘密之门；（6）重复步骤（）重复步骤（1）（5）n次。次。14基本的零知识协议过程基本的零知识协议过程假设假设P知道一部分信息，并且该信息是一个难题的解法知道一部分信息，并且该信息是一个难题的解法：（1）P用自己的信息和一个随机数将这个难题转变为用自己的信息和一个随机数将这个难题转变为与之同构的新难题，然后用自己的信息和这个随机数与之同构的新难题，然后用自己的信息和这个随机数这个新难题；这个新难题；（2）P利用位承诺方案提交对于这个新难题的解法；利用位承诺方案提交对于这个新难题的解法；（3）P向向V透漏这个新难题，透

10、漏这个新难题，V无法通过新难题得到关无法通过新难题得到关于原难题或其解法的任何信息；于原难题或其解法的任何信息；（4）V要求要求P：（：（a）证明新、旧难题同构；或者）证明新、旧难题同构；或者（b）公布）公布P在（在（2）中提交解法并证明该解法的确为新）中提交解法并证明该解法的确为新难题的解法；难题的解法；（5）P答应答应V的要求；的要求；（6）重复步骤（）重复步骤（1）（5）n次。次。15交互与非交互交互与非交互交互零知识证明交互零知识证明：证明者和验证者之间必须进行交互：证明者和验证者之间必须进行交互。由。由Goldwasser等人在等人在20世纪世纪80年代初提出年代初提出 GMR模型；

11、模型；FFS模型。模型。非交互零知识证明非交互零知识证明：用一个短随机串代替交互过程并：用一个短随机串代替交互过程并实现了零知识证明实现了零知识证明。20世纪世纪80年代末，年代末，Blum等人进等人进一步提出一步提出 成员（或定理）的非交互零知识证明系统；成员（或定理）的非交互零知识证明系统；知识（或身份）的非交互零知识证明系统。知识（或身份）的非交互零知识证明系统。16交互图灵机交互图灵机 交互图灵机指的是一个具有一条只读输入带、一条工交互图灵机指的是一个具有一条只读输入带、一条工作带、一条随机带、一条只读通信带和一条只写通信作带、一条随机带、一条只读通信带和一条只写通信带的图灵机。其中，

12、随机带上包含一条无限长的随机带的图灵机。其中，随机带上包含一条无限长的随机比特序列，并且只能从左向右读入。比特序列，并且只能从左向右读入。“一个交互图灵一个交互图灵机投一个硬币机投一个硬币”指该图灵机从自己的随机带上读取指该图灵机从自己的随机带上读取1bit。17交互协议交互协议 即满足以下两个条件的有序图灵机（即满足以下两个条件的有序图灵机（A,B），其中，），其中，A具有无限的计算能力，具有无限的计算能力，B具有多项式时间的计算能力：具有多项式时间的计算能力：（a）A与与B共享同一输入带；共享同一输入带；（b）B的只写通信带是的只写通信带是A的只读通信带，同时，的只读通信带，同时，B的只的

13、只读通信带是读通信带是A的只写通信带。的只写通信带。18GMR模型模型 假设证明者具有无限的计算能力，并且验证者具有多假设证明者具有无限的计算能力，并且验证者具有多项式时间的计算能力。项式时间的计算能力。对于输入对于输入I和语言和语言L，判断，判断IL是否成立。是否成立。由于这一过程向验证者泄露了由于这一过程向验证者泄露了1b信息（即信息（即IL），所），所以基于以基于GMR模型的零知识证明并非真正的零知识证明。模型的零知识证明并非真正的零知识证明。这种交互零知识证明通常被称为这种交互零知识证明通常被称为“成员（或定理）的成员（或定理）的零知识证明（零知识证明（zero knowledge p

14、roofs of membership or theorem）。）。19FFS模型模型 假设证明者与验证者具有多项式时间的计算能力。假设证明者与验证者具有多项式时间的计算能力。证明者向验证者证明的不是证明者向验证者证明的不是IL成立与否，而是证明自成立与否，而是证明自己知道输入己知道输入I关于语言关于语言L的状况。由于在这个证明过程中，的状况。由于在这个证明过程中，验证者相信这个证明，但是又无法得知任何信息（包括验证者相信这个证明，但是又无法得知任何信息（包括IL是否成立）。是否成立）。基于基于FFS模型的零知识证明是真正的零知识证明。这种交模型的零知识证明是真正的零知识证明。这种交互零知识证

15、明通常被称为互零知识证明通常被称为“知识（或身份）的零知识证知识（或身份）的零知识证明（明（zero knowledge proofs of knowledge or identity）”。20成员（或定理）的非交互零知识成员（或定理）的非交互零知识证明系统证明系统 两个阶段两个阶段预处理阶段预处理阶段：建立证明者和验证者所拥有的某些共同：建立证明者和验证者所拥有的某些共同信息及其各自拥有的秘密信息，允许证明者和验证者信息及其各自拥有的秘密信息，允许证明者和验证者进行交互。进行交互。定理证明阶段定理证明阶段：证明者选择并向验证者证明自己所知：证明者选择并向验证者证明自己所知道的定理，这个阶段是非交互的。道的定理，这个阶段是非交互的。21