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 1


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}}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.