×

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.

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)

Citations:

Zbl 0444.94013
PDFBibTeX XMLCite
Full Text: DOI