Composition of random systems: When two weak make one strong Conference Paper

Author(s): Maurer, Ueli M; Pietrzak, Krzysztof
Title: Composition of random systems: When two weak make one strong
Title Series: LNCS
Abstract: 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).
Conference Title: TCC: Theory of Cryptography Conference
Volume: 2951
Conference Dates: February 19-21, 2004
Conference Location: Cambridge, MA, USA
Publisher: Springer  
Date Published: 2004-03-19
Start Page: 410
End Page: 427
Copyright Statement: ⓒ Springer-Verlag Berlin Heidelberg 2004
DOI: 10.1007/978-3-540-24638-1_23
Open access: no
IST Austria Authors
Related IST Austria Work