# Is $f\colon x\mapsto g(x+1)$ necessarily a pseudorandom function?

Let $l\in\mathbb N$ and suppose $$g\colon\;\{0,1\}^l\to\{0,1\}^l$$ is a pseudorandom function. Is $f$, defined as below, necessarily a pseudorandom function as well?

$$f(x)=g((x+1)\bmod2^l)$$

-
Hint: if you had a distinguisher for $f$ (that is, a way to distinguish $f$ from a random function with some advantage), could you use that to distinguish $g$ from random? – poncho Apr 10 '15 at 19:45
Dear poncho , to be honest I don't know what you mean because if you can find a distinguisher for $f$ so the question is solved and if show the distinguisher so I will have the answer of the above question. – ebad Apr 10 '15 at 20:01
If we were to have a distinguisher for $f$, what would that imply about $g$? If we know that $g$ doesn't have a distinguisher, what does that imply about $f$? – poncho Apr 10 '15 at 20:10
I think I understood your question but I don't know the answer – ebad Apr 10 '15 at 20:19

So, assume $f$ isn't a PRF. That means that there's an efficient algorithm with a function as its input that can reliably tell whether you gave it $f$ or gave it a random function as input, by evaluating its input at a bunch of points. You can modify this algorithm to tell $g$ apart from a random function -- because $f(x)=g(x+1)$, just tweak the algorithm so that every time it evaluates the function you had passed it at $x$, it instead evaluates it at $x+1$. If you run this algorithm with $g$ as input, it acts exactly like your original algorithm did with $f$ as input. If you pass it a random function as input, the random function is still random. So, this new algorithm can tell $g$ apart from a random function, and $g$ isn't a PRF.
Because any distinguisher for $f$ can be tweaked to make a distinguisher for $g$, it means that $g$ can only be a PRF if $f$ is, so if $g$ is a PRF then $f$ is a PRF. This kind of argument is extremely useful when building cryptographic functions using primitives; it even works when the properties of the underlying primitive and your construction are different (you show that an attack on property A of your construction lets you attack property B of the underlying primitive).