Hardness amplification of PRFs by increasing key length

Question

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$?

Answer 1

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.