Abstract
We consider the efficient generation of solved instances of computational problems. In particular, we consider invulnerable generators. Let S be a subset of 0,1* and M be a Turing Machine that accepts S; an accepting computation w of M on input x is called a “witness” that x ∈ S. Informally, a program is an α-invulnerable generator if, on input 1n, it produces instance-witness pairs <x, w>, with |x| = n, according to a distribution under which any polynomial-time adversary who is given x fails to find a witness that x ∈ S, with probability at least α, for infinitely many lengths n.