# An Information-theoretic Approach to Hardness Amplification

## Ueli Maurer

```
```Consider two independent games of chance, $G$ and $H$, which can be
won with probability at most $\beta$ and $\gamma$,
respectively. Then it can be shown that the game consisting of
winning both $G$ * and*} $H$ can be won with probability at most
$\beta\gamma$. If the bounds on the winning probability are only due
to the computational hardness of the problems and the computational
complexity constraints of the game solver algorithm, then the
analogous statement is not trivial but indeed holds in an
approximate sense under certain conditions.

This paper provides a general information-theoretic treatment of
this result, showing that it is an abstract statement that is
independent of complexity-theoretic considerations and exhibiting
explicitly the requirement that a given game instance must be
clonable. The core of the proof is a lemma on multi-argument
conditional probability distributions.

The amplification statement can be generalized to an
arbitrary number of independent games, making the winning
probability exponentially small in the number of such games.