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.
