The complexity of promise problems with applications to public-key cryptography.

*(English)*Zbl 0592.94012Summary: 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) |