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

Ueli Maurer and Stefano Tessaro

Theory of Cryptography — TCC 2010, Lecture Notes in Computer Science, Springer-Verlag, vol. 5978, pp. 237–254, Feb 2010.

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 $ϵ$ , then with probability $1 - ϵ$ 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 $ϵ$ (e.g. $ϵ = \frac{1}{2}$ ), one can define an event on the seed of the PRG which has probability at least $1 - ϵ$ 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 - ϵ))$ less than its length. As an application, we show an optimally efficient construction for converting a weak PRG for any $ϵ < 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 $ϵ \geq \frac{1}{2}$ and also requires the seed of the constructed strong PRG to be very long.

BibTeX Citation

@inproceedings{MauTes10,
    author       = {Ueli Maurer and Stefano Tessaro},
    title        = {A Hardcore Lemma for Computational   Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch},
    editor       = {Daniele Micciancio},
    booktitle    = {Theory of Cryptography --- TCC 2010},
    pages        = {237--254},
    series       = {Lecture Notes in Computer Science},
    volume       = {5978},
    year         = {2010},
    month        = {2},
    publisher    = {Springer-Verlag},
}