I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF constructions which take into account key length for increasing hardness? Alternatively, are there any constructions which transform a $(t, \epsilon)$ PRF of key length $k$ to something like $(t^2, \epsilon)$ PRF of key length $2k$ or $k^2$?


It's important to be clear about what is the purpose of the GGM construction. The GGM construction is designed to build a PRG out of a PRF: i.e., to construct one primitive, given an instance of a different primitive. It's not designed to increase the security of the underlying primitive.

This is a general theme in a lot of provable cryptography: you have to start with a primitive that is secure; then you can build other things out of it, but the primitive you start with has to be secure, or else you can't do anything. The standard constructions don't increase the security of the basic primitive; instead, that's the job of the person who designed the basic primitive.

Hardness amplification is a different task. Hardness amplification means: given a primitive of type T, build another primitive type T that is more secure (in some sense). In general, provably-secure hardness amplification is very difficult to achieve. Why? Well, we don't know how to build any crypto algorithm that is provably secure; all we know is conditional results (if you give me a secure one-way function, then I can build other things that are secure).

There are some examples of techniques that given a $(t,\epsilon)$-scheme construct a new scheme that is something like $(t,\epsilon^2)$-secure, but that's different. (If you're interested in that, spend some quality time with Google and Google Scholar looking at results on "hardness amplification"; see, e.g., Yao's XOR lemma.) I don't know of any techniques that given a $(t,\epsilon)$-scheme construct a $(t^2,\epsilon)$-scheme.

| cite | improve this answer | |
  • $\begingroup$ I did not ask my question completely. I have edited it now to include that I also wanted to know if there are any constructions of PRF from PRG which can use larger key length. $\endgroup$ – nikhil_vyas Jul 17 '16 at 9:47
  • $\begingroup$ @nikhil_vyas, my answer covers that case as well -- the bottom line remains the same, I'm afraid. $\endgroup$ – D.W. Jul 17 '16 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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