Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomness
Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomness
复制标题
去相关和超伪随机性的自适应攻击范数
DOI：
10.1007/3-540-46513-8_4
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Vaudenay
中科院分区：
文献类型：
--
作者：
S. Vaudenay
在以前的工作中，去相关理论的安全性结果是基于无穷相关矩阵范数。这使得能够证明去相关提供针对非自适应迭代攻击的安全性。在本文中，我们定义了一个新的矩阵范数专用于自适应选择明文攻击。同样地，我们构造了另一个矩阵范数，专门用于选择明文和密文攻击。去相关的形式化使得能够如此容易地操纵攻击者的最佳优势的概念，以至于我们证明了一个有点直观的定理，该定理说，区分随机乘积密码和真正随机置换的最佳优势随项数呈指数下降。我们证明了几个矩阵范数的最佳优势。之前关于去相关的结果扩展了这些新规范。特别地，我们证明了Peanut构造（例如DFC算法）在不变界的情况下对自适应迭代选择明文攻击是安全的，而在其它界的情况下对自适应迭代选择明文和密文攻击是安全的，这表明它实际上是超伪随机的.我们还将Peanut构造推广到任何方案，而不是Feistel方案.我们表明，只需要一个等价的Luby-Rackoff引理，以获得去相关上界。
In previous work, security results of decorrelation theory was based on the infinity-associated matrix norm. This enables to prove that decorrelation provides security against non-adaptive iterated attacks. In this paper we define a new matrix norm dedicated to adaptive chosen plaintext attacks. Similarly, we construct another matrix norm dedicated to chosen plaintext and ciphertext attacks.The formalism from decorrelation enables to manipulate the notion of best advantage for distinguishers so easily that we prove as a trivial consequence a somewhat intuitive theorem which says that the best advantage for distinguishing a random product cipher from a truly random permutation decreases exponentially with the number of terms.We show that several of the previous results on decorrelation extend with these new norms. In particular, we show that the Peanut construction (for instance the DFC algorithm) provides security against adaptive iterated chosen plaintext attacks with unchanged bounds, and security against adapted iterated chosen plaintext and ciphertext attacks with other bounds, which shows that it is actually super-pseudorandom.We also generalize the Peanut construction to any scheme instead of the Feistel one. We show that one only requires an equivalent to Luby-Rackoff’s Lemma in order to get decorrelation upper bounds.