**Indistinguishability Amplification**

*Ueli Maurer and Krzysztof Pietrzak and Renato Renner*

**Abstract: ** 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.

**Category / Keywords: **foundations / informatin theory, random systems, direct product

**Date: **received 1 Dec 2006

**Contact author: **pietrzak at di ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20061204:103357 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]