Proof that IND$-CPA implies IND-CPA?

Question

I've read a few papers recently that used a notion of security called "indistinguishability from random bits/strings" under chosen plaintext attack, also called IND\$-CPA. See e.g. http://pdf.aminer.org/000/217/279/nonce_based_symmetric_encryption.pdf. The authenticated encryption mode "OCB" is also proved using this notion. This is different from notions I am more familiar with, such as Left-Or-Right (LOR) or Real-Or-Random (ROR), which are generally called IND-CPA. These papers all claim that "it is easy to verify that the IND\$-notion of security implies the IND-notion, and by a tight reduction", but neglect to provide the proof for this implication. So can anyone provide this proof?

Here is the classic LOR definition for IND-CPA, from http://www.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf, also explained more fully here: http://cseweb.ucsd.edu/~mihir/cse107/w-se.pdf.

A symmetric encryption scheme $\mathcal{S}$ is a set of three algorithms, $\{\mathcal{K}, \mathcal{E}, \mathcal{D}\}$. The randomized key generation algorithm, $\mathcal{K}$, selects a key K uniformly at random from the Key-Space, which is defined by the security parameter $k$ -- Key-Space = $\{0, 1\}^k$. The encryption algorithm $\mathcal{E}$ takes the key K and a plaintext M and outputs either a ciphertext C or the symbol $\bot$ (to indicate the plaintext was not in the domain of $\mathcal{S}$). At this stage I am not restricting what sort of algorithm $\mathcal{E}$ has to be -- it can be randomized (like CBC mode), or stateful (like CTR mode), or deterministic and stateless (like ECB mode, although it's easy to show that any encryption algorithm that is not stateful or randomized is trivially insecure). The decryption algorithm $\mathcal{D}$ is deterministic and stateless, and takes the key K and a ciphertext C and outputs either a plaintext M or the symbol $\bot$ (to indicate the submitted ciphertext was not in the domain of $\mathcal{S}$). $\mathcal{D}$ is the inverse of $\mathcal{E}$, such that $D_K(E_K(M)) = M$ for all M in the domain of $\mathcal{S}$ and all keys in the Key-Space.

The IND-CPA Game

This notion of security can be defined in terms of a game between an Adversary $\mathcal{A}$ and a Challenger who is implementing the encryption scheme $\mathcal{S}$. The Challenger grants $\mathcal{A}$ access to a Left-Or-Right encryption 'oracle' $E_K(\mathcal{LR}(\cdot, \cdot, b))$, which takes queries of the form $(M_0, M_1)$ and returns either $E_K(M_b)$ or the symbol $\bot$ if $|M_0| \neq |M_1|$ (i.e. if the messages were not of the same length).

Here are the steps of the game:

1. The Challenger picks a security parameter $k$ and uses $\mathcal{K}$ to choose a key K from the Key-Space defined by that security parameter. The Challenger then sends the parameter $k$ to $\mathcal{A}$. If the security parameter is fixed and public then the Challenger does not need to select it or send it to $\mathcal{A}$.

2. The Challenger selects a value $b$ uniformly at random from the set $\{0, 1\}$ (by, for example, flipping a fair coin). This bit defines how the encryption oracle will behave for the rest of the game -- either it will be a 'Left Oracle' (if $b = 0$), or a 'Right Oracle' (if $b = 1$). The Challenger grants $\mathcal{A}$ access to the now defined oracle, but does not tell $\mathcal{A}$ the value of $b$ (whether the oracle is a Left Oracle or a Right Oracle is a secret).

3. $\mathcal{A}$ submits queries to the oracle of the form $(M_0, M_1)$, and receives replies that are either the encryption of the left message, $M_0$, or the right message, $M_1$, depending on $b$. $\mathcal{A}$ is allowed to make up to $q_e$ such queries, with a total message-length at most $\mu$ bits, and can adaptively select queries depending on earlier answers (this is an 'adaptive' chosen plaintext attack).

4. After making all the queries it wants to and/or can, $\mathcal{A}$ outputs a bit, $b'$, which is its best guess as to the value of $b$. If $b' = b$ then $\mathcal{A}$ wins the game, but if $b' \neq b$ then $\mathcal{A}$ loses.

The Advantage of any Adversary $\mathcal{A}$ playing this game is defined as the probability that $\mathcal{A}$ wins minus the probability that $\mathcal{A}$ loses.

$Adv^{lor-cpa}_{\mathcal{S}, \mathcal{A}} = P(\mathcal{A} \textit{ wins}) - P(\mathcal{A} \textit{ loses})$

Typically in security proofs, we attempt to prove an upper bound for the advantage of any adversary making at most $q_e$ queries, totaling at most $\mu$ bits, with a maximum running time of $t$ (the running time of the algorithm that $\mathcal{A}$ uses to devise queries and then decide what guess to make), and for a given security parameter $k$. If the proven upper bound is 'small' for 'reasonable' values for $k, t, q_e$ and $\mu$ then the encryption scheme $\mathcal{S}$ is considered 'provably secure'.

The IND\$-CPA Game

This notion of security is similarly defined in terms of a game between $\mathcal{A}$ and the Challenger implementing $\mathcal{S}$. There is one key difference:

The Challenger again randomly picks $b$, but this time instead of defining either a Left Oracle or a Right Oracle, this bit $b$ determines whether the Challenger will implement a 'Real' Oracle or a 'Fake' Oracle. The Real Oracle takes queries of the form $M$ and returns $E_K(M)$ (i.e. the queries do not come in pairs of equal length messages). The Fake Oracle takes queries of the form $M$ and returns a string selected independently and uniformly at random from the set $\{0, 1\}^{|M|+s}$, where $|M|$ is the length of the query $M$ and $s$ is the 'stretch' of $\mathcal{E}$ (the amount the encryption algorithm expands the ciphertext associated with $M$, e.g. how CBC pads messages that are not divisible by the block-size of the cipher).

The Adversary $\mathcal{A}$ is thus not trying to distinguish between the encryption of $M_0$ and $M_1$, but rather it is trying to distinguish the encryption of $M$ from a random string of the same length. As before, the Advantage of an Adversary is defined as the probability that it correctly guesses the bit $b$ minus the probability that it makes a wrong guess. And as before, if the max Advantage over all ($k, t, q_e, \mu$)-limited Adversaries is sufficiently small for reasonable values for those parameters, then the encryption scheme is 'provably secure'.

Answer 1

Here is the proof I came up with. Please let me know if you see any problems with it...

Statement to prove: If an encryption scheme is secure in the IND\$-CPA sense, then it is secure in the IND-CPA sense as well. i.e. IND\$-CPA $\Rightarrow$ IND-CPA

The contrapositive is easier to prove: $\neg$IND-CPA $\Rightarrow$ $\neg$IND\$-CPA. This statement is a trivial consequence of the following Lemma:

Lemma 1. Any efficient (LOR) IND-CPA adversary with an advantage of $\epsilon$ can be translated into an IND\$-CPA adversary with polynomially similar efficiency and an advantage of $\frac{\epsilon}{2}$.

Thus, if the IND-CPA advantage is large (meaning the encryption scheme is insecure in that sense) then the IND\$-CPA advantage will also be large (meaning it will be insecure in that sense too).

To prove Lemma 1 I will use a reduction argument. Let $\mathcal{A}_{\mathcal{LOR}}$ be the LOR adversary with advantage $\epsilon$, and let $\mathcal{A}_\$$ be the IND\$-CPA adversary. $\mathcal{A}_\$$ can function as a 'wrapper', posing as a LOR-Challenger to $\mathcal{A}_{\mathcal{LOR}}$, and shuttling the plaintext queries and answers back and forth between the \$-Challenger and $\mathcal{A}_{\mathcal{LOR}}$ in the following manner:

1. $\mathcal{A}_\$$ flips a coin, $b'$, and uses the value for the rest of the game;
2. $\mathcal{A}_{\mathcal{LOR}}$ transmits requests of the form $(x_0, x_1)$ to $\mathcal{A}_\$$, who picks $x_{b'}$ and transmits that to the \$-Challenger, and then passes the response from the \$-Challenger back to $\mathcal{A}_{\mathcal{LOR}}$;
3. After $q_e$ queries, $\mathcal{A}_{\mathcal{LOR}}$ makes its guess, $b^*$, as to the value of $b'$ and sends that guess to $\mathcal{A}_\$$;
4. $\mathcal{A}_\$$ checks whether $b' = b^*$. If it does, then $\mathcal{A}_\$$ guesses that $b = 0$ (i.e. that the \$-Challenger oracle is a Real Oracle), and if $b' \neq b^*$ then $\mathcal{A}_\$$ guesses that $b = 1$ (i.e. that the \$-Challenger oracle is a Random String Oracle).

Definition of Advantage: $Adv(\mathcal{A}) = P(\mathcal{A}$ Guesses Correctly$) - P(\mathcal{A}$ Guesses Incorrectly$)$

Let $\mathcal{A}_\$\Rightarrow x$ mean adversary $\mathcal{A}_\$$ guesses that $b = x$.

So, $Adv(\mathcal{A}_\$) = [P(\mathcal{A}_\$\Rightarrow 0|b = 0)P(b = 0) + P(\mathcal{A}_\$\Rightarrow 1 | b = 1)P(b = 1)] - [P(\mathcal{A}_\$\Rightarrow 0 | b = 1)P(b = 1) + P(\mathcal{A}_\$\Rightarrow 1 | b = 0)P(b = 0)]$

Since $\mathcal{A}_\$\Rightarrow 0$ (it guesses that the \$-Challenger is instantiating a Real Oracle) if and only if $b^* = b'$, then:

$Adv(\mathcal{A}_\$) = [P(b^* = b'|b = 0)P(b = 0) + P(b^* = b' | b = 1)P(b = 1)] - [P(b^* \neq b'| b = 1)P(b = 1) + P(b^* \neq b' | b = 0)P(b = 0)]$

The \$-Challenger chooses the value for b uniformly at random from $\{0, 1\}$, so $P(b = 0) = P(b = 1) = \frac{1}{2}$, and as such:

$Adv(\mathcal{A}_\$) = P(b^* = b'|b = 0)\frac{1}{2} + P(b^* = b' | b = 1)\frac{1}{2} - P(b^* \neq b'| b = 1)\frac{1}{2} - P(b^* \neq b' | b = 0)\frac{1}{2}$

At this point I need another Lemma...

Lemma 2. $P(b^* = b'| b = 1) = P(b^* \neq b'| b = 1) = \frac{1}{2}$.

This is because when $b = 1$ then the \$-Challenger is instantiating a Random String Oracle, and as such $\mathcal{A}_{\mathcal{LOR}}$ only ever sees sequences of uniformly random strings in response to its queries, independent of what value $\mathcal{A}_\$$ selected for $b'$. So it can never do better (or worse) than a random guess in terms of correctly guessing $b'$.

This Lemma in hand, the two $b = 1$ terms in the previous advantage equation cancel out, leaving us with,

$Adv(\mathcal{A}_\$) = P(b^* = b'|b = 0)\frac{1}{2} - P(b^* \neq b' | b = 0)\frac{1}{2}$,

$ = \frac{1}{2}[P(b^* = b'|b = 0) - P(b^* \neq b' | b = 0)]$.

When $b = 0$ then the overall game is essentially a LOR game, and when $\mathcal{A}_{\mathcal{LOR}}$ is actually playing a LOR game, its advantage is,

$Adv(\mathcal{A}_{\mathcal{LOR}}) = P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Correctly$) - P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Incorrectly$)$,

Or to explicitly include the condition that it is playing a LOR game,

$Adv(\mathcal{A}_{\mathcal{LOR}}) = P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Correctly | Game = LOR$) - P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Incorrectly | Game = LOR$)$.

For $\mathcal{A}_{\mathcal{LOR}}$ to guess correctly, that means $b^* = b'$, and for it to guess incorrectly then $b^* \neq b'$. So:

$P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Correctly | Game = LOR$) = P(b^* = b'|b = 0)$

$P(\mathcal{A}_{\mathcal{LOR}}$ Guesses Incorrectly | Game = LOR$) = P(b^* \neq b' | b = 0)$.

$\therefore$ $Adv(\mathcal{A}_\$) = \frac{1}{2}[Adv(\mathcal{A}_{\mathcal{LOR}})]$

In terms of the 'efficiency' of $\mathcal{A}_\$$ (its running time), this will essentially be the computational cost of $\mathcal{A}_{\mathcal{LOR}}$ together with the 'wrapper' overhead, which should be trivially small. The only 'per query' operations that $\mathcal{A}_\$$ has to perform are: a) receive the $(x_0, x_1)$ queries from $\mathcal{A}_{\mathcal{LOR}}$, b) decide whether $x_{b'}$ equals $x_0$ or $x_1$, c) send that to the \$-Challenger, and d) send the response back through to $\mathcal{A}_{\mathcal{LOR}}$. The only 'per game' operations $\mathcal{A}_\$$ has to perform are to randomly choose a value for $b'$ at the beginning, and then at the end decide whether $b^* = b'$ or $b^* \neq b'$ and output its guess as to the value of $b$ accordingly. So if the operational cost of $\mathcal{A}$ is $C_{\mathcal{A}}$, then:

$C_{\mathcal{A}_\$} = A(C_{\mathcal{A}_{\mathcal{LOR}}}) + B$, where $A$ and $B$ are small.

Thus is Lemma 1, and thereby the statement IND\$-CPA $\Rightarrow$ IND-CPA, proved. Or so I believe. Thoughts?