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 computational hardness 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 (e.g. epsilon = 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 PRO for any epsilon < 1. into a strong PRO by proving that the intuitive construction of applying an extractor to an appropriate number of independent weak PRG outputs yields a strong PRO. This improves strongly over the best previous construction for security amplification of PRGs which does not work for epsilon >= 1/2 and requires the seed of the constructed strong PRO to be very long.
