Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?


share|improve this question
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 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 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 at 20:10
I think I understood your question but I don't know the answer – ebad Apr 10 at 20:19

1 Answer 1

up vote 3 down vote accepted

The general way to answer questions like this in the affirmative (i.e. prove that some transformation of a certain type of thing gives you another of that type of thing) is to assume that your transformed version doesn't have the property you need, and use that to prove that the original also doesn't have that property. Then if the original does have the property we want, so must the transformed version.

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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