Show that function isn't a PRF

Question

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.

Answer 1

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