On generating solved instances of computational problems

Martín Abadi, Eric Allender, Andrei Broder, Joan Feigenbaum, Lane A. Hemachandra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 1988 - Proceedings
EditorsShafi Goldwasser
PublisherSpringer Verlag
Pages297-310
Number of pages14
ISBN (Print)9780387971964
DOIs
StatePublished - Jan 1 1990
EventConference on Theory and Applications of Cryptography, CRYPTO 1988 - Santa Barbara, United States
Duration: Aug 21 1988Aug 25 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume403 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherConference on Theory and Applications of Cryptography, CRYPTO 1988
CountryUnited States
CitySanta Barbara
Period8/21/888/25/88

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On generating solved instances of computational problems'. Together they form a unique fingerprint.

  • Cite this

    Abadi, M., Allender, E., Broder, A., Feigenbaum, J., & Hemachandra, L. A. (1990). On generating solved instances of computational problems. In S. Goldwasser (Ed.), 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. https://doi.org/10.1007/0-387-34799-2_23