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

  • $\begingroup$ 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! $\endgroup$
    – Saar
    Jul 18, 2022 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.