# Pseudorandom function of different keys 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.

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.

• 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)$. – user153882 Nov 3 '16 at 15:15