Regarding Pseudo Random Functions

Question

I am right now studying Pseudo Random Functions. I have a couple of constructions made of a safe PRF F:{0,1}^l x {0,1}^l -> {0,1}^l. I am unsure of wether these are safe ( in terms pseudorandomness ) or not. I will try and reason. Correct me if I am wrong.

1.) F1 = F(k,x)||k

F1 is not safe, since the concatenation of k will always happen. Since the k is fix it should be the same for two different requests x1 and x2 right? An attacker would notice that and realize that F1 is not a PRF.

2.) F2 = F(k,x) XOR y, where y is random {0,1}^l

This should be safe even if y wasnt random. Since F is pseudorandom the attacker cant distinguish between F and F XOR y since it is still looking random to the attacker, wether y is randomly selected or not.

3.) F3 = F(F(k,x),0^l)

So the inner F(k,x) acts as a key for the outer F. So this reduces to F(k',0^l). The input is plainly 0 but since we have a valid key unequal to zero,F3 should be pseudorandom. Additional question: Now if the key where to be 0^l and the input x something different then 0^l, we would receive an output exactly the same as the input x, every time right ?

I appreciate your time & effort

Answer 1

1. $F_1(k,x):=F(k,x)\mathbin\|k$

Beside the valid reason cited, another (rather worse) reason why that's not a PRF is that one example outputs reveals $k$, which then allows to compute $F_1(k,x)$ for any $x$ given the (assumed public) definition of $F$.

2. $F_2(k,x):=F(k,x)\oplus y$ for some $y$

As long as $y$ is fixed or otherwise independent of $(k,x)$, this is safe. The reasoning given is OK, if not formal. A formal reasoning would construct a distinguisher for $F$ from an hypothetical one for $F_2$, the definition of $y$, and perhaps invocation of $F$ (though that won't be necessary in the case at hand).

3. $F_3(k,x):=F(F(k,x),0^\ell)$

That definition requires the key of the outer $F$ to be of the same size as the output of the inner $F$, which restricts to some $F$ with output the size of their key (which I'll assume), or complicates things.

The input is plainly 0 but since we have a valid key unequal to zero, $F_3$ should be pseudorandom.

The conclusion is correct but the reasoning is wrong

• "unequal to 0" is unwarranted; $F(k,x)=0^\ell$ could well occur for some $k$ and $x$, or even regardless of $x$ for some vanishing fraction of $k$
• Nothing special occurs for $F$ when it's key is $0^\ell$ (all-zero) key.
• If the key of the outer $F$ was whatever known constant rather than $F(k,x)$, then $F_3$ would not be a PRF.

What matters is that for unknown random $k$, $F_3(k,x)$ is $F(k_x,0^\ell)$ for $k_x=F(k,x)$ with $k_x$ indistinguishable from a random value except that it's a function of $x$, thus $F_3(k,x)$ is indistinguishable from a random value except that it's a function of $x$. Again, that's informal, and I don't immediately see a formal reasoning (perhaps a hybrid argument would do, but that's out of my comfort zone).

If the key where to be $0^\ell$ and the input $x$ something different from $0^\ell$, we would receive an output exactly the same as the input $x$, every time right ?

No. There's nothing special with the $0^\ell$ (all-zero) key. It's a constant key, like any other one.