Are there deterministic private-key encryption schemes that are CPA-secure?

Question

I'm assuming there can't be such schemes because CPA-security is equivalent to CPA-security for multiple encryptions, and an adversary can distinguish between $(\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_0))$ and $(\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_1))$ if Enc is deterministic, hence there is no deterministic symmetric encryption scheme that is CPA-secure.

However, I can't see how an adversary might distinguish only one encryption from another.

The CPA indistinguishability experiment $\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n)$:

Let $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ be any encryption scheme, $\mathcal A$ any adversary, and $n$ the security parameter.

1. A key $k$ is generated by running $\mathsf{Gen}(1^n)$.
2. The adversary $\mathcal A$ is given input $1^n$ and oracle access to $\mathsf{Enc}_k(\cdot)$, and outputs a pair of messages $m_0$, $m_1$ of the same length.
3. A uniform bit $b \in \{0, 1\}$ is chosen, and then a ciphertext $c \leftarrow \mathsf{Enc}_k(m_b)$ is computed and given to $\mathsf A$.
4. The adversary $\mathcal A$ continues to have oracle access to $\mathsf{Enc}_k(\cdot)$, and outputs a bit $b'$.
5. The experiment is defined to be $1$ if $b' = b$, and $0$ otherwise.

Definition of CPA-security:

A private-key encryption scheme $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ has indistinguishable encryptions under a chosen-plaintext attack, or is CPA-secure, if for all probabilistic polynomial-time adversaries $\mathcal A$ there is a negligible function $\mathsf{negl}$ such that $$\text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1] \leq \frac{1}{2} + \mathsf{negl}(n),$$ where the probability is taken over the randomness used by $\mathcal A$, as well as the randomness used in the experiment.

Answer 1

Summarizing fkraiem's comment, a CPA-secure encryption scheme can not be deterministic.

The reason is simple: the attacker is challenged to distinguish between the encryption of $m_0$ and $m_1$, but he also has access to an encryption oracle (and he can query the oracle at whatever input he wants!). If the encryption scheme yields the same ciphertexts each time it's queried on the same plaintexts, the attacker can simply ask the oracle for an encryption of $m_0$ and an encryption of $m_1$, and compare which one is equal to the given challenge ciphertext.

Answer 2

As it was already mentioned by @fkraiem and summarized by @Daniel, deterministic encryption scheme cannot be secure under standard definition of CPA-security. But as deterministic encryption can be quite useful for some purposes (for example, encrypting database keys and entries), there is a weakened definition of CPA-security known as deterministic CPA-security which assumes that encryptor never encrypts the same message twice (for example, messages being encrypted are chosen at random from large message space or uniqueness of the message is inherent in its structure).

Deterministic CPA experiment differs from standard one in that assuming $q$ queries of the form $(m_{i,0}, m_{i, 1}), i \in 1,...,q$ to the encryption oracle, all $m_{1,0},...,m_{q,0}$ are required to be distinct, as well as $m_{1,1},...,m_{q,1}$.

There exist deterministic encryption schemes that satisfy deterministic CPA-security definition:

1. SIV (synthetic IV), which basically replaces randomized IVs or nonces in a standard CPA-secure encryption scheme with deterministically generated ones. It is defined as follows: $$E_{det}((k_1, k_2), m) = E(k_2, m; r = F(k_1, m)),$$ $$D_{det}((k_1, k_2), (m, r)) = D(k_2, m; r),$$ where $(E, D)$ - CPA-secure (randomized) encryption scheme, $F$ - secure PRF.

2. Wide PRP or wide block encryption basically relies on an idea that using plain PRP on distinct messages gives a deteministic CPA-secure encryption scheme. The problems is that most common PRPs work on small message spaces (for example $\{0, 1\}^{128}$), so we need a way to construct PRPs with much bigger message spaces from PRPs with small message spaces. Examples of such constructions are XCB and EME, which were proposed by IEEE P1619 as encryption schemes for shared storage.

Answer 3

There is no deterministic private-key encryption scheme that is CPA-secure.
Consider an adversary $\mathcal A$ that does the following:

1. On input $1^n$ and $\mathsf{Enc}_k(\cdot)$ $\mathcal A$ chooses some message $m_0 \in \{1,0\}^n$ and queries the oracle on message $m_0$ to obtain the ciphertext $c_0$ of message $m_0$.
2. $\mathcal A$ chooses some message $m_1 \in \{1,0\}^n$ that is distinct from $m_0$. $\mathcal A$ returns $(m_0, m_1)$ to the challenger.
3. On recieving the challenge ciphertext $c$ $\mathcal A$ returns bit $b' = 0$ if $c = c_0$, and $1$ otherwise.
   Notice that $\mathcal A$ terminates in polynomial time.

Let $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ be a deterministic private-key encryption scheme.

We conduct the CPA indistinguishability experiment $\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n)$.
If $b = 0$ then $\mathsf{Enc}_k(m_0) = c = c_0 = \mathsf{Enc}_k(m_0)$. Hence $\mathcal A$ succeds with probability one.
If $b = 1$ then $\mathsf{Enc}_k(m_1) = c \not= c_0 = \mathsf{Enc}_k(m_0)$, because for every key $k$, and every $m \in \{1,0\}$, it holds that $\mathsf{Dec}_k(\mathsf{Enc}_k(m)) = m$ (i.e. $\mathsf{Enc}$ is injective). Thus $\mathcal A$ succeds with probability one.
Together we have \begin{eqnarray*} &&\text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1 | b=0] \cdot \text{Pr}[b=0] + \text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1 | b=1] \cdot \text{Pr}[b=1]\\ &=&\text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1] =1 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} = 1 > \frac{1}{2} + \mathsf{negl}(n) \end{eqnarray*} For all negligible functions $\mathsf{negl}$.