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

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.

My question is, is it possible to get rid of the factor 2, or does there exist an encryption scheme for which the LoR-cpa security is double its RoR-cpa security?

-

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 $m$ has no ones and at least $n$ zeros then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.03 in}(m) \: = \: 00\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else if $m$ has no zeros and at least $n$ ones then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 1\hspace{-0.03 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 0\hspace{-0.02 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
.

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

-