Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
复制标题
计算不可区分性放大：系统组成的紧积定理
DOI：
10.1007/978-3-642-03356-8_21
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Stefano Tessaro
中科院分区：
文献类型：
--
作者：
U. Maurer;Stefano Tessaro
计算不可扩展性放大是加强密码原语的问题，其安全性通过限制有效密码的显著优势来定义。示例包括伪随机发生器（PRG）、伪随机函数（PRF）和伪随机排列（PRP）。
关于计算不可逆性放大的文献只包括少数孤立的结果。姚的XOR引理意味着，由一个混合的论点，没有有效的搜索引擎有优势比（大约）n2米？一号？m在区分m个独立的n位PRG输出S1，.，S m从均匀随机性，如果没有有效的随机性的优势超过？从一个统一的n位字符串中区分Si。系数2 m？1仅当$\delta<\frac{1}{2}$时允许安全放大：对于PRF的情况，Myers的随机偏移XOR构造是实现强安全放大的第一个结果，即，也适用于$\frac{1}{2} \le \delta < 1$。
本文提出了一个系统的处理计算不相容性放大。我们推广和改进了上述乘积定理，用于PRG沿着五个轴的异或。首先，我们证明了紧信息理论界2米？一号？m（无因子n）也用于计算设置。其次，我们证明了交互式系统（如PRFs或PRPs）的结果。第三，我们考虑一般类的中和组合结构，而不仅仅是XOR。作为一个应用，这产生了PRP级联的第一个不可逆性扩增结果（即，块密码）将弱PRP转换为任意强PRP，用于单侧和双侧查询。第四，强大的安全放大实现了一个子类的中和结构，其中包括作为一个特殊情况下的建设迈尔斯。作为一个应用，我们获得了高度实用的最佳安全放大的分组密码，简单地通过添加随机偏移的输入和输出的级联。第五，我们还显示了强大的安全放大功能，例如针对随机输入（而不是选择输入）攻击的安全性等弱化假设。
一个关键技术是将Yao的XOR引理推广到具有独立兴趣的（交互式）系统。
Computational indistinguishability amplification is the problem of strengthening cryptographic primitives whose security is defined by bounding the distinguishing advantage of an efficient distinguisher. Examples include pseudorandom generators (PRGs), pseudorandom functions (PRFs), and pseudorandom permutations (PRPs).
The literature on computational indistinguishability amplification consists only of few isolated results. Yao's XOR-lemma implies, by a hybrid argument, that no efficient distinguisher has advantage better than (roughly) n2 m ? 1 ? m in distinguishing the XOR of m independent n-bit PRG outputs S 1,...,S m from uniform randomness if no efficient distinguisher has advantage more than ? in distinguishing S i from a uniform n-bit string. The factor 2 m ? 1 allows for security amplification only if $\delta<\frac{1}{2}$: For the case of PRFs, a random-offset XOR-construction of Myers was the first result to achieve strong security amplification, i.e., also for $\frac{1}{2} \le \delta < 1$.
This paper proposes a systematic treatment of computational indistinguishability amplification. We generalize and improve the above product theorem for the XOR of PRGs along five axes. First, we prove the tight information-theoretic bound 2 m ? 1 ? m (without factor n) also for the computational setting. Second, we prove results for interactive systems (e.g. PRFs or PRPs). Third, we consider the general class of neutralizing combination constructions, not just XOR. As an application, this yields the first indistinguishability amplification results for the cascade of PRPs (i.e., block ciphers) converting a weak PRP into an arbitrarily strong PRP, both for single-sided and two-sided queries. Fourth, strong security amplification is achieved for a subclass of neutralizing constructions which includes as a special case the construction of Myers. As an application we obtain highly practical optimal security amplification for block ciphers, simply by adding random offsets at the input and output of the cascade. Fifth, we show strong security amplification also for weakened assumptions like security against random-input (as opposed to chosen-input) attacks.
A key technique is a generalization of Yao's XOR-lemma to (interactive) systems which is of independent interest.