# Would an NP-complete public key cryptosystem imply NP=co-NP?

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.

• I found a nice set of slides for you... slideshare.net/alexprut/… I think you will find complexity class UP more interesting.... – Tayfun Pay Feb 2 '19 at 2:08
• 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. – Stella Biderman Apr 23 '19 at 21:25 