7
$\begingroup$

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.

  1. Does my last state seems logical/correct?
  2. How can I further formalize it?
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I don't understand your second paragraph, but the answer is simply that OWFs (and in particular TDPs) cannot exist if $P \neq NP$. $\endgroup$
    – Huck Bennett
    Commented Dec 24, 2013 at 21:11

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Tayfun Pay
    Commented Dec 24, 2013 at 22:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Commented Dec 25, 2013 at 16:12
  • $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Commented Dec 25, 2013 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.