Paper 2006/456

Indistinguishability Amplification

Ueli Maurer, Krzysztof Pietrzak, and Renato Renner


A random system is the abstraction of the input-output behavior of any kind of discrete system, in particular cryptographic systems. Many aspects of cryptographic security analyses and proofs can be seen as the proof that a certain random system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the distinguishing advantage of a combined system, assuming upper bounds of various types on the component systems. For a general type of combination operation of systems (including the combination of functions or the cascade of permutations), we prove two amplification theorems. The first is a direct-product theorem, similar in spirit to the XOR-Lemma: The distinguishing advantage (or security) of the combination of two (possibly stateful) systems is twice the product of the individual distinguishing advantages, which is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of attacks. As a corollary we obtain tight bounds on the adaptive security of the cascade and parallel composition of non-adaptively (or only random-query) secure component systems. A key technical tool of the paper is to show a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of provoking an appropriately defined event on one of the systems.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
informatin theoryrandom systemsdirect product
Contact author(s)
pietrzak @ di ens fr
2006-12-04: received
Short URL
Creative Commons Attribution


      author = {Ueli Maurer and Krzysztof Pietrzak and Renato Renner},
      title = {Indistinguishability Amplification},
      howpublished = {Cryptology ePrint Archive, Paper 2006/456},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.