Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of a mystery to me.

Any useful cryptosystem has to be in NP or co-NP. Using digital signatures as an example, you obviously need signature verification to be in P. Similarly, key generation needs to be in P, or good luck generating keys.

To say that a signature system is an NP-complete problem would really mean that the decision problem of determining whether the signature for an arbitrary message is less than some integer is NP-hard. That definition would imply that deriving whether the private key is less than some integer is also NP-hard. For both these problems, the certificate is the full answer, which shows membership in NP (and NP-complete).

But then the complement to these two problems, determining whether their full answer is not less than some number, is a simple reduction to the "less than" version. Does this mean that the existence of such an NP-complete signature system implies NP = co-NP?

My argument above is highly informal. For example, checking whether an alleged private key in fact matches a given public key may not be straightforward and possibly not in P. (It is definitely in BPP, though: try signing random messages.) Also, many public-key signature systems may have multiple valid signatures (DSA, ECDSA) or multiple matching private keys (RSA). These things throw wrenches into the works.

  • 1
    $\begingroup$ I found a nice set of slides for you... slideshare.net/alexprut/… I think you will find complexity class UP more interesting.... $\endgroup$ – Tayfun Pay Feb 2 at 2:08

Your argument is correct about the FACTORING problem, but it does not automatically generalize to all public-key cryptosystems.

Here's an excerpt from an exercise by Dominique Unruh, showing formally that if FACTORING is NP-complete, then NP = coNP.

an exercise by Dominique Unruh, showing if FACTORING is NP-complete, then NP = coNP

If you are interested in research on the relationship between crypto and NP-completeness, I suggest reading Pass's paper Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.