Maurer, Ueli M; Pietrzak, Krzysztof ZIST Austria
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+ln1), 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).
410 - 427
TCC: Theory of Cryptography Conference
Maurer U, Pietrzak KZ. Composition of random systems: When two weak make one strong. In: Vol 2951. Springer; 2004:410-427. doi:10.1007/978-3-540-24638-1_23
Maurer, U., & Pietrzak, K. Z. (2004). Composition of random systems: When two weak make one strong (Vol. 2951, pp. 410–427). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-540-24638-1_23
Maurer, Ueli, and Krzysztof Z Pietrzak. “Composition of Random Systems: When Two Weak Make One Strong,” 2951:410–27. Springer, 2004. https://doi.org/10.1007/978-3-540-24638-1_23.
U. Maurer and K. Z. Pietrzak, “Composition of random systems: When two weak make one strong,” presented at the TCC: Theory of Cryptography Conference, 2004, vol. 2951, pp. 410–427.
Maurer U, Pietrzak KZ. 2004. Composition of random systems: When two weak make one strong. TCC: Theory of Cryptography Conference, LNCS, vol. 2951, 410–427.
Maurer, Ueli, and Krzysztof Z. Pietrzak. Composition of Random Systems: When Two Weak Make One Strong. Vol. 2951, Springer, 2004, pp. 410–27, doi:10.1007/978-3-540-24638-1_23.