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

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.


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)


Zbl 0444.94013
Full Text: DOI