Pseudorandom function of different keys

Question

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}$

Answer 1

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.

Answer 2

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.