Maeher
Reputation
1,612
Top tag
Next privilege 2,000 Rep.
Access moderator tools
 Mar18 revised Why concatenate the key a second time in HMAC? added 9 characters in body; edited tags Mar17 reviewed Reject Randomness test question from FIPS 140-1 and comparison with 140-2 Mar14 comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1) @fgrieu This is getting way too long for the comments. But you have some basic misunderstanding about the proof technique here. IF the construction from the proof WOULD work against $f$, THEN the proof would lead to the conclusion that F'' is a PRF. But it does not. Mar14 comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1) @fgrieu The reasoning (which while correct is missing a crucial argument about the distribution of sums of uniformly and independently distributed values) simply does not apply to your example. The reasoning goes as follows: To simulate the oracle for a dist. against $F$ we simply follow the construction of $F$, but use the oracle (containing either $f$ or a random function) instead of $f$. Now the following holds: (1) If the oracle is $f$, then we perfectly simulate $F$. (2) If the oracle is a random function then we perfectly simulate a random function. The second part fails for $F''$. Mar14 comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1) @fgrieu Yes, the proof sketch is missing the argument, why it is that the reduction perfectly simulates a random function in the case that it itself is given access to a random function. But my point is that the proof does NOT need " profound change" besides that. The reduction trivially fails for the examples you give, because the distribution of outputs is incorrect for the random case. In particular your distinguisher would always output the same bit when run as a subroutine of the reduction, because the condition you check would hold in both cases. Mar13 comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1) @fgrieu I don't see how the same argument would work for your examples. If we assume an analogous simulation of the oracle for $F'$, it is easy to see that the simulation of the random case simply fails. That is, in both cases (PRF and random function) the simulated oracle exhibits the bias you mention. The hard part in proving such PRF constructions secure is always to argue why the simulation does not fail in the random case. Here, such an argument can be made for the original function, but not for your examples. Mar3 reviewed Approve What RC4 key value will completely invert $S$ after initial permutation? Feb28 reviewed Approve Cryptographic Protocol using NaCl Feb21 revised Prove that two MACs with incremendal PRF application are not secure fixed index of key Feb21 comment Prove that two MACs with incremendal PRF application are not secure Well, to show that they are not secure, you have to present an adversary that is able to forge them. For the first one, think about how, given a message and a tag, you can find another message for which the same tag will verify. For the second one, think about how you might be able to compute a tag for a longer message without knowing the key. Feb20 reviewed Leave Closed Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)? Feb20 reviewed Reopen RSA vs El Gamal digital signature. Which is more secure? Feb20 reviewed Leave Closed Why does a one-time-pad key have to be at least as long as a message? Feb20 reviewed Close Finding if exponent share is present in dlog instance Feb20 reviewed Leave Open Signature based on public key cryptography and forgery Feb20 reviewed Approve What makes LSBit steganography detectable? And what would help in concealing it? Feb17 comment Proving that a function is not a OWF (One-way-function) That information is exactly what your definition is missing. But in general when it comes to crypto we are interested in average-case one-way functions. Which means the probability is taken over the choice of x and therefore it is fine if the function is easy to invert for some inputs, as long as it is hard on average. Feb13 awarded Civic Duty Feb10 comment Signature based on public key cryptography and forgery It depends on what you mean. If the secret key is necessary to find the second document, then it is fine. If you know the secret key, you can already sign anything you want. However, if it is possible to find the second document given only the original message, signature and public key, then the scheme is trivially forgeable. Feb9 comment RSA assumption and cryptography This sounds a lot like homework. But it sounds like you might want to check out random self-reducibility.