Bitte wählen Sie ihr Lieferland und ihre Kundengruppe
The first part of this paper gives results about promise problems. A 'promise problem' is a formulation of a partial decision problem that is useful for describing cracking problems for public-key cryptosystems (PKCS). We prove that every NP-hard promise problem is uniformly NP-hard, and we show that a number of results and a conjecture about promise problems are equivalent to separability assertions that are the natural analogues of wellknown results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second part of the paper studies more appropriate measures for PKCS. It will follow that there exist PKCS that cannot be cracked in polynomial time (and that satisfy other reasonable assumptions) only if P.N.E.U.