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

<p>Here's an excerpt from <a href="https://courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/solution-03.pdf" rel="nofollow noreferrer">an exercise by Dominique Unruh</a>, showing formally that if FACTORING is NP-complete, then NP = coNP.</p>

<hr>

<p><a href="https://i.sstatic.net/eYyBM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eYyBM.png" alt="an exercise by Dominique Unruh, showing if FACTORING is NP-complete, then NP = coNP"></a></p>

<hr>

<p>If you are interested in research on the relationship between crypto and NP-completeness, I suggest reading Pass's paper <a href="https://ieeexplore.ieee.org/document/1663729" rel="nofollow noreferrer">Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness</a>.</p>

CC BY-SA 4.0
2019-02-02T05:10:18.643Z
2019-02-02T05:10:18.643Z
Sadeq Dousti
<p>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.</p>

<p>Any <em>useful</em> 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.</p>

<p>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).</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 4.0
2019-02-02T02:08:40.033Z
I found a nice set of slides for you... https://www.slideshare.net/alexprut/algorithms-and-complexity-cryptography-theory I think you will find complexity class UP more interesting....
Tayfun Pay
CC BY-SA 4.0
2019-04-23T21:25:48.290Z
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
<cc.complexity-theory><cr.crypto-security>
Would an NP-complete public key cryptosystem imply NP=co-NP?
Myria
# Would an NP-complete public key cryptosystem imply NP=co-NP?

(Asked by: username_0 on 2019-02-01)

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.

**Tags:** cc.complexity-theory, cr.crypto-security

> **Comments:**
> **username_1**: I found a nice set of slides for you... https://www.slideshare.net/alexprut/algorithms-and-complexity-cryptography-theory I think you will find complexity class UP more interesting....  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2019-02-02. Score: 3 | Accepted answer

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](https://courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/solution-03.pdf), 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](https://i.sstatic.net/eYyBM.png)](https://i.sstatic.net/eYyBM.png)

---

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](https://ieeexplore.ieee.org/document/1663729).


---

