2
$\begingroup$

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.

$\endgroup$
  • 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
  • $\begingroup$ It's worth noting that from a cryptographic POV, you're making a common confusion: being in NP is not required. Membership in NP is a statement about worse-case complexity, but there are plenty of problems that are harder than NP and have infinite families of inputs on which they are in NP. The easy example is that the halting problem has an infinite family of inputs of every complexity. The properties you mention must hold for the infinite family we use, but we don't care if they don't hold for other inputs. $\endgroup$ – Stella Biderman Apr 23 at 21:25
2
$\begingroup$

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.

$\endgroup$

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.