On Generating Hard Instances of Problems in NP

We consider the efficient generation of hard instances of NP problems with known solutions. For example, one may wish to generate pairs , where f is a boolean formula and a is a satisfying assignment, give the secret a to one user U, publish the formula f, and remain reasonably confident that a polynomial-time adversary would be unable to "crack" U's identity by discovering any satisfying assignment a' for f. We propose a precise definition of "the generation of hard instances" and prove two results: The first is a completeness theorem, which exhibits a generator that produces a distribution of instances that is secure against polynomial-time adversaries if indeed any generable distribution is secure; the second is an amplification theorem, which shows how to enhance the security of the distribution generated.