yuuwwang/aicrypto huggingface dataset:
\paragraph{Problem 6 (18 points)}
In the class we have learned that random matrices are very useful in building candidate cryptographic schemes. In this problem we try an idea of using random matrices in building pseudorandom functions (PRFs).

Let $F:=\{ F^n:= \{ f^n_k: \{0,1\}^n \to \{0,1\} \}_{k\in \mathcal{K}^n} \}_{n\in\mathbb{N}}$ be a function family. 
For every $n\in\mathbb{N}$, we construct a keyed function $f^n_k: \{0,1\}^n \to \{0,1\}$ as follows: 
\begin{enumerate}
\item To generate the key $k$, we sample $2n$ random binary invertible matrices 
\[ M_{1, 0}, M_{1, 1}, M_{2, 0}, M_{2, 1}, ..., M_{n, 0}, M_{n, 1} \in \mathbb{Z}_2^{n\times n},\] 
and let  $k = \{ M_{1, 0}, M_{1, 1}, M_{2, 0}, M_{2, 1}, ..., M_{n, 0}, M_{n, 1} \}$. 
\item To evaluate, let the input $x = x_1|x_2|...|x_n\in\{0,1\}^n$. We compute $W_x := \prod_{i = 1}^n M_{i, x_i}$, and output the first bit of $W_x$ (i.e., the first row and first column of $W_x$). In other words, we use $x$ to select a subset of matrices from the key $k$ and take the subset product, get a matrix $W_x$, and pick the first bit of $W_x$ as the output.
\end{enumerate}

Show that $F$ is not a PRF family.