<p>In a <a href="http://en.wikipedia.org/wiki/Ciphertext_indistinguishability#Indistinguishability_under_chosen-plaintext_attack_.28IND-CPA.29" rel="nofollow">CPA game</a>, a key pair $(sk,pk)$ is generated, and $pk$ is given to the adversary.
The adversary outputs a pair of messages $(m_0,m_1)$ in the message space, such that $|m_0|=|m_1|$. A random bit $b \in \{0,1\}$ is then generated, and $m_b$ is encrypted and returned as the cipher $c = E_{pk}(m_b ; r)$, where $r$ is the randomness used for encryption. The task of the adversary is to guess $b$ correctly.</p>

<p><strong>Lemma.</strong> There do not exist $r_0$ and $r_1$ such that $c = E_{pk}(m_0 ; r_0)$ and $c = E_{pk}(m_1 ; r_1)$.</p>

<p><strong>Proof.</strong> If such $r_0$ and $r_1$ exist, $c$ can be decrypted to both $m_0$ and $m_1$, which contradicts the uniqueness of decryption.</p>

<p><strong>Note.</strong> In some texts, uniqueness of decryption is not required. It is only required that decryption is unique with overwhelming probability. In such cases, the above lemma must be changed accordingly.</p>

<p>Now, assume that $\mathsf{P = NP}$. The adversary can then find in <strong>polynomial time</strong> whether there exists an $r$ (i.e., an $\mathsf{NP}$-witness) such that $c = E_{pk}(m_0 ; r)$. If so, the adversary outputs $b=0$. Otherwise, he outputs $b=1$.</p>

<p>Therefore, if $\mathsf{P = NP}$, there exists a polynomial-time adversary which always succeeds in the CPA game, and no encryption scheme will be CPA-secure.</p>

CC BY-SA 3.0
2013-12-24T22:45:28.303Z
Do we have to collapse NP all the way to P for this? Could P=UP have the same affect? And then it is still possible P to not equal NP.
Tayfun Pay
CC BY-SA 3.0
2013-12-25T16:12:53.950Z
@TayfunPay: Yes, that's right. The OP asked for the consequence of $\mathsf{P = NP}$ on CPA security, but as you pointed out, $\mathsf{P = UP}$ is enough. Even better, as Huck Bennett stated in a comment on the OP, non-existence of OWFs is enough for CPA insecurity. The relations are best described [Impagliazzo's worlds](http://cstheory.stackexchange.com/q/1026/873).
Sadeq Dousti
CC BY-SA 3.0
2013-12-25T21:39:17.847Z
@TayfunPay: On a second thought, $r$ is not required to be unique. In other words, there might be distinct $r, r'$ such that $E_{pk}(m;r) = E_{pk}(m;r')$. For instance, if $\hat E$ is a CPA-secure encryption, then $E$—defined as follows—is also a CPA-secure encryption: $E$ requires a random string which is one-bit longer than $\hat E$. Let $d(r)$ be equal to $r$, with the last bit discarded. Let $E_{pk}(m;r)$ be defined as $\hat E_{pk}(m; d(r))$. The encryption $E$ has the above property. **Bottom line:** $\mathsf{P = UP}$ is not necessarily enough.
Sadeq Dousti
CC BY-SA 3.0
2013-12-24T21:08:50.483Z
2015-01-12T10:07:00.737Z
2015-01-12T10:07:00.737Z
Sadeq Dousti
<p>I'm not talking about the <a href="http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29" rel="nofollow noreferrer">RSA</a>, <a href="http://en.wikipedia.org/wiki/El_Gamal" rel="nofollow noreferrer">El-gamal</a>, nor any specific encryption scheme. Rather, my question, as related to <a href="https://cstheory.stackexchange.com/questions/453/how-does-theoretical-computer-science-relate-to-security/7299#7299">this</a> and <a href="https://cstheory.stackexchange.com/questions/20084/cryptography-without-assumptions-seeking-an-overview">this</a> threads, is why the idea of Public-Key encryption scheme cannot be secure under CPA (which has equal power as eavesdropper in the public-key area) without the assumption that $P \neq NP$.</p>

<p>If $P=NP$ the task to compute a decision of "whether a secret key $S_k$ is the <em>complement</em> of the given public key $P_k$?" takes a poly time (where <em>complement</em> may be refer to <em>inverse in the Euler group</em> in RSA or <em>discrete-log</em> in El-Gamal or any other term but my question is general) is equal (in regard to the time complexity) to the task of "finding the actual complement $S_k$ from a given $P_k$ and additional public settings (as the group description etc.)" which will also take poly time.</p>

<ol>
<li>Does my last state seems logical/correct?</li>
<li>How can I further formalize it?</li>
</ol>

CC BY-SA 3.0
2013-12-24T21:11:21.813Z
I don't understand your second paragraph, but the answer is simply that OWFs (and in particular TDPs) cannot exist if $P \neq NP$.
Huck Bennett
<cc.complexity-theory><cr.crypto-security><big-picture><np><p-vs-np>
Public-key encryption without the assumption that $P \neq NP$
Bush
# Public-key encryption without the assumption that $P \neq NP$

(Asked by: username_0 on 2013-12-23)

I'm not talking about the [RSA](http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29), [El-gamal](http://en.wikipedia.org/wiki/El_Gamal), nor any specific encryption scheme. Rather, my question, as related to [this](https://cstheory.stackexchange.com/questions/453/how-does-theoretical-computer-science-relate-to-security/7299#7299) and [this](https://cstheory.stackexchange.com/questions/20084/cryptography-without-assumptions-seeking-an-overview) threads, is why the idea of Public-Key encryption scheme cannot be secure under CPA (which has equal power as eavesdropper in the public-key area) without the assumption that $P \neq NP$.

If $P=NP$ the task to compute a decision of "whether a secret key $S\_k$ is the *complement* of the given public key $P\_k$?" takes a poly time (where *complement* may be refer to *inverse in the Euler group* in RSA or *discrete-log* in El-Gamal or any other term but my question is general) is equal (in regard to the time complexity) to the task of "finding the actual complement $S\_k$ from a given $P\_k$ and additional public settings (as the group description etc.)" which will also take poly time.

1. Does my last state seems logical/correct?
2. How can I further formalize it?

**Tags:** cc.complexity-theory, cr.crypto-security, big-picture, np, p-vs-np
> **Comments:**
> **username_1**: I don't understand your second paragraph, but the answer is simply that OWFs (and in particular TDPs) cannot exist if $P \neq NP$.  

---

## 1 answers

### Answer by username_2 on 2013-12-24. Score: 7 | Accepted answer

In a [CPA game](http://en.wikipedia.org/wiki/Ciphertext_indistinguishability#Indistinguishability_under_chosen-plaintext_attack_.28IND-CPA.29), a key pair $(sk,pk)$ is generated, and $pk$ is given to the adversary.
The adversary outputs a pair of messages $(m\_0,m\_1)$ in the message space, such that $|m\_0|=|m\_1|$. A random bit $b \in \{0,1\}$ is then generated, and $m\_b$ is encrypted and returned as the cipher $c = E\_{pk}(m\_b ; r)$, where $r$ is the randomness used for encryption. The task of the adversary is to guess $b$ correctly.

**Lemma.** There do not exist $r\_0$ and $r\_1$ such that $c = E\_{pk}(m\_0 ; r\_0)$ and $c = E\_{pk}(m\_1 ; r\_1)$.

**Proof.** If such $r\_0$ and $r\_1$ exist, $c$ can be decrypted to both $m\_0$ and $m\_1$, which contradicts the uniqueness of decryption.

**Note.** In some texts, uniqueness of decryption is not required. It is only required that decryption is unique with overwhelming probability. In such cases, the above lemma must be changed accordingly.

Now, assume that $\mathsf{P = NP}$. The adversary can then find in **polynomial time** whether there exists an $r$ (i.e., an $\mathsf{NP}$-witness) such that $c = E\_{pk}(m\_0 ; r)$. If so, the adversary outputs $b=0$. Otherwise, he outputs $b=1$.

Therefore, if $\mathsf{P = NP}$, there exists a polynomial-time adversary which always succeeds in the CPA game, and no encryption scheme will be CPA-secure.

> **Comments:**
> **username_3**: Do we have to collapse NP all the way to P for this? Could P=UP have the same affect? And then it is still possible P to not equal NP.  
> **username_2**: @TayfunPay: Yes, that's right. The OP asked for the consequence of $\mathsf{P = NP}$ on CPA security, but as you pointed out, $\mathsf{P = UP}$ is enough. Even better, as Huck Bennett stated in a comment on the OP, non-existence of OWFs is enough for CPA insecurity. The relations are best described [Impagliazzo's worlds](http://cstheory.stackexchange.com/q/1026/873).  
> **username_2**: @TayfunPay: On a second thought, $r$ is not required to be unique. In other words, there might be distinct $r, r'$ such that $E_{pk}(m;r) = E_{pk}(m;r')$. For instance, if $\hat E$ is a CPA-secure encryption, then $E$—defined as follows—is also a CPA-secure encryption: $E$ requires a random string which is one-bit longer than $\hat E$. Let $d(r)$ be equal to $r$, with the last bit discarded. Let $E_{pk}(m;r)$ be defined as $\hat E_{pk}(m; d(r))$. The encryption $E$ has the above property. **Bottom line:** $\mathsf{P = UP}$ is not necessarily enough.  

---

