If we want to construct a PRF that is length preserving, it is easy to show with hybrid proof that the resulting construction is a PRF.

But what happens when we have longer input. Supose that the key and output length are $n$ and the input size is $2n$.

I have been imagining what could happen to the binary tree. I feel like since input is double the size it will go double the depth. But in this case I cant tell if the resulting construction is a PRF.

Any hint would be helpful!


1 Answer 1


The input size and the key size need not have any specific relation. The security analysis of GGM goes through as long as the key size is equal to the seed size of a secure length-doubling pseudorandom generator, independently of the input size, which can be an arbitrary polynomial in the security parameter.

Since the depth of the GGM tree is exactly the input length, if you double the input length, you indeed double the depth of the tree. The security analysis remains identical: the only difference is the number of hybrids in the proof, but changing the number of hybrids by any polynomial amount does not harm security, since the adversary has negligible advantage in distinguishing any two hybrids.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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