Composition of Random Systems: When Two Weak Make One Strong
Ueli Maurer and Krzysztof Pietrzak
A new technique for proving the adaptive indistinguishability of two systems, each composed of some component systems, is presented, using only the fact that corresponding component systems are non-adaptively indistinguishable. The main tool is the definition of a special monotone condition for a random system $\bf F$, relative to another random system $\bf G$, whose probability of occurring for a given distinguisher $\bf D$ is closely related to the distinguishing advantage $\varepsilon$ of $\bf D$ for $\bf F$ and $\bf G$, namely it is lower and upper bounded by $\varepsilon$ and $\varepsilon(1+\ln \frac{1}{\varepsilon})$, respectively.
A concrete instantiation of this result shows that the cascade of two random permutations (with the second one inverted) is indistinguishable from a uniform random permutation by adaptive distinguishers which may query the system from both sides, assuming the components' security only against non-adaptive one-sided distinguishers.
As applications we provide some results in various fields as almost $k$-wise independent probability spaces, decorrelation theory and computational indistinguishability (i.e., pseudo-randomness).
BibTeX Citation
@inproceedings{MauPie04,
author = {Ueli Maurer and Krzysztof Pietrzak},
title = {Composition of Random Systems: When Two Weak Make One Strong},
editor = {Moni Naor},
booktitle = {Theory of Cryptography Conference --- TCC 2004},
pages = {410--427},
series = {Lecture Notes in Computer Science},
volume = {2951},
year = {2004},
month = {2},
publisher = {Springer-Verlag},
}