Could someone explain to me how they formulated the equation and how it equals to $0^{n}$ (like what F(x, x) equals to or how they cancel each other out?) on the first box and if its related to the second. I know that PRF output plus itself would make all the bits 0, so $F_K(x) + F_K(x) = 0^{n}$


As kodlu previously said, this text is confusing because it uses the name $F$ for two different things. For clarity, I'll use

  • $P$ (rather than $F$) for a function that we already know (or assume) is an n-bit pseudorandom function. Typically a pseudorandom function "encrypts" a n-bit plaintext block to a n-bit ciphertext block using a k-bit key.
  • $M$ (rather than $F$) for any function that we are trying to prove either definitely is or definitely is not a pseudorandom function. As the attacker, you win if you can find any way to distinguish $M$ from a random oracle -- in other words, you win if you can show that candidate $M$ definitely is not a pseudorandom function.
  • $D$ is a "function of a function" that can be applied to any keyed function $M$. The text leaves unstated a few details that it expects you to fill in, but to be explicit (where + represents xor): $$D(M, K, K', x, y) = \begin{cases} 1, & \mbox{if } M_{K, K'}(x,x) + M_{K, K'}(x,y) + M_{K, K'}(y,x) + M_{K, K'}(y,y) = 0^n \\ 0, & \mbox{otherwise} \end{cases}$$

We separately apply $D$ to two different things: first we set $M$ to a true random oracle $R$ (or a pseudorandom function $P$, which should give the same results) and calculate D, and then we set $M$ to the function $G$ given in the problem and calculate D. (When D calls the random oracle with the two keys of length k and the two inputs of length n, we concatenate the keys and we concatenate the inputs to call a random oracle with one key of length 2k and one input of length 2n and we only use the first n bits of the output of the oracle).

what happens if the key is the same as message such as $F_x(x)$.

In this particular problem and solution, we set the message independently of the key, so they are almost certainly not the same. Even if they were the same, nothing special happens. A few (old and deprecated) password hash functions set the key the same as the message: "HMACs that have the same key and message" , "HMAC SHA1 using the same value for key and message", etc.

| improve this answer | |

The quantity in the second red box is clearly zero since it is a sum of an even number of $F_K(x), F_K(y), F_{K'}(x), F_{K'}(y).$

What may be confusing you is the fact that the quantity in the first red box, is a distinguisher definition for ANY keyed function but the function name $F$ was also used there.

The motivation for the definition of the distinguisher $G$ is the observation that $G$ as defined can be turned into a multilinear function by a "parallelogram" addition, as in the definition.

| improve this answer | |
  • $\begingroup$ Could you elaborate how the first red box for ANY keyed function works. Im a little confused how the the key is used in the PRF and what happens if the key is the same as message such $F_x(x)$. $\endgroup$ – user153882 Nov 3 '16 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.