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.

  • $\begingroup$ 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? $\endgroup$ Mar 21, 2022 at 16:54
  • $\begingroup$ @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. $\endgroup$
    – X. G.
    Mar 22, 2022 at 1:56
  • $\begingroup$ Ï 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. $\endgroup$ Mar 22, 2022 at 7:49
  • $\begingroup$ The original question on shared randomness is still intersting tho: ) $\endgroup$ Mar 22, 2022 at 7:50
  • $\begingroup$ @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$. $\endgroup$
    – X. G.
    Mar 22, 2022 at 11:10

1 Answer 1


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.

  • $\begingroup$ Thank you very much for the detailed example! $\endgroup$
    – X. G.
    Mar 24, 2022 at 10:48
  • 1
    $\begingroup$ or simply $F=G$ $\endgroup$
    – Mikero
    Mar 24, 2022 at 22:43
  • $\begingroup$ @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. $\endgroup$
    – Mark Schultz-Wu
    Mar 24, 2022 at 23:10

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.