Bit Flipping in State Separable Proofs

When working with State Separable Proofs, it’s often easier to frame every game as distinguishing between the “real world” and the “ideal world”. This allows keeping the framing consistent throughout the composition of different games / packages.

For example, the security of a PRF is defined in this real ideal paradigm, by distinguishing between the case of actually calling the PRF with a key, and the case of a genuine random function.

If you then use this PRF to make an encryption scheme, it’s useful to also define security in terms of distinguishing between encrypting messages, and encrypting random ciphertexts, which helps the proofs go more smoothly when trying to reduce the security of the larger encryption scheme to the security of the smaller PRF.

Contrast this with the other common notion of encryption security, in which the adversary sends two messages each round, and has to figure out whether the challenger is consistently encrypting the first or the second message.

This begs the question: can you reduce the real-or-random notion of encryption to the left-or-right notion of encryption? Yes.

Background

For left-or-right, we have the following pair of games:

$$\boxed{\begin{array}{rl}& {\text{LR}}_b\\ & \\ & k\stackrel{R}{\leftarrow }K\\ & \text{encrypted}\leftarrow \varnothing \\ & \\ & \underline{LR.Choose(m_0,m_1):}\\ & c\leftarrow E(k,m_b)\\ & \text{encrypted}\leftarrow \text{encrypted}\cup \{c\}\\ & \text{return }c\\ & \\ & \underline{LR.Enc(m):}\\ & \text{return }E(k,m)\\ & \\ & \underline{LR.Dec(c):}\\ & \text{require }c\notin \text{encrypted}\\ & \text{return }D(k,c)\end{array}}$$

and for real-or-random, we have:

$$\boxed{\begin{array}{rl}& {\text{RR}}_b\\ & \\ & k\stackrel{R}{\leftarrow }K\\ & \text{encrypted}\leftarrow \varnothing \\ & \\ & \underline{RR.Choose(m_0):}\\ & m_1\stackrel{R}{\leftarrow }\{0,1{\}}^{|m_0|}\\ & c\leftarrow E(k,m_b)\\ & \text{encrypted}\leftarrow \text{encrypted}\cup \{c\}\\ & \text{return }c\\ & \\ & \underline{RR.Enc(m):}\\ & \text{return }E(k,m)\\ & \\ & \underline{RR.Dec(c):}\\ & \text{require }c\notin \text{encrypted}\\ & \text{return }D(k,c)\end{array}}$$

Note:

For full generality, you’d have a function which lets you sample a random message of the same length as another message, which lets you accomodate cases where the messages aren’t just simple bit-strings.

Note that because the oracles are the same in both cases, I’ll omit them in the reductions for simplicity.

$\text{RR}\stackrel{ϵ}{\to }\text{LR}$

In other words, for every adversary $\mathcal{A}$ against ${\text{RR}}_b$ with advantage $ϵ$, there exists an adversary $\mathcal{B}$ against ${\text{LR}}_b$ with advantage $ϵ$ as well.

To show this, we provide a shim $S$ which provides the interface for ${\text{RR}}_b$ over ${\text{LR}}_b$:

$$\boxed{\begin{array}{rl}& S\\ & \\ & \underline{RR.Choose(m_0):}\\ & m_1\stackrel{R}{\leftarrow }\{0,1{\}}^{|m_0|}\\ & c\leftarrow LR.Choose(m_0,m_1)\\ & \text{return }c\end{array}}$$

Then, we clearly have $S\circ {\text{LR}}_b={\text{RR}}_b$, in the sense of providing identical distributions. Thus $ϵ(\mathcal{A}\circ {\text{RR}}_b)=ϵ(\mathcal{A}\circ S\circ {\text{LR}}_b)=ϵ((\mathcal{A}\circ S)\circ {\text{LR}}_b)$, and $\mathcal{B}:=\mathcal{A}\circ S$ is the adversary breaking ${\text{LR}}_b$.

The Other Direction

In the other direction, the idea is more subtle. We can’t directly translate an oracle encrypting either our message or a random message into one encrypting one of two messages.

The idea of the reduction in standard game notation is to choose the random bit for the message ourselves, inside of the shim. Then, if the adversary is able to accurately detect the bit, that tells us that we’re in the case where we’re not seeing random ciphertexts from the oracle.

There’s actually a general lesson to be learned here.

Let’s say you have two bit-indexed games, $G_{b_G}$ and $H_{b_H}$.

If we look at:

$$H_{b_H}\circ G_{b_G}$$

Then we can replace $H_{b_H}$ with a concrete game $H$, where the bit is flipped on initialization. Ditto with $G$.

From a technical point of view, $H$ includes a special function to read this bit, called $\text{get-b}$. Then, given an adversary $\mathcal{A}$ for $H_{b_H}$, whose interface doesn’t include $\text{get-b}$, of course, we have an adversary $\hat{\mathcal{B}}$ which runs $\mathcal{A}$, and then checks if that bit is equal to $\text{get-b()}$, returning $1$ if that’s the case.

The question is about the advantage:

$$ϵ(\hat{\mathcal{B}}\circ (1(\text{get-b})\otimes \mathcal{A})\circ H\circ G_{b_G})$$

By definition, we have:

$$ϵ:=|P[\hat{\mathcal{B}}\to 1|b_G=0]-P[\hat{\mathcal{B}}\to 1|b_G=1]|$$

Letting $\hat{\mathcal{B}}(x_0,x_1):=P[\hat{\mathcal{B}}\to 1|b_H=x_0,b_G=x_1]$, we can expand this to get:

$$ϵ=\frac{1}{2}|\hat{\mathcal{B}}(0,0)+\hat{\mathcal{B}}(1,0)-(\mathcal{B}(0,1)+\mathcal{B}(1,1))|$$

Letting $\mathcal{A}(x_0,x_1)$ denote a similar quantity, we have:

$$ϵ=\frac{1}{2}|(1-\mathcal{A}(0,0))+\mathcal{A}(1,0)-((1-\mathcal{A}(0,1))+\mathcal{A}(1,1))|$$

which we can reduce to:

$$ϵ=\frac{1}{2}|\mathcal{A}(1,0)-\mathcal{A}(0,0)+\mathcal{A}(0,1)-\mathcal{A}(1,1)|$$

Using the reverse triangle inequality, we can write this as:

$$ϵ\ge \frac{1}{2}||\mathcal{A}(0,0)-\mathcal{A}(1,0)|-|\mathcal{A}(0,1)-\mathcal{A}(1,1)||$$

Or, in terms of advantages, we have:

$$ϵ\ge \frac{1}{2}|ϵ(\mathcal{A}\circ H_b\circ G_0)-ϵ(\mathcal{A}\circ H_b\circ G_1)|$$

Which is actually a useful result. We can use an adversary $\mathcal{A}$ which can break the inner part, and use that to get an adversary breaking $G_b$.

A similar reasoning shows that:

$$ϵ(\hat{\mathcal{B}}\circ \mathcal{A}\circ H_{b_H}\circ G)\ge \frac{1}{2}|ϵ(\mathcal{A}\circ H_0\circ G_b)-ϵ(\mathcal{A}\circ H_1\circ G_b)|$$

Let’s summarize the main result. Given an adversary $\mathcal{A}$ playing against $H_{b_H}\circ G_{b_G}$, there exists an adversary $\mathcal{B}$ such that:

$$ϵ(\mathcal{B}\circ G_b)\ge \frac{1}{2}|ϵ(\mathcal{A}\circ H_b\circ G_0)-ϵ(\mathcal{A}\circ H_b\circ G_1)|$$

$\text{LR}\stackrel{\frac{1}{2}ϵ}{\to }\text{RR}$

If we let $G_b:={\text{RR}}_b$, then we can create a shim $H_b$ such that $H_b\circ G_0={\text{LL}}_b$, as follows:

$$\boxed{\begin{array}{rl}& H{}_b\\ & \\ & \underline{LR.Choose(m_0,m_1):}\\ & c\leftarrow RR.Choose(m_b)\\ & \text{return }c\end{array}}$$

It should be clear that $H_b\circ {\text{RR}}_0$ provides an equivalent game as ${\text{LL}}_b$. Note also that ${\text{LL}}_0\circ {\text{RR}}_1={\text{LL}}_1\circ {\text{RR}}_1$, since the bit has no impact, since the ciphertext is always random.

We can now apply the result we derived in the previous section. Given an adversary $\mathcal{A}$ playing against ${\text{LR}}_b$, there exists an adversary $\mathcal{B}$ playing against $\text{RR}$ such that:

$$ϵ(\mathcal{B}\circ {\text{RR}}_b)\ge \frac{1}{2}|ϵ(\mathcal{A}\circ H_b\circ {\text{RR}}_0)-ϵ(\mathcal{A}\circ H_b\circ {\text{RR}}_1)|=\frac{1}{2}|ϵ(\mathcal{A}\circ {\text{LL}}_b)-0|$$

The last part is $0$, since the two games are equivalent.

And that implies the reduction.

$\square$