# Indistinguishability Amplification

## Ueli Maurer and Krzysztof Pietrzak and Renato Renner

```
```Many aspects of cryptographic security proofs can be seen as the
proof that a certain 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 information-theoretic distinguishing advantage (from an ideal
system) for a combined system, assuming upper bounds of certain
types for the component systems. For a general type of combination
operation of systems, including the XOR of functions or the cascade
of permutations, we prove two amplification theorems.
The first is a product theorem, in the spirit of XOR-lemmas: The
distinguishing advantage of the combination of two systems is at
most twice the product of the individual distinguishing
advantages. This bound 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 distinguishers.
A key technical tool of the paper is the proof of a tight two-way
correspondence, previously only known to hold in one direction,
between the distinguishing advantage of two systems and the
probability of winning an appropriately defined game.