### 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 a-invulnerable generator if, on input 1^{n}, 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 a, for infinitely many lengths n. The question of which sets have invulnerable generators is intrinsically appealing theoretically, and the results can be applied to the generation of test data for heuristic algorithms and to the theory of zero-knowledge proof systems. The existence of invulnerable generators is closely related to the existence of cryptographically secure one-way functions. We prove three theorems about invulnerability. The first addresses the question of which sets in NP have invulnerable generators, if indeed any NP sets do. The second addresses the question of how invulnerable these generators are. Theorem (Completeness): If any set in NP has an α-invulnerable generator, then SAT has one. Theorem (Amplification): If S ϵ NP has a β-invulnerable generator, for some constant β ϵ (0,1), then S has an α-invulnerable generator, for every constant α ϵ (0,1). Our third theorem on invulnerability shows that one cannot, using techniques that rela-tivize, resolve the question of whether the assumption that P ≠ NP alone suffices to prove the existence of invulnerable generators. Clearly there are relativized worlds in which invulnerable generators exist; in all of these worlds, P ≠ NP. The more subtle question, which we resolve in our third theorem, is whether there are also relativized worlds in which P ≠ NP and invulnerable generators do not exist. Theorem (Relativization): There is an oracle relative to which P ≠ NP but there are no invulnerable generators.

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology – CRYPTO 1988 - Proceedings |

Editors | Shafi Goldwasser |

Publisher | Springer Verlag |

Pages | 297-310 |

Number of pages | 14 |

ISBN (Print) | 9780387971964 |

State | Published - Jan 1 1990 |

Event | Conference on Theory and Applications of Cryptography, CRYPTO 1988 - Santa Barbara, United States Duration: Aug 21 1988 → Aug 25 1988 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 403 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | Conference on Theory and Applications of Cryptography, CRYPTO 1988 |
---|---|

Country | United States |

City | Santa Barbara |

Period | 8/21/88 → 8/25/88 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Advances in Cryptology – CRYPTO 1988 - Proceedings*(pp. 297-310). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 403 LNCS). Springer Verlag.

}

*Advances in Cryptology – CRYPTO 1988 - Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 403 LNCS, Springer Verlag, pp. 297-310, Conference on Theory and Applications of Cryptography, CRYPTO 1988, Santa Barbara, United States, 8/21/88.

**On generating solved instances of computational problems.** / Abadi, Martín; Allender, Eric; Broder, Andrei; Feigenbaum, Joan; Hemachandra, Lane A.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On generating solved instances of computational problems

AU - Abadi, Martín

AU - Allender, Eric

AU - Broder, Andrei

AU - Feigenbaum, Joan

AU - Hemachandra, Lane A.

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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 a-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 a, for infinitely many lengths n. The question of which sets have invulnerable generators is intrinsically appealing theoretically, and the results can be applied to the generation of test data for heuristic algorithms and to the theory of zero-knowledge proof systems. The existence of invulnerable generators is closely related to the existence of cryptographically secure one-way functions. We prove three theorems about invulnerability. The first addresses the question of which sets in NP have invulnerable generators, if indeed any NP sets do. The second addresses the question of how invulnerable these generators are. Theorem (Completeness): If any set in NP has an α-invulnerable generator, then SAT has one. Theorem (Amplification): If S ϵ NP has a β-invulnerable generator, for some constant β ϵ (0,1), then S has an α-invulnerable generator, for every constant α ϵ (0,1). Our third theorem on invulnerability shows that one cannot, using techniques that rela-tivize, resolve the question of whether the assumption that P ≠ NP alone suffices to prove the existence of invulnerable generators. Clearly there are relativized worlds in which invulnerable generators exist; in all of these worlds, P ≠ NP. The more subtle question, which we resolve in our third theorem, is whether there are also relativized worlds in which P ≠ NP and invulnerable generators do not exist. Theorem (Relativization): There is an oracle relative to which P ≠ NP but there are no invulnerable generators.

AB - 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 a-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 a, for infinitely many lengths n. The question of which sets have invulnerable generators is intrinsically appealing theoretically, and the results can be applied to the generation of test data for heuristic algorithms and to the theory of zero-knowledge proof systems. The existence of invulnerable generators is closely related to the existence of cryptographically secure one-way functions. We prove three theorems about invulnerability. The first addresses the question of which sets in NP have invulnerable generators, if indeed any NP sets do. The second addresses the question of how invulnerable these generators are. Theorem (Completeness): If any set in NP has an α-invulnerable generator, then SAT has one. Theorem (Amplification): If S ϵ NP has a β-invulnerable generator, for some constant β ϵ (0,1), then S has an α-invulnerable generator, for every constant α ϵ (0,1). Our third theorem on invulnerability shows that one cannot, using techniques that rela-tivize, resolve the question of whether the assumption that P ≠ NP alone suffices to prove the existence of invulnerable generators. Clearly there are relativized worlds in which invulnerable generators exist; in all of these worlds, P ≠ NP. The more subtle question, which we resolve in our third theorem, is whether there are also relativized worlds in which P ≠ NP and invulnerable generators do not exist. Theorem (Relativization): There is an oracle relative to which P ≠ NP but there are no invulnerable generators.

UR - http://www.scopus.com/inward/record.url?scp=84916256739&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84916256739&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84916256739

SN - 9780387971964

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 297

EP - 310

BT - Advances in Cryptology – CRYPTO 1988 - Proceedings

A2 - Goldwasser, Shafi

PB - Springer Verlag

ER -