# Show that function isn't a PRF

Let $$F$$ be a PRF such that $$|F(k,x)|=2n$$ show that $$F_2$$ isn't a PRF. Let's assume $$F(k,x)=(y_1,...,y_{2n})$$ then $$F_2(k,x)=(y_1\land y_2,...,y_{2n-1}\land y_{2n})$$.

I want to prove $$F_2$$ isn't a PRF but not sure where to start from since I don't really know much about $$F$$.

I thought about looking how many 0's are there since for a random string $$r$$, each entry is 0 in probability $$\frac{3}{4}$$ and since $$F$$ is a PRF it should act similarly to pure random.

But not sure how to calculate the probabilities of such a distinguisher and show that pure random and this $$F_2$$ are computationally distinguishable.

## 1 Answer

So, the effect of the unknown key $$k$$ is reflected in the $$2n-1$$bit output of $$F(k,x)$$ and it can be ignored.

A random uniform sequence $$r$$ of length $$2n-1$$ with equally likely zeroes and ones has Hamming weight distributed according to $$\mathbb{Bin}(2n-1,1/2)$$ while your $$F_2(k,x)$$ assuming $$F(k,x)$$ is random has Hamming weight distributed according to $$\mathbb{Bin}(2n-1,1/4).$$

Define the treshold below which you will declare non-random as $$t=3(2n-1)/8$$ (the midpoint between $$(2n-1)/2$$ and $$(2n-1)/4$$; this can be made more precise by carefully considering the flawed $$F_2(k,x)$$ distribution). The point is that with overwhelming probability a random string will have Hamming weight above $$t.$$

We use the simplified Chernoff bound on Binomial tails (see Wikipedia). For independent random variables $$X_1,\ldots,X_m$$ in $$\{0,1\}$$ with $$X=X_1+\cdots+X_m$$ and mean $$\mathbb{E}[X]=\mu,$$ we have $$Pr[X\leq (1-\delta)\mu]\leq \exp[-\delta^2 \mu/2].$$ Here, $$\mu=(2n-1)/2,$$ and $$\delta=1/8.$$ This gives the upper bound $$Pr[\mathrm{HammingWeight}[r]\leq t] \leq \exp[-(1/8)^2 (2n-1)/4]=\\ =\exp[-(2n-1)/256]\approx \exp[-n/128].$$ This is falling exponentially and can be made arbitrarily small by choosing $$n$$ large enough. For example if $$n=2^{12},$$ the upper bound is roughly $$\exp[-2^{12-7}]=\exp[-2^5]\approx 2^{-32 /\ln 2}=2^{-46}.$$

• Thanks for the answer! I meant that $F$ has an output of length $2n$ and $F_2$ has output of length $n$, I guess it wasn't that understandable, I'll learn for my next questions :) For my question I'll just fix the numbers in my own calculation, thanks a lot! Jul 18 at 14:14