ESC的RO区分有利条件上界

摘 要：文献[1]给出了一个新的密码建构ESC，但其未给出ESC的RO区分有利条件上界的详细证明，本文给出了当对ESC的一系列询问没有导致内部碰撞时其输出位是均匀和独立的，并由此进而再得到：当f是一个随机变换函数时，ESC的RO区分有利条件的上界是：；当f是一个随机置换函数时，ESC的RO区分有利条件上界是：。

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

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

1 ESC的RO区分有利条件

1.1 基本概念

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

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

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

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

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

定义5：ESC的一对内部碰撞指的是一对不同的字符串P和P，它们被吸收后后尾状态的内部状态相等，即。

定义6：一个随机预言机RO是指接受任意长度的二进制字符串作为输入然后对每个输入返回一个无限长度的二进制字符串，即它是一个从到的映射，通过对每个输入M，均匀和独立地选取返回值RO（M）中的每个比特值来产生。

我们将用来表示一次调用RO后被截成比特的输出。ESC对一个输入消息M的输出的第j块为，其中。上面的基础性质暗示着填充规则必须是海绵遵从[2]的。

1.2 ESC输出的均匀性和独立性

定理 1. 若f表示一个随机变换（或置换）函数和pad表示一个海绵遵从的填充规则，当没有发生内部碰撞时由对一系列询问返回的输出比特是均匀和独立分布的。

证明. 我们用Q来表示向系统的一系列询问，用来表示系统对Q的一系列回复。在这情况下，Q是一系列对，并且是一个正整数，（Q）是一系列对 。对于给定的一系列询问Q，随机ESC当吸收输入串和被挤压时经历过一些整体状态 。 我们用表示到实验过程中的路径集，即有={X是的一个前缀且X的长度是r的整数倍}，其中。询问过程不发生内部碰撞意味著 。考虑第i次询问的第j块输出块，我们将用来表示从第一次询问到第i-1次询问和当次询问先前经历过（除掉和）的整体状态集，将用，， 和来分别表示关于的前状态集合，后首状态集合，后尾状态集合和内部状态集合，要求在输出块的产生过程中不发生内部碰撞意味着限制内部状态的值与内部状态集合里的值都不相同。当f是一个随机变换函数时，输出块的值必须在状态集合里，这些值是等概率的。当f是一个随机置换函数时，由f的可逆性要求必须与所有先前经历过的后首状态不同 （除了），即要求是从整体状态集中来选择。又因为，所以可以简化为。因此在两种情况下对输出块在中所有可能的值都是等概率的而且独立于先前经历过的外部状态（消息块的反馈异或并不影响输出块的均匀和独立分布），所以输出比特也是均匀和独立分布的。

1.3 攻击者的情况

我们考虑一个将区分两个系统的攻击者，如图1所示，左边的系统是随机变换（或置换）函数f与ESC E的组合，攻击者不能直接询问f但可以询问E，E将会调用f来构造它的回复，这表示为E[f]，我们用H来表示E[f]的交互交互界面，交互界面H取一个二进制字符串串和一个整数作为输入，返回一个二进制串， 就是ESC被截成比特的输出。右边的系统由一个随机预言机组成，随机预言机提供与E[f]相同的交互界面H。当接受输入后，它返回被截成比特的输出 。攻击者交互界面背后的系统不是E[f]就是RO，系统是E[f]还是RO的优先概率均为1/2，攻击者会向的交互界面H发送询问，甚至是适应性的，通过连续的询问的输出的前比特，在发送完所有询问后，攻击者使用系统对询问的回复来猜测是E[f]还是RO。我们假设攻击者的计算能力无界限，她可以最大限度的挖掘呈现在询问回复中的信息。然后我们来限定作为总询问成本[2]的函数的ESC RO区分有利条件的上界。

1.4 ESC的RO区分有利条件

又由于ESC与文献[2]中海绵建构不同的是在每次调用完变换（或置换）函数后对外部状态进行的消息反馈异或，相应后尾状态和后首状态的内部状态相同，属于同一个超级节点，因此通过最优策略时ESC产生内部碰撞的概率与海绵建构的相同，所以再根据文献[2]中产生内部碰撞的概率就可推导出以下两个定理。

参考文献：

[1]陈伟彬.一个阻止内部碰撞转状态碰撞的海绵建构变体[J].科技传播，2014（06）：149-150.

[2]G.Bertoni，J.Daemen，M.Peeters，and G.Van Assche，Cryptographic sponge functions[OL]，（2012/02/15）[2013/11/30]http：//sponge.noekeon.org/.

[3]Gauravaram，P.，Kelsey，J.，Knudsen，L.R.， Thomsen，S.S.：On hash functions using checksums[J].Int.J.Inf.Secur.vol.9（2），pp.137-151（2010）.

[4]U.Maurer.Indistinguishability of random systems. In Advances in Cryptology—EUROCRYPT 02， volume 2332 of Lecture Notes in Computer Science， pages 110-132. Springer-Verlag，2002.

作者简介：陈伟彬（1987—），男，广东汕头人，硕士研究生，助教，研究方向：密码学和数论等。