# 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. 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)\ ?$$

• In other words, where Bellare et al proved that the max LOR Advantage can never be greater than twice the max ROR Advantage, you are asking whether that upper bound is in fact an equality (i.e. whether max Adv LOR $= 2 \cdot$ max Adv ROR for all encryption schemes)? – J.D. Jun 4 '15 at 1:42
• Not for all encryption schemes, but does there exist an encryption scheme for which max Adv LOR = $2\cdot$ max Adv ROR. – pxdnr Jun 5 '15 at 4:27
• OK that clarifies the question for me. Of course there are encryption schemes where max Adv LOR = max Adv ROR = 1 (e.g. where the encryption function is the identity function). So we know Bellare's upper bound is not always met. But you want to know if it is ever met at all. That's a good question, so I am upvoting it. Unfortunately I don't know the answer. – J.D. Jun 5 '15 at 12:30
• I incorporated your comment into the question to improve it. – pxdnr Jun 6 '15 at 15:16
• While writing my answer, I realized that the RoR advantage versus $\mathcal{E}$ = the identity function doesn't actually exactly equal 1, because the random oracle can always by chance generate and 'encrypt' the same string as the query. Of course this probability very quickly becomes extremely small, and as such the RoR advantage very quickly approaches 1 as the total bit-length of the queries grows. But this is not like the LoR advantage, which can equal 1 immediately, even with a query where the left and right messages are each a single bit long. – J.D. Jun 7 '15 at 17:44

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.

$$\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.

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}'$.)

• Do I understand your response correctly in that it should be a construction for which the lor advantage is nearly double the ror advantage? If so, could you perhaps provide some computations, because the adversaries I come up with don't show this gap in advantage. – pxdnr Jun 7 '15 at 5:13
• I believe I fixed that problem. $\:$ Now, in the lor case, the adversary can learn which one $\hspace{1.21 in}$ it was when the ciphertext's initial bit is a $1$. $\;\;\;\;$ – user991 Jun 7 '15 at 7:25
• Your answer is correct, but I went with the other one because it gave more explanation. – pxdnr Jun 8 '15 at 1:56