Henning Makholm

209 reputation

bio	website	henning.makholm.net
	location	Copenhagen, Denmark
	age	39
visits	member for	1 year, 7 months
	seen	Mar 5 at 13:14
stats	profile views	14

	209 reputation	bio	website	henning.makholm.net	visits	member for	1 year, 7 months
15 badges		location	Copenhagen, Denmark		seen	Mar 5 at 13:14

summary answers questions tags badges favorites bounties reputation activity

23 Actions

suggestions reviews revisions comments badges posts accepts all

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
Nov 1	answered	CPA Secure Chosen plaintext scheme
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	awarded	Supporter
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.