ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

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$, relative to another random system $\bG$, whose probability of occurring for a given distinguisher $\bD$ is closely related to the distinguishing advantage $\varepsilon$ of $\bD$ for $\bF$ and $\bG$, namely it is lower and upper bounded by $\varepsilon$ and $\varepsilon(1+\lninv{\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).