The example for IND-CPA secure schemes given is generally:
for a random r,
Enc_k(m) =(r|| E_k(r) XOR m) where E is a PRF
But does the role of r and k really matter--i.e. isn't this equally secure?
Enc_k(m) =(r|| E_r(k) XOR m) ?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
13
The pseudo-random $E$ is meant to model a real-world cipher algorithm in some appropriate sense, so it is generally assumed that an attacker can compute $E_k(x)$ for all $k$ and $x$, and can compute $E_k^{-1}(y)$ for all $k$ and $y$.
In CPA, you let the attacker choose $m$. If you then give him $(r \mathop\| E_r(k) \oplus m)$, he can use his knowledge of $m$ to find $E_r(k)$, and since you're explicitly telling him what $r$ is, he can invert $E_r$ to find $k$. Poof, no security at all.
Beware: It turned out (see comments) that I probably misunderstood the question. If $E$ is actually a pseudo-random function, then the that property is supposed to be symmetric in its two arguments (and writing one of them as a subscript is just suggestive of their intended roles), and $E_r(k)$ and $E_k(r)$ are indeed equally secure. On the other hand, then $E$ cannot be instantiated to be an ordinary cipher, because ciphers, even ideal ones, are not actually PRFs.
answered Nov 1, 2012 at 0:11
-
$\begingroup$ This answer might be a bit confusing, because it confuses a PRF with a PRP. A block cipher is a PRP. For a block cipher/PRP, it is generally assumed that one can compute $E_k^{-1}(y)$. But the question asked about a PRF (not a PRP). We normally don't assume, in general, that one can necessarily compute $F_k^{-1}(y)$ when $F$ is a PRF. I agree your answer does get you to the correct final answer, because of this connection (which wasn't spelled out): any PRP is also a PRF, and any PRP is reversible, so at least some PRFs are reversible (even though in general not all PRFs are reversible). $\endgroup$– D.W.Commented Nov 3, 2012 at 21:11
-
$\begingroup$ @DW: I think what is confusing (but perhaps I'm the one it confuses?) is that the question attempted to formulate CPA in terms of a PRF rather than a PRP. I implicitly assumed that this was simply a typo or sloppy terminology in the question. Since CPA (unless I'm misunderstanding) stands for "chosen plaintext attack", that seems to imply that we're dealing with a purported cipher scheme (which is by definition supposed to be reversible given a key), and what role would an actual PRF have in that context? $\endgroup$ Commented Nov 4, 2012 at 2:48
-
$\begingroup$ I think the "IND-CPA" in the question referred to the encryption scheme (Enc_k) not to the PRF (E_k). $\endgroup$– D.W.Commented Nov 4, 2012 at 3:25
-
$\begingroup$ @DW. Hmm, is that a standard concept? I assumed the formula was just plucked from an attempt to formalize the general concept of indistinguishablility under chosen-plaintext attacks. $\endgroup$ Commented Nov 4, 2012 at 3:29
-
$\begingroup$ When you ask "is that a standard concept?", what are you referring to? IND-CPA is a standard concept. A PRF and PRP are a standard concept. The first encryption scheme presented here can be viewed as basically just counter mode. The second one is not standard, precisely because it is insecure. :-) Not sure if that answered your question. $\endgroup$– D.W.Commented Nov 4, 2012 at 4:11
$\begingroup$
$\endgroup$
1
No, it is not equally secure. Consider an instantiation where $E$ is instantiated with AES, and where the message is always 128 bits long. Can you find an attack on this particular version of the scheme?
This smells like homework (I'm guessing?), so to avoid ruining the problem and give you a chance to learn from it, I'm just going to leave it at that. I think you'll find the process of working out the rest of the details to be instructive: for instance, it might help you understand IND-CPA security a bit better and how a scheme can fail to meet this security definition.
-
1$\begingroup$ I second that when $E$ is a block cipher with equal key and input size, $x\mapsto E_k(x)$ is a member of a family of PRF (and PRP) indexed by $k$, and the first scheme in the question meets IND_CPA; while $x\mapsto E_x(k)$ is not a PRF (or PRP), and it is possible to show that the second scheme does not meet IND-CPA, by exhibiting a concrete strategy winning the corresponding game. $\endgroup$– fgrieu ♦Commented Nov 7, 2012 at 7:27