Is the reduction from left-or-right IND-CPA to real-or-random IND-CPA tight?

Question

A modern trend in cryptography consists of defining security as rigorously as possible, and then designing schemes which are secure according to those definitions. Proving security comes in the form of reducing one scheme to a more basic problem or scheme. Furthermore, there are many different ways of formalizing security, and equivalence between security definitions is shown via reductions as well.

The concrete security approach for reductions, as introduced by Bellare, Desai, Jokipii, and Rogaway in FOCS '97, moves away from polynomial reductions and instead focuses on finding concrete bounds, so as to provide a more nuanced view of security. They discuss various formalizations of security for symmetric encryption schemes, including indistinguishability under chosen plaintext attacks (IND-CPA). Two variants of IND-CPA they come up with are left-or-right (LoR) and real-or-random (RoR), which they prove to be equivalent in the following sense:

Let $\mathcal{E}$ be an encryption scheme. For all adversaries with time complexity $t$ making at most $q$ queries to $\mathcal{E}$ totalling at most $\mu$ bits, $$\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu) \le \mathbf{Adv}_{\mathcal{E}}^{\text{lor-cpa}}(t,q,\mu) \le 2\cdot\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu)\enspace.$$ Note that the bound on the right-hand side includes a factor 2. There are encryption schemes for which the factor of two is absent. For example, for the identity function we have that $\mathbf{Adv}^{\text{ror-cpa}}(t,q,\mu)$ approaches $\mathbf{Adv}^{\text{lor-cpa}}(t,q,\mu) = 1$ for $\mu\to\infty$, which leads me to my question.

Does there exist an encryption scheme $\mathcal{E}$ for which $$\mathbf{Adv}_{\mathcal{E}}^{\text{lor-cpa}}(t,q,\mu) = 2\cdot\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu)\ ?$$

Answer 1

Here's an artificial example: Start with some secure encryption scheme with encryption function $\mathcal{E}(\cdot)$, and construct a new scheme with encryption function $\mathcal{E}'(\cdot)$, which for any input message $m$ copies the first bit, $b$, of the message, and outputs $b||\mathcal{E}(m)$, where $||$ denotes concatenation.

For such a scheme, there exists a LoR adversary $\mathcal{A}_{lor}$ with Advantage 1 using only one query. $\mathcal{A}_{lor}$ merely has to submit a query $(m_0,m_1)$, where $m_0$ starts with a 0 and $m_1$ starts with a 1. Assuming wlog that the Challenger has a coin $c$ and returns the ciphertext $\mathcal{E}'(m_c)$, $\mathcal{A}_{lor}$ then bases its guess for the value of the Challenger's coin on the first bit of the returning ciphertext (i.e. for a returning ciphertext with first bit $b$ it outputs the guess $c = b$). This guess will always succeed, because with such a query, the first bit of the ciphertext does indeed equal the Challenger's coin $c$.

However, the RoR advantage for any adversary similarly restricted to just one query can be no greater than $1/2$ (again assuming that the underlying scheme we started with is secure). Because the underlying scheme is secure, any adversary $\mathcal{A}_{ror}$ must base its guess entirely on the first bit of the resulting ciphertext and whether that first bit is equal to the first bit of its query. Wlog we can assume $\mathcal{A}_{ror}$ submits a query $(q)$ with the first bit set to 1. If the output ciphertext starts with a 1 then $\mathcal{A}_{ror}$ guesses the Challenger is running the $Real$ oracle, and if the output starts with 0 it guesses the Challenger is running the $Random$ oracle.

Recall the definition of the RoR adversarial advantage function,

$$\mathbf{Adv}^{ror-cpa}_{\mathcal{E}',\mathcal{A}_{ror}}(k) = \Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] - \Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real].$$ If the Challenger is running the $Real$ oracle then the first bit of the output ciphertext will be a 1 with probability 1, and so $\Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1$. However, if the Challenger is running the $Random$ oracle, then it will return the ciphertext $\mathcal{E}'(*)$ for some random string $*$ equal in length to the query $q$. The first bit of $*$ will be a 1 with probability $1/2$, and so $\Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1/2$.

As such, for adversaries restricted to one query, the maximum RoR advantage versus $\mathcal{E}'$ is half the maximum LoR advantage.

Answer 2

One can't "get rid of" the factor 2.
However, there might be a way to replace it with
$2\hspace{-0.03 in}-\hspace{-0.03 in}o(1)\:$ where that depends on $q$ and the advantage.

$||$ is concatenation.
Start with some encryption scheme $\mathcal{E}'\hspace{-0.04 in}$, and for any
integer $n$ and probability $p$, let $\mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}$ be given by
$\;\;\;$ if $\: \operatorname{length}(m) < n \:$ then output $\: 000\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;$ with probability $\: 1\hspace{-0.05 in}-\hspace{-0.03 in}(2\hspace{-0.05 in}\cdot \hspace{-0.05 in}p) \:$, $\:$ output $\: 000\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;$ choose a bit $b$ uniformly at random
$\;\;\;$ if $m$ is all-$b$ then output $\: 1b1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m) \:$ else output $\: 1b\hspace{.02 in}0\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
.

(Decryption just removes the first three bits and then applies $\mathcal{D}\hspace{.02 in}'$.)