# A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch

## Ueli Maurer and Stefano Tessaro

```
```It is well known that two random variables $X$ and $Y$ with the same
range can be viewed as being equal (in a well-defined sense) with
probability $1-d(X,Y)$, where $d(X,Y)$ is their statistical
distance, which in turn is equal to the best distinguishing
advantage for $X$ and $Y$. In other words, if the best
distinguishing advantage for $X$ and $Y$ is $\epsilon$, then with
probability $1-\epsilon$ they are completely indistinguishable.
This statement, which can be seen as an information-theoretic
version of a hardcore lemma, is for example very useful for proving
indistinguishability amplification results.

In this paper we prove the computational version of such a hardcore
lemma, thereby extending the concept of hardcore sets from the context
of hard computational problems (like inverting a one-way function)
to the context of computational indistinguishability. This paradigm
promises to have many applications in cryptography and complexity
theory. It is proven both in a non-uniform and a uniform
setting.
For example, for a weak pseudorandom generator (PRG) for which the
(computational) distinguishing advantage is known to be bounded by
$\epsilon$ (e.g. $\epsilon=\frac{1}{2}$), one can define an event on the
seed of the PRG which has probability at least $1-\epsilon$ and such
that, conditioned on the event, the output of the PRG is essentially
indistinguishable from a string with almost maximal min-entropy, namely
$\log(1/(1-\epsilon))$ less than its length. As an application, we show
an optimally efficient construction for converting a weak PRG for any
$\epsilon < 1$ into a strong PRG by proving that the intuitive
construction of applying an extractor to an appropriate number of
independent weak PRG outputs yields a strong PRG. This improves strongly
over the best previous construction for security amplification of PRGs
(the XOR of several weak PRG outputs) which does not work for
$\epsilon \geq \frac{1}{2}$ and also requires the seed of the constructed
strong PRG to be very long.