Public-key encryption without the assumption that $P \neq NP$ I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this 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.


Does my last state seems logical/correct?
How can I further formalize it?
In a CPA game, 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.