Paper 2009/396
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Ueli Maurer and Stefano Tessaro
Abstract
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 XORlemma implies, by a hybrid argument, that no efficient distinguisher has advantage better than (roughly) $n2^{m1} \delta^m$ in distinguishing the XOR of $m$ independent $n$bit PRG outputs $S_1,\ldots,S_m$ from uniform randomness if no efficient distinguisher has advantage more than $\delta$ in distinguishing $S_i$ from a uniform $n$bit string. The factor $2^{m1}$ allows for security amplification only if $\delta<\frac{1}{2}$: For the case of PRFs, a randomoffset XORconstruction of Myers was the first result to achieve {\em 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 {\em tight} informationtheoretic bound $2^{m1}\delta^m$ (without factor $n$) also for the computational setting. Second, we prove results for {\em interactive} systems (e.g. PRFs or PRPs). Third, we consider the general class of {\em 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 singlesided and twosided queries. Fourth, {\em 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 {\em weakened assumptions} like security against randominput (as opposed to choseninput) attacks. A key technique is a generalization of Yao's XORlemma to (interactive) systems, which is of independent interest.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Full version of a paper appearing at CRYPTO 2009
 Keywords
 security amplificationpseudorandomnesscascaded encryption
 Contact author(s)
 tessaros @ inf ethz ch
 History
 20090815: received
 Short URL
 https://ia.cr/2009/396
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/396, author = {Ueli Maurer and Stefano Tessaro}, title = {Computational Indistinguishability Amplification: Tight Product Theorems for System Composition}, howpublished = {Cryptology ePrint Archive, Paper 2009/396}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/396}}, url = {https://eprint.iacr.org/2009/396} }