I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one:
Let G(k) be a PRG with |k| = n, and G'(k) the output of G(k) truncated to the first n bits. Prove that $F_k(x) = G'(k) \oplus x$ is not pseudorandom.
The only thing I can say is that $F_k()$ has a very specific structure, not chosen randomly from $1/2^n$.
Any hints?
Before answering the actual question, I will offer some general advice.
To turn to the main question, we first need to know and undertand the definition of a pseudorandom family of functions. We consider a function $F$ which maps each pair of strings $(k,x)$ of equal length to a third string $y$ of the same length as $k$ and $x$. For any string $k$ of length $n$, we note $F_k$ the function which maps the $n$-bit string $x$ to the $n$-bit string $y$ (i.e., $F_k(x) = F(k,x)$. The string $k$ is called the key. I only state the definition of a pseudorandom function without a lengthy discussion (which can be found in the book).
The function $F$ defined above is pseudorandom if it satisfies the following two conditions.
- Easy to compute. There is a deterministic polynomial-time algorithm $C$ such that $C(k,x) = F_k(x)$ for any strings $k$ and $x$ of equal length.
- Pseudorandom. For every probabilistic polynomial-time algorithm $D$, every polynomial $p$ and all sufficiently large $n$, we have $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] - \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right| < \frac{1}{p(n)}.$$
My notation is as follows:
Here, you want to prove that the given function is not pseudorandom, meaning that it does not satisfy the definition above. In other words, that it satisfies its logical negation. Since the logical negation of the definition is not entirely trivial, it is best stated explicitly. Typically, the "easy to compute" condition will be satisfied, so we only give the negation of the pseudorandomness condition.
A function $F$ as above which is easy to compute is not pseudorandom if there exists a probabilistic polynomial-time algorithm $D$ and a polynomial $p$ such that for infinitely many $n$, we have $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] - \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right| \ge \frac{1}{p(n)}.$$
We can finally define the algorithm $D$ (we denote by $\mathcal{O}$ the function computed by the oracle). On input $1^n$, it proceeds as follows.
Compute $y_0 = \mathcal{O}(0^n)$.
Compute $y_1 = \mathcal{O}(1^n)$.
If $y_0 \oplus y_1 = 1^n$, output $1$. Otherwise, output $0$.
We must determine the probability that $D$ outputs $1$ in each case: when $\mathcal{O}$ is $F_k$ for a uniformly chosen $k$, and when it is a uniformly chosen $f$.
In the first case, regardless of what $k$ is, we have $y_0 = G'(k) \oplus 0^n = G'(K)$ and $y_1 = G'(K) \oplus 1^n$. Hence we have $y_0 \oplus y_1 = G'(k) \oplus G'(k) \oplus 1^n = 1^n$, and $D$ ouputs $1$ with probability $1$.
For the second case, we note that $D$ outputs $1$ if and only if $y_1 = y_0 \oplus 1^n$. If $f$ is a totally random function, $y_1$ is chosen among all $2^n$ strings of length $n$ uniformly and independently of $y_0$, and so it will equal $y_0 \oplus 1^n$ with probability $1/2^n$.
Hence finally we see that for all $n$, the value of the big probability expression in the definition equals $1-\frac{1}{2^n}$. If $n > 0$ this is at least $\frac{1}{2}$, and so we can take $p$ to be the constant polynomial $2$.
fkraiem's notation is quite confusing.
The security parameter $1^n$ used in the definition of a pseudorandom function is in unary, which does not contain 0, since only unary uses only 1 symbol.
When you use $1^n$ and $0^n$ in the definition of the adversary, it then seems like you're mixing up unary and binary strings. If you use $1^n$ to refer to a binary string of only 1s, I fail to see why that's relevant because that is not the string used in the definition of the pseudorandom function.
If $1^n$ is a unary string and $0^n$ is a binary string, well you need to make that clear because it's not at all obvious that they are strings in different bases.
EDIT: Having now read example 3.26 in Introduction to Modern Cryptography 2nd Edition, I believe that your choice of $1^n$ and $0^n$ are indeed binary strings but they are arbitrary could have been anything else. In which case I believe the book's use of $x_1$ and $x_2$ makes things clearer.
