216 reputation
18
bio website henning.makholm.net
location Copenhagen, Denmark
age 41
visits member for 2 years, 10 months
seen 21 hours ago

Aug
12
awarded  Student
Mar
31
awarded  Critic
Mar
27
awarded  Scholar
Mar
27
accepted Is it secure to choose d in a RSA key pair?
Mar
27
asked Is it secure to choose d in a RSA key pair?
Nov
19
awarded  Yearling
Nov
4
comment CPA Secure Chosen plaintext scheme
Since it's becoming clear that I don't actually have a clue here, could someone write a better answer that the OP could accept instead of this?
Nov
4
comment CPA Secure Chosen plaintext scheme
@PaĆ­lo: There may be subtleties here that I have not grasped, but my idea was that the concept of a PRF (not the actual function) would be symmetric, since a distinguisher for $E_x(y)$ could trivially be adapted to distinguish $E_y(x)$ and vice versa. There's a hidden assumption that the two value spaces are the same.
Nov
4
revised CPA Secure Chosen plaintext scheme
fix language
Nov
4
revised CPA Secure Chosen plaintext scheme
Looks like I was wrong
Nov
4
awarded  Commentator
Nov
4
comment CPA Secure Chosen plaintext scheme
On the other hand, I'm not sure I agree with @DW that any PRP is also a PRF, since a PRP has a few collisions (namely none) to look like a random oracle, and we can discover that fact probabilistically by querying only birthday-bound many values of the PRP. Or is that too strict a demand to make of a PRF?
Nov
4
comment CPA Secure Chosen plaintext scheme
... and then the answer to the OP's question is: No it doesn't make a difference whether you write $E_r(k)$ or $E_k(r)$.
Nov
4
comment CPA Secure Chosen plaintext scheme
Oh, I think I see. I assumed that the OP's formula was meant as part of a test for being IND-CPA, sort of like "your cryptosystem has the IND-CPA property if an attacker cannot effectively tell the difference between it and $(k,m)\mapsto(r\mathop\|E_k(r)\oplus m)$" or something like that. But I see now that it makes more sense to interpret is as "here is a way to construct a cryptosystem with the IND-CPA property". Then it does make sense to speak of PRFs rather than PRPs.
Nov
4
comment CPA Secure Chosen plaintext scheme
@DW: What I'm asking is, is "IND-CPA" a standard name for the particular construction $\mathit{Enc}_k(m) = (r\mathop\| E_k(r) \oplus m) $ the OP referred to? If yes, then I've been talking nonsense all the way. But my assumption was that "IND-CPA" here just means the ordinary concept of "indistinguishability under chosen-plaintext attacks", applicable to many different constructions.
Nov
4
comment CPA Secure Chosen plaintext scheme
@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.
Nov
4
comment CPA Secure Chosen plaintext scheme
@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?
Nov
2
awarded  Citizen Patrol
Nov
2
awarded  Editor
Nov
2
revised CPA Secure Chosen plaintext scheme
TeXify