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

7 Citations (Scopus)

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

Fingerprint

Turing machines
Heuristic algorithms
Amplification
Polynomials
Generator
Theorem
Resolve
Relativization
One-way Function
Zero-knowledge Proof
Proof System
Turing Machine
Heuristic algorithm
Completeness

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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.
Abadi, Martín ; Allender, Eric ; Broder, Andrei ; Feigenbaum, Joan ; Hemachandra, Lane A. / On generating solved instances of computational problems. Advances in Cryptology – CRYPTO 1988 - Proceedings. editor / Shafi Goldwasser. Springer Verlag, 1990. pp. 297-310 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{b0863ac721ce4681a6a90c3e5df287b7,
title = "On generating solved instances of computational problems",
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.",
author = "Mart{\'i}n Abadi and Eric Allender and Andrei Broder and Joan Feigenbaum and Hemachandra, {Lane A.}",
year = "1990",
month = "1",
day = "1",
language = "English (US)",
isbn = "9780387971964",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "297--310",
editor = "Shafi Goldwasser",
booktitle = "Advances in Cryptology – CRYPTO 1988 - Proceedings",
address = "Germany",

}

Abadi, M, Allender, E, Broder, A, Feigenbaum, J & Hemachandra, LA 1990, On generating solved instances of computational problems. in S Goldwasser (ed.), 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.

Advances in Cryptology – CRYPTO 1988 - Proceedings. ed. / Shafi Goldwasser. Springer Verlag, 1990. p. 297-310 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 403 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Abadi M, Allender E, Broder A, Feigenbaum J, Hemachandra LA. On generating solved instances of computational problems. In Goldwasser S, editor, Advances in Cryptology – CRYPTO 1988 - Proceedings. Springer Verlag. 1990. p. 297-310. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).