原文教材 与 参考资料：

? ? ? ? Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography[J].

? ? ? ? 该书项目地址（可以免费获取）：http://toc.cryptobook.us/

? ? ? ? 博客为对该书的学习笔记，并非原创知识，帮助理解，整理思路。

随机语言机模型的安全性定义

? ? ? ? 假设我们有一些密码学协议S，这个协议的实现使用了一个子程序计算哈希函数H。协议S可以调用H在任意随机的点上，但是S不能看到H的内部是实现方式。我们定义S将H作为一个语言机。

? ? ? ?我们想要分析协议S的安全性，假设定义任意我们感兴趣的安全属性为“属性X”，并将其建模为一个挑战者（专门针对属性X）和敌手之间的游戏。挑战者计算协议S中的函数得到给敌手的回复结果，这些函数也可能要求计算H。这个游戏定义了这个属性的优势Xadv[A,S], 并且关于这个属性的安全意味着没有有效的敌手能够以不可忽略的优势赢得游戏。

? ? ? ? 当我们想要在随机谕言机模型下分析这个方案S时，攻击游戏中的H被修改为一个随机函数O，这个函数来源于H的全映射函数。任何的挑战者和敌手都能够访问这个谕言机。

1. 在游戏的开始时，挑战者从函数集合Funs[M,T]中随机选取一个函数函数作为谕言机。

2. 此外，敌手A除了提交标准请求外，还能够提交随机谕言机请求，敌手可以任意的交叉提出标准请求和随机谕言机请求。

3. 在标准请求的过程中，挑战者使用O替换原来的H。 (在随机语言机模型中，其实本质上就是用一个随机置换替换掉了函数中需要计算H的部分，当然在定义的时候，我们亦可以分开来定义，专门定义一下谕言机的描述）

例子 ：PRF在随机谕言机中的证明

? ? ? ? 这里该书展示了一个例子，如何使用随机谕言机框架来构造安全的PRF。那么首先需要建立一个攻击游戏，这个随机谕言机的攻击游戏来源于标准的PRF安全攻击游戏。如果我们有一个PRF F使用了有一个哈希函数H作为谕言机，我们定义FO符号为该函数使用随机谕言机O替换了H。

该攻击游戏定义如下：

? ? ? ?在这个游戏中，有两个实验b = 0/1。当b = 1时，定义b =? 0时，f 访问的是随机谕言机，此时F-query和O-query是相同的。当b = 1时，F-query 访问的是一个随机函数，O-query 依然是随机谕言机访问方式。敌手A的优势其实就是相当于区分这两个实验的概率，当这个优势可以忽略时，我们说敌手PRF F在随机谕言机模型下式安全的。

? ? ? 我们可以观察到，在这个简单的例子中，敌手A依然是一个自由的敌手，其可以发送任意的攻击，随机谕言机在这里只能保证在H是安全的情况下，该实验对一般性的PRF安全属性得到保证，但是无法防御潜在的经过精心设计的恶意攻击。

进一步，我们获得该模型下的安全定理：

需要注意的是，敌手这里唯一被限制的地方是敌手仅仅依赖于访问次数，不依赖于其他的任何复杂性假设。

证明：

? ? ? ? 构造游戏Game 0, 这个游戏等价与上述实验0，b = 0，并且假设敌手永远不会请求F-query两次，我们创建一个映射表Map是三元表格Map = { k, x, t }。在Game 0 中 要求F请求是与一个随机的函数交互（随机谕言机），O请求是与定义的随机谕言机交互，那么此时挑战者0对于敌手而言应当表现出来的是使用一个随机谕言机与其交互，当然此时敌手也是可以访问该谕言机的，所以得到该实验的细节描述如下：

? ? ? ? 此时对于敌手A而言，每次询问不同的输入，都会得到不同的输出，并且假设不能询问F两次相同的询问，上述（1）（2）完美模拟了随机谕言机的O请求。例如，敌手首先询问某个值A,B ，作为F请求，那么该表会记录（A，B ,C ）并将C作为结果返回给敌手，Map增加表项（A,B.C），因为我们假设了敌手不会询问两次相同的F请求，那么敌手如果要询问只能向O发出请求，再次请求（A，B）, 谕言机此时查表Map因为之前已经请求过，所以谕言机O返回表项C给敌手。所以，对于敌手而言，看到的视图是相同的，都是谕言机返回的结果。

进一步，构造游戏Game 1.

?Game 1游戏与Game 0 的不同就在于，删除了F构造中的两个条件，那么挑战者1将不在使用列表l来回复敌手的询问，只是返回一个随机的值，那么敌手发起F-query时(请求（A,B））敌手将会获得请求结果C。并且敌手不能询问两次相同的F-query，此时敌手依然可以进行随机的O-query，因为此时随机函数蕴含着使用随机谕言机O，所以可以询问O。随机谕言机依然使用Map的方式回复。Game 1将会等价攻击游戏实验1。敌手不能够,因此获得如下：

定义时间Z为在Game 1中，敌手请求一个O-query, m = (k||x) ,那么此时两个游戏将会有相同的输出结果，因为在Game 0 中，F-query 和 O-query 对于m = (k || x)输出是相同一个结果。在Game 1中输出0，在Game 0中输出1，由Difference Lemma，得到：

? ? ? ?

为什么我们要用随机谕言机模型？

（下述内容为个人的看书的一点思考，也许并不正确，欢迎讨论）

? ? ? ? 首先，构建密码方案的安全性证明，是针对我们关系的安全属性进行抽象，然后设计出能够反应该安全属性的攻击游戏（实验）。在这个过程中，我们需要确保挑战者的回复是符合原来协议的，能够体现安全属性的，同时还要兼顾所有方案中使用到的密码学组件，因为各类组件未必是可以随机自由组合的。

? ? ? ?其次，谕言机这个概念在密码学的安全性证明中是常见的，随机谕言机只不过体现了这是一个返回随机输出的谕言机，谕言机本质和其他种类的谕言机没有质的区别，敌手和挑战者都可以访问谕言机，并且访问它的参与方都不知道其中的内容实现方式，就像一个黑盒。

? ? ?最后，随机谕言机与哈希函数的关系，哈希函数我们知道是一个很有用的密码学工具，我们给与该函数一定的输入，它返回一个输出，一般要求其应该具备很强的抗碰撞属性。但是，在现实中到底是否存在这样的哈希函数呢？答案是否定的，很多哈希函数可能并不是安全的，例如MD5已经被证明不是一个安全的哈希函数。那么，如果我们的方案中使用了类似的哈希函数，如何保证其安全性? 或者说如何保证不会因为哈希函数引入新的不安全因素？答案是：将它抽象成为一个安全的模型，使用随机谕言机来替代方案中哈希函数。由于引入了随机谕言机，所以很多安全模型需要做相应的修改，并且我们假设了随机谕言机是一个理想的安全组件，那么，对于敌手和挑战者而言，都应当具备访问该谕言机的能力。和标准模型相比，相对而言，我们可以认为敌手此时其实具有了一个新的访问随机谕言机的能力，那么就需要修改原始的安全模型，建立新的随机谕言机模型下的安全模型。至于如从标准模型到随机谕言机模型及其合理性此处暂时不展开讨论。

单词表

heuristic <adj> 启发式? ? ? ? ? ? ? ? ? ? ?grabbing: <v> 抓，夺走

analogous 类似的? ? ? ? ? ? ? ? ? ? ? ? ? ? indifferentiability: 不可微

thumb <n> 拇指 手势? ? ? ? ? ? ? ? ? ? ? out of ：超出，用....

rule out: 排除? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? In either case: 不论发生任何情况

relevant <adj> 相关的，切题的

off the shelf: 现成的

?

cs