Two (equivalent) definitions of computational indistinguishability, two (isomorphic) ways of doing hybrids

It wasn’t until recently did I realise there are two isomorphic ways (different styles) of writing hybrid proofs. They actually correspond to the two equivalent definitions of computational indistinguishability — one based on guessing and the other based on distinguishing. Actually, I’ve been writing both kinds of proofs subconciously.

The hero image (as well as the tile images) is taken from the lecture notes by Rafael Pass and abhi shelat.

Updated on 22 June. I suddenly recall that the second style is the game-based proof introduced by Victor Shoup (I also learnt that from the Boneh-Shoup book version 0.3), and that the first style is the usual ‘hybrid argument’. (Hmmm, I might have stretched the term ‘hybrid argument’ in my daily discourse.) I also recalled the intent of writing this entry — it is this Zhihu question (in Chinese), in which the OP said that ‘proving security means proving the indistinguishability of games’, which confused me a bit because security is often defined as either indistinguishability of oracles/distributions, or the winning probability of some game being close to 0 or 1/2. The full game-based proof consists of two parts: (1) the winning probabilities in the games are negligibly close; (2) one game has the ‘ideal’ winning probability.

Consider the simplest IND-CPA security for public-key encryption scheme $(G e n, E n c, D e c),$ there are two equivalent ways of defining it. The first is indistinguishability-based. Define two call-once oracles $O_{p k, b} (m_{0}, m_{1}) \to E n c (p k, m_{b}),$ for all efficient adversary $A,$ the function $Pr [A^{O_{0}} (p k \leftarrow $ G e n) \to 1] - Pr [A^{O_{1}} (p k \leftarrow $ G e n) \to 1]$ is negligible. The other is guessing game-based. Define the game as:

Sample a public key $p k \leftarrow $ G e n .$
Launch the adversary $A (p k) .$
Wait for two messages $m_{0}, m_{1}$ from the adversary.
Sample $b \leftarrow $ {0, 1}$ and reply $E n c (p k, m_{b})$ to $A .$
$A$ outputs a bit $b^{'}$ and it wins if $b = b^{'} .$

The security stipulates that for any efficient adversary $A,$ the function $Pr [A wins] - \frac{1}{2}$ is negligible.

Now suppose $(G e n, E n c, D e c)$ is an IND-CPA secure public-key encryption scheme. One can make the encryption more efficient by mixing the public-key encryption and a pseudorandom generator $G .$ The new scheme uses the same key generator. For encryption, a random seed is generated and encrypted, and the message is XORed with the PRG image of the seed. For decryption, the random seed is recovered using the original decryption algorithm, and the message is recovered by doing the XOR again. The benefit is that the scheme handles a much longer message using the same number of public-key operations. To prove IND-CPA security assuming IND-CPA security of the underlying scheme and the PRG security, one uses a hybrid argument, in two different flavours. The two different flavours correspond exactly to the two equivalent ways of defining IND-CPA security.

In the indistinguishability-based IND-CPA, the proof proeeds via 4 hybrid oracles:

The ‘left oracle’, which returns $(E n c (p k, s), G (s) \oplus m_{0}) .$
The oracle now returns $(E n c (p k, 0), G (s) \oplus m_{0}) .$
The oracle now returns $(E n c (p k, 0), t \oplus m_{0}) .$
The oracle now returns $(E n c (p k, 0), t \oplus m_{1}) .$
The oracle now returns $(E n c (p k, 0), G (s) \oplus m_{1}) .$
The ‘right oracle’, which returns $(E n c (p k, s), G (s) \oplus m_{1}) .$

The neighbouring indistinguishability follows by the underlying IND-CPA security, the PRG security, information-theoretic identity, the PRG security, and the underlying IND-CPA security, respectively. The reduction will interface with the adversary by playing the role of the challenger, and use the output bit $b^{'}$ of $A$ as its output. The reduction implies the probabilities of $A$ outputting 1 are negligibly close.

In the guessing game-based IND-CPA, the proof proceeds via 2 hybrid games:

The real game, which replies $(E n c (p k, s), G (s) \oplus m_{b}) .$
The game now replies $(E n c (p k, 0), G (s) \oplus m_{b}) .$
The game now replies $(E n c (p k, 0), t \oplus m_{b}) .$

The reduction is again interfacing with the adversary by playing the role of the challenger, but it now uses the bit ‘whether $A$ wins the game’ as its output. The reduction implies the probabilities of $A$ winning the neighbouring games are negligibly close. In the last hybrid game, $A$ wins the game with probability exactly $\frac{1}{2}$ by an information-theoretic argument. Combined with the previous reductions, the conclusion is thus the probability that $A$ wins the real game is negligibly close to $\frac{1}{2} .$

I believe I have been implicitly writing the proofs in the second style when I was doing the rudimentary cryptography course, but the two styles are really isomorphic, illustrated as below:

The oracle hybriding moves among oracles and concludes security by walking to the right oracle from the left oracle. The game hybriding moves among games and concludes security by arriving in a game where the security is information-theoretic. It’s always possible to translate a game hybrid proof into an oracle hybrid one, provided that the game is distinguishing two oracles, by ‘unfolding the chain’.

Note that this phenomenon might not be so obvious if you nest hybrids. For example, consider the multi-challenge IND-CPA security (it’s reducible to the single-challenge IND-CPA security for public-key encryption schemes, just to demonstrate), the chain of hybrid oracles will be the following:

Left oracle.
Left oracle, first response has fake seed.
Left oracle, first response has fake seed and truly random pad.
Left oracle, first response has fake seed and truly random pad and is for the right message.
Left oracle, first response has fake seed and is for the right message.
Left oracle, first response is for the right message.
Left oracle, first response is for the right message, second response has fake seed.
… (replace each response by going through the left/malformed/right stages)
Right oracle.

It’s possible to prove a lemma that allows you to replace one challenge, which means the hybrids are ‘folded’ in the following way:

In the illustration above, each ‘red hill’ represents a change from using $m_{0}^{(k)}$ to $m_{1}^{(k)}$ in response to the $k$ ^th challenge. Now, there’s another way to do this (but this is not general) as follows:

Left oracle.
Left oracle, first response has fake seed.
Left oracle, first response has fake seed and truly random pad.
Left oracle, first response has fake seed and truly random pad, second response has fake seed.
… (replace each response to the malformed version)
Left oracle, all responses have fake seed and truly random pad.
Right oracle, all responses have fake seed and truly random pad.
… (replace the malformed responses to normal responses)
Right oracle.

By going in this way, you can either use hybrid oracles or hybrid games, where the games are the following:

Distinguish left/right oracles.
Distinguish left/right oracles, but first response has fake seed.
Distinguish left/right oracles, but first response has fake seed and truly random pad.
Distinguish left/right oracles, but first response has fake seed and truly random pad, and second response has fake seed.
… (replace each response to the malformed version)
Distinguish left/right oracles, but all responses have fake seed and truly random pad.

In the last hybrid game, the two oracles are identical, so the probability of $A$ winning it is exactly $\frac{1}{2},$ and by hybrid argument, the adversary wins the real game with probability negligibly close to $\frac{1}{2} .$ Doing hybrids in this order, we recover the full analogy in the first illustration, just with a longer chain — it’s a chain with $2 q + 2$ oracles, or equivalently, $q + 1$ games, where

the oracle reductions interleave between IND-CPA and PRG for $q$ times, use information-theoretic once, and then interleave between PRG and IND-CPA for another $q$ times;
and the game reductions interleave between IND-CPA and PRG for $q$ times to arrive in a game where security is unconditional.

Note that this phenomenon usually does not appear in a proof of simulation-based security, because we’re comparing apples and oranges (quoting Rachel Lin), and there might not be this ‘folded chain of oracles as games’. In fact, the IND-CPA simulator can just simulate the two middle oracles (all responses have fake seed and truly random pad), and indistinguishability of the real/simulation oracles can be seen as ‘half of the IND-CPA security’. Indeed, the simulation-based IND-CPA implies the usual IND-CPA by moving from the left oracle to the simulation oracle, then to the right oracle.

P.S. In terms of concrete security loss, the two methods should give you the same loss factor. Also, I wrote some hybrid arguments ‘in a huge probabilistic way’ (meaning as one single reduction algorithm instead of doing polynomially many times of reductions; quoting Rachel Lin), instead of ‘doing it one step at a time’.