0
$\begingroup$

For a CPA-secure encryption scheme, suppose that there is an adversary who can find that the two ciphertexts are encrypted from the same plaintext.

Is this encryption scheme still CPA secure?

Or, CPA security only models whether the adversary can find out what plaintext is encrypted, regardless of the above situation

$\endgroup$
2
$\begingroup$

Recall that the adversary in the IND-CPA security game gets a "left-right oracle":

$$\mathsf{LR}(m_0,m_1) := \mathsf{Enc}_{pk}(m_b)$$

where $b\in\{0,1\}$ is a secret bit that the adversary has to try to recover.

suppose that there is an adversary who can find that the two ciphertexts are encrypted from the same plaintext.

In the above, you can see that there is only one ciphertext though --- $\mathsf{LR}(m_0,m_1)$ returns the single ciphertext $\mathsf{Enc}_{pk}(m_b)$. This means I am not 100% sure of what you intend to ask. If we modify your question to:

Suppose there is an adversary $\mathcal{A}$ who, given two arbitrary ciphertexts $c, c'$ encrypted under the same public key, can determine whether they encrypt the same thing --- meaning can answer the question $$\mathsf{Dec}_{sk}(c)\stackrel{?}{=}\mathsf{Dec}_{sk}(c')$$ Can this adversary break IND-CPA security?

The answer is yes. The attack is simple --- for distinct $m_0, m_1, m_2$, query $c\gets \mathsf{LR}(m_0, m_1)$, $c'\gets \mathsf{LR}(m_2, m_1)$. If the adversary determines that $c, c'$ encrypt the same message, then both $\mathsf{LR}$ queries encrypted $m_1$, e.g. $b = 1$. Otherwise, $b = 0$.

This is actually the foundation of a fairly fundamental result in public-key encryption.

Deterministic public-key encryption is impossible.

I think the citation for this is Goldwasser-Micali 1982, but regardless of the particulars it is one of the "early" results in theoretical cryptography. To prove this, all you need to do is notice that if $\mathsf{LR}$ is deterministic, building the adversary $\mathcal{A}$ we mentioned before is quite simple (I'll let you think of how). We can then mount the attack we mentioned before.

$\endgroup$
1
  • $\begingroup$ Thank you for your clear explanation. $\endgroup$ Sep 17 at 7:06

Your Answer

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

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