# How to turn adversary against encryption of zeroes into adversary against random bits?

I recently read the article Nonce-Based Symmetric Encryption by Rogaway, where he presents two different notions of indistinguishability, which he calls ind$and ind, respectively. Here's the definitions of these to notions: First, let$A^g$be an algorithm with access to an oracle$g$, and let$\Pi = (\mathcal{E},\mathcal{D})$be an encryption scheme with key space$\mathrm{Key}$. Ind\$ is then defined as follows: $$\mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{}(\cdot)} \Rightarrow 1],$$

where $\$(\cdot)$is a random oracle, returning random bits equal to the block size of$\mathcal{E}$. In other words: ind$ asks an adversary to distinguish between messages encrypted by the real encryption scheme and random bits.

Ind is defined as: $$\mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1].$$

That is, ind asks an adversary, when quarrying the input message $M$ to the oracles, to distinguish between the real encryption of $M$, and the encryption of $0^{|M|}$.

He then claims that

"It is easy to verify that the ind$-notion of security implies the ind-notion, and by a tight reduction". My question: Intuitively, the implication seems easy enough: If$\Pi$is ind\$-secure, then encryption of $0^{|M|}$ will be indistinguishable from random, so we just get the "ind\$-game". However, how would you go about showing the tightness of the reduction? Usually I'm used to doing this by a reduction like so: assume you have an ind-adversary that breaks the ind-security, how can you turn this into an (effective) adversary against the ind\$-security of $\Pi$? But I don't really see how an adversary against ind can be turned into an (effective) adversary against ind\$. - ## 1 Answer It's actually quite simple. Given your adversary$A$against ind you construct an adversary$A'$against ind$ by simply forwarding the queries and answers. (This may seem stupid but please bear with me.)

Consider now, the difference between the advantage of $A$ and $A'$: $$\mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{}(\cdot)} \Rightarrow 1]-(\mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1])$$ $$= \mathrm{Pr}[K \xleftarrow{} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{}(\cdot)} \Rightarrow 1]$$

If this distance were non-negligible, we could build a successful adversary $A''$ against ind$\mathrm{$}$as follows: Whenever$A$queries a message,$A''$queries$0^{|\cdot|}$instead and returns the answer to$A$. It's easy to see that the advantage of$A''\$ is excactly the difference from above. Therefore you get $$\mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}} - \mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$ $$\Rightarrow 2\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$ $$\Rightarrow\mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \frac{1}{2}\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$

-