# Does shared randomness between two cryptographic primitives complicate the hybrid argument for computational indistinguishability?

Let $$(Enc, Dec)$$ be an IND-CPA secure encryption scheme, where $$Enc: \mathcal{K} \times \mathcal{M}_1 \rightarrow \mathcal{C}_1$$, and $$F: \mathcal{K} \times \mathcal{M}_2 \rightarrow \mathcal{C}_2$$ be a pseudorandom function.

Consider a simple example where we may want to prove the distribution $$(Enc_k(m_1), F_k(m_2))$$ (whose randomness comes from the shared key $$k \leftarrow \mathcal{K}$$) is computationally indistinguishable from the uniform distribution on $$\mathcal{C}_1 \times \mathcal{C}_2$$. Clearly, we can show that the distribution of $$Enc_k(m_1)$$ is computationally indistinguishable from the uniform distribution on $$\mathcal{C}_1$$ via a reduction to IND-CPA security. By replacing $$Enc_k(m_1)$$ with a random element $$r_1 \leftarrow \mathcal{C}_1$$, we can obtain an intermediate hybrid $$(r_1, F_k(m_2))$$. My question is that:

Can we then apply the pseudorandomness of $$F$$ to replace $$F_k(m_2)$$ with another random element $$r_2 \leftarrow \mathcal{C}_2$$, in order to prove the above computational indistinguishability?

From my perspective, the two random variables $$Enc_k(m_1)$$ and $$F_k(m_2)$$ are not independent since they share the same randomness $$k$$. This is reminiscent of the reason why we should consider the joint distribution of someone's view-output tuple rather than its view in secure computation. So, I suppose that the shared randomness here does prevent a simple hybrid argument from going through. Is this conclusion right? Many thanks.

• Can we always have the guarantee that $\mathcal C_1 \times \mathcal C_2$ is indistinguishable from random? Wouldn't it be easy for an attacker to distinguish $\mathcal C_1$ if the encryption is some counter-based mode? Mar 21, 2022 at 16:54
• @MarcIlunga, I think that IND-CPA security ensures that the output of $Enc$ should be pseudorandom as long as key space $\mathcal{K}$ has enough entropy, say, $\kappa$ bits. Mar 22, 2022 at 1:56
• Ï am not sure CPA can always give that guarantee. A pathological example: modify a CPA scheme to append a $0$. i.e. $ctxt = c|0$ . This remains CPA secure but is distinguishable from random. A better example would be the CTR mode of operation with nonces. so $ctxt = n | c$. I think also distinguishable from random if $n$ is a counter and not randomized. Mar 22, 2022 at 7:49
• The original question on shared randomness is still intersting tho: ) Mar 22, 2022 at 7:50
• @MarcIlunga, thank you for your comment. A formal definition of IND-CPA is indeed missing in my question. Here, I informally use the term "IND-CPA" to refer to the property that an encryption scheme can result in pseudorandom ciphertexts in $\mathcal{C}_1$. Mar 22, 2022 at 11:10

Yes, you are right.

A formal definition of IND-CPA is indeed missing in my question. Here, I informally use the term "IND-CPA" to refer to the property that an encryption scheme can result in pseudorandom ciphertexts in $$\mathcal{C}_1$$

This is of course a stronger assumption than being IND-CPA, but it is boring to point this out. Really, this assumption can be written as

$$\mathsf{Enc}_k$$ is a PRF family.

It is perhaps more straightforward to think about this in terms of PRFs, so I will quickly show that if $$F_k, G_k$$ are (individually) PRFs, then $$(F_k, G_k)$$ need not be, e.g. sharing PRF keys can break security. This is because of the dependence between the left and right components, as you have guessed.

Let $$F_k$$ be a PRF, and let $$G_k = F_k^{\circ 2}$$, i.e. $$G_k(x) = F_k(F_k(x))$$. It is simple to see that $$G_k$$ is (individually) a PRF --- any distinguisher for it implies a distinguisher for $$F_k$$, as you can efficiently emulate query access to $$G_k$$ given query access to $$F_k$$.

Now, $$(F_k, F_k^{\circ 2})$$ is not a PRF. This is because, given an oracle $$\mathcal{O}(\cdot)$$ that is either real or random, you can.

1. $$(y_1, y_2)\gets \mathcal{O}(x)$$,
2. $$(z_1, z_2) \gets \mathcal{O}(y_1)$$,
3. guess REAL if $$y_2 = z_1$$, and RANDOM otherwise.

IF $$\mathcal{O}(x) = (F_k(x), F_k^{\circ 2}(x))$$ is your PRF, then $$y_2 = F_k^{\circ 2}(x)$$, and $$z_1 = F_k(y_1)= F_k(F_k(x)) = F_k^{\circ 2}(x)$$ collide. In the random game, the probability of any two values colliding is quite small, so this immediately implies a rather good distinguisher.

There are more immediate problems though. One way to build $$\mathsf{Enc}_k(m)$$ is by XORing $$m$$ with a PRF, for example $$\mathsf{Enc}_k(m) = (r, F_k(r)\oplus m)$$. This is simply randomized counter mode (where messages are a single block). In this setting, the joint construction is $$(m_1,m_2)\mapsto (r, F_k(r)\oplus m_1, F_k(m_2))$$. Again, by querying on $$(m_1, m_2)$$, and then querying $$(m_3, r)$$, one can obtain an efficient distinguisher. This is to say a natural construction (where $$\mathsf{Enc}$$ is randomized counter mode) is not secure in your setting as well.

• Thank you very much for the detailed example! Mar 24, 2022 at 10:48
• or simply $F=G$ Mar 24, 2022 at 22:43
• @Mikero that is actually a much more interesting example, as it shows that $F, G$ being PRFs individually is not enough to show that $(F, G)$ is even a "weak PRF", meaning an adversary can distinguish $(F_k(x), G_k(x))$ from random even if $x$ is randomly chosen, rather than adversarial chosen. I was unable to show this using my examples in my answer. Mar 24, 2022 at 23:10