# How to prove that a function is not pseudorandom?

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?

1. It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this case it has one which is conceptually identical to the one you have given here (where $G'(k)$ is replaced by $k$).
2. It is crucial to know and understand your definitions. Here, you want to show that a certain family of functions is not pseudorandom (i.e., does not satisfy the definition of a pseudorandom family of functions), but it is not clear that you understand what this means (you do not articulate it in your question). You must understand this definition if you want to be able to show that a certain construction does or does not satisfy it.
3. Broadly speaking, you seem to lack what is commonly known as mathematical maturity, which is not knowledge of any specific mathematics, but rather the ability to see how to connect the dots in a mathematical argument between the hypotheses and the conclusion. Indeed, a telltale sign of someone who is not "mathematically mature" is that they balk at the mere sight of the word "proof" and seem unable to make any progress beyond stating the hypotheses. Unfortunately, cryptography is not the best of places to "get your feet wet" in writing proofs because it is a very complicated business (most results in cryptography aim to prove that it is impossible to do something), and you can feel overwhelmed pretty quickly. For this reason, abstract algebra or real analysis are better training grounds, even if you have no intention of studying them for their on sake.

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:

• $\{0,1\}^n$ is the set of all strings of length $n$.
• $\mathrm{Func}_n$ is the set of all functions from $\{0,1\}^n$ to itself.
• $k \gets X$, where $X$ is a finite set, means that $k$ is randomly and uniformly chosen from $X$.
• $D^f$ denotes the algorithm $D$ when given oracle access to the function $f$. That is, $D^f$ can obtain $f(x)$, for any $x$ of its choice, at the cost of only one operation.
• $\mathrm{Pr}[A : P(x)]$ denotes the probability that $P(x)$ holds after the execution of $A$.

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.

1. Compute $y_0 = \mathcal{O}(0^n)$.

2. Compute $y_1 = \mathcal{O}(1^n)$.

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

• You have to construct an algorithm which is able to distinguish this function from a random one. Remember that your algorithm can obtain $f(x)$ for (polynomially many) arbitrarily chosen $x$. Maybe there is some specific $x$ for which $f(x)$ gives you a hint? What about $f(0^n)$ for example? – fkraiem Jul 25 '15 at 13:12
• In that example, for two inputs $x$ and $y$, where $|x| = |y|$, then $F_k(x) \oplus F_k(y) = x \oplus y$ with probability one, while that equality holds with small probability for a true random function. An Adversary basing its guess on the truth of that equality will have very high Advantage in distinguishing the Function from a random function. Therefore the Function is not pseudorandom. – J.D. Jul 25 '15 at 13:17
• So in the case that $f = F_K$, you have $f(0^n) = G'(k)$, and so for any $x$ you have $f(x) = f(0^n) \oplus x$. On the other hand, this last equality is very unlikely to hold for a random function, because $f(x)$ is randomly chosen, and so it can equal $f(0^n) \oplus x$ only with probability $1/2^n$ (if $x \ne 0^n$). – fkraiem Jul 25 '15 at 13:37
• @pa5h1nh0 - If the XOR of the two inputs equals the XOR of the two outputs, then with high probability the function is $F_k(x)$ and not a random function. This shows that $F_k(x)$ is not pseudorandom (because it can be distinguished from random with non-negligible Advantage). – J.D. Jul 25 '15 at 14:13
• Note that this is essentially the same thing as Example 3.26 in the book (page 79). Maybe your problem is just that you don't pay enough attention... – fkraiem Jul 25 '15 at 14:27

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.

• Downvoter: Can you point out what I said was incorrect? – 1f604 Nov 10 '16 at 11:47