# 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).