The complexity of promise problems with applications to public-key cryptography. (English) Zbl 0592.94012

Even, Shimon; Selman, Alan L.; Yacobi, Yacov

Inf. Control 61, 159-173 (1984).

Summary: A ”promise problem” is a formulation of a partial decision problem. Complexity issues about promise problems arise from considerations about cracking problems for public-key cryptosystems. Using a notion of Turing reducibility between promise problems, this paper disproves a conjecture made by S. Even and Y. Yacobi [Lect. Notes Comput. Sci. 85, 195-207 (1980; Zbl 0444.94013)], that would imply nonexistence of public- key cryptosystems with NP-hard cracking problems. In its place a new conjecture is raised having the same consequence. In addition, the new conjecture implies that NP-complete sets cannot be accepted by Turing machines that have at most one accepting computation for each input word.

MSC:

94A60	Cryptography
68P25	Data encryption (aspects in computer science)
03B25	Decidability of theories and sets of sentences
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

partial decision problem; Turing reducibility; NP-hard cracking problems; NP-complete sets; Turing machines

Citations:

Zbl 0444.94013