Join Log in
Score:2
X. G. avatar Crypto

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

in flag
X. G.

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.

107
0 + 0
Marc Ilunga avatar
tr flag
Marc Ilunga
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?
0
Reply
X. G. avatar
in flag
X. G.
@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.
0
Reply
Marc Ilunga avatar
tr flag
Marc Ilunga
Ï 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.
0
Reply
Marc Ilunga avatar
tr flag
Marc Ilunga
The original question on shared randomness is still intersting tho: )
0
Reply
X. G. avatar
in flag
X. G.
@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$.
0
Reply
Marc Ilunga avatar
tr flag
Marc Ilunga
I would suggest to explicitly add this version of CPA in the question explicitly. It’s worth noting that this is not the standard CPA notion and seems like too strong of a requirement. The CTR example has a proof for standard CPA but doesn’t satisfy this non standard CPA notion
0
Reply
Score:1
Mark avatar Crypto
ng flag
Mark

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.

0 + 0
X. G. avatar
in flag
X. G.
Thank you very much for the detailed example!
0
Reply
us flag
Mikero
or simply $F=G$
1
Reply
Mark avatar
ng flag
Mark
@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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.