In a given public key cryptosystem, if the problem of determining the private key from the public key is NP-complete or co-NP-complete, does that imply that NP = co-NP?

Complexity theory is definitely not my specialty. I ask because from what I read that it seems that this would be the case (informally):

Determining the private key from the public key can be converted to a decision problem by asking whether a given bit of the private key is $1$. The complement of this problem is then asking whether a given bit is not $1$ (that is, $0$). For both problems, the entire private key is a certificate. Clearly they are polynomial-time reducible to each other.

If either decision problem were NP-complete or co-NP-complete, wouldn't that imply NP = co-NP?

  • $\begingroup$ The title and body don't match. Also, you mean and instead of or? There is an answer in CS for this intersection, and this question might be asked there, too. $\endgroup$ – kelalaka Jan 31 '19 at 22:32
  • $\begingroup$ @kelalaka Fixed the title; thanks. I think that one would imply the other, so using "or" versus "and" would be the same thing? $\endgroup$ – Myria Jan 31 '19 at 22:47
  • $\begingroup$ Or only false if both are false. So this has three sub-questions; the problem of determining the private key from the public key (1) is NP-complete, (2) is co-NP-complete (3) NP-complete and co-NP-complete. $\endgroup$ – kelalaka Jan 31 '19 at 22:53
  • $\begingroup$ @kelalaka If either one is NP-complete or co-NP-complete, that they are their own complement (within polynomial-time reduction) would imply NP = co-NP, right? $\endgroup$ – Myria Jan 31 '19 at 22:57

Your Answer

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

Browse other questions tagged or ask your own question.