关键词：密码建构；随机预言机；RO区别有利条件；随机变换函数；随机置换函数

DOI：10.16640/j.cnki.37-1222/t.2016.09.188

1 前言

Maurer等人在文献[3]中提出了不可区别性，后来由Coron等人在文献[4]将其应用到了迭代的Hash函数。Andreeva等人在文献[5]中正式证明任何对密码建构发动的一般攻击的成功概率上界是该攻击对随机预言机的成功概率加上RO区别有利条件的上界，这就是不可区别性的中心思想是，因此给出ESC的RO区别有利条件的上界将十分必要。

由于ESC与海绵建构不同的是在每次调用完变换（或置换）函数后对外部状态进行的消息反馈异或，相应后尾状态和后首状态的内部状态相同，属于同一个超级节点，因此我们可利用文献[2]中G. Bertoni等人对海绵建构不可区别性的证明方法来证明ESC的不可区别性。

2 ESC的RO区别有利条件

2.1 基本概念

定义1：一个超级节点指内部状态相同的节点集。

定义2：ESC吸收字符串P后的前状态是指那个对字符串P的最后一块消息只进行了一次异或后得到的整体状态，我们将用来表示。

定义3：ESC吸收字符串P后的后首状态是指的是那个用变换（或置换）处理相应前状态后得到的整体状态，我们将用表示。

定义4：ESC吸收字符串P后的后尾状态指的是那个对相应后首状态进行了消息反馈异或后得到的整体状态，我们将用来表示。

我们将用，，和来分别表示ESC吸收字符串P后后首状态的内部状态，外部状态和整体状态；将用，，和来分别表示ESC吸收字符串P后后尾状态的内部状态，外部状态和整体状态，我们知道ESC吸收同一个字符串P后后首状态和相应的后尾状态的内部状态相同，而且挤压阶段可视为吸收零块消息，因此后首状态和相应的后尾状态相同（调用变换（或置换）函数后）；……