# Regarding Pseudo Random Functions

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

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

1. $$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).

1. $$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.