211 reputation
17
bio website henning.makholm.net
location Copenhagen, Denmark
age 40
visits member for 2 years, 5 months
seen Apr 8 at 16:33

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
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
21
comment Trying to find a different DES encryption system explanation
@Borja: you write "I know this has a mathematical explanation" -- where do you know this from? Whoever told you this, do you have reason to trust them?
Nov
21
comment Trying to find a different DES encryption system explanation
No information about where the S-boxes came from was available when DES was first specified; this generated significant amounts of paranoia. It was later found that the exact choices increased the resistance of DES to differential cryptanalysis, but AFAIK the precise way they were selected is still classified (that is, if the details are even written down anywhere). There may be no more to it, mathematically, than "use this magic table lookup".
Nov
19
comment How does a chosen ciphertext attack work, with a simple example?
Depends on what you consider communication. If the attacker simply steals a tamper-proof decrypting machine that will self-destruct after decrypting $n$ messages without ever revealing the key explicitly, does that count as "communication"? If you can think of any way the attacker can get to know the decrypted messages without "unprotected communication" happening, then no. Otherwise maybe.
Nov
19
comment How does a chosen ciphertext attack work, with a simple example?
The important fact is that the attacker somehow learns what his test message decrypts to. It doesn't need to be anything as "obviously risky" as calling on an unsecured line -- in a more modern setting, we could be thinking of a protocol where an encrypted message contains a nonce that the recipient will later echo back without encryption, or of a setting where the encrypted message contains data that the recipient is supposed to publish on behalf of the sender.