An information-theoretic approach to hardness amplification

Abstract

Consider two independent games of chance, G and H, which can be won with probability at most β and γ, respectively. Then it can be shown that the game consisting of winning both G and H can be won with probability at most β γ . 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.