Composition of Random Systems: When Two Weak Make One Strong

Ueli Maurer and Krzysztof Pietrzak

Theory of Cryptography Conference — TCC 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 2951, pp. 410–427, Feb 2004.

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 $F$ , relative to another random system $G$ , whose probability of occurring for a given distinguisher $D$ is closely related to the distinguishing advantage $ε$ of $D$ for $F$ and $G$ , namely it is lower and upper bounded by $ε$ and $ε (1 + \ln \frac{1}{ε})$ , 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},
}