Score:0

Does CPA model the challenge plaintext are the same

co flag

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

Score:2
ng flag

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.

Zi-Yuan Liu avatar
co flag
Thank you for your clear explanation.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.