Garg's work has been very influential, even comparable to Craig Gentry's fully homomorphic encryption breakthrough. Like FHE, the influence has been mostly theoretical so far, but history has shown that things that appear theoretical today can be practical tomorrow. I'm not holding my breath, though.
While obfuscation has been the most touted application of the multilinear maps, another straightforward application of these maps is for single-round N-party Diffie-Hellman.
Consider a map that respects f(G, G)^ab = f(aG, G)^b = f(G, bG)^a = f(aG, bG). Then 3 parties A, B, C, with secret keys a,b,c can agree on a shared key by broadcasting aG, bG, and cG (let's assume that the discrete logarithm is hard in this group). The shared key will be f(aG, bG)^c = f(aG, cG)^b = f(bG, cG)^a = f(G, G)^abc. This was in fact one of the first applications of bilinear maps via the Weil pairing, discovered by Joux [1].
There's an obvious generalization of the concept to N parties with an (N-1)-linear map, but until recently no cryptographically useful maps had been discovered for this effect.
No, not that I know of. You're of course right that what exists today are approximations. But the maps can be made to work for any given n, so we can pretend they're 'real'.
This is pretty neat stuff. It suggests that you can run trusted code on an un-trusted machine, and trust the results, all while not revealing the code. Imagine "your homework is correct" without "here are the answers."
There may be limitations, this is denser than I can really parse, but if this is open ended, it could lead to some interesting use cases.
On the down side, obfuscation appears to win, which I did not expect.
From the explanation, the obfuscation seems to be akin to encryption in that it is easy to go from normal code to obfuscated, but difficult to go back.
http://www.cs.ucla.edu/~sanjamg/Sanjam%20Garg_files/sanjam-t...
Garg's work has been very influential, even comparable to Craig Gentry's fully homomorphic encryption breakthrough. Like FHE, the influence has been mostly theoretical so far, but history has shown that things that appear theoretical today can be practical tomorrow. I'm not holding my breath, though.
While obfuscation has been the most touted application of the multilinear maps, another straightforward application of these maps is for single-round N-party Diffie-Hellman. Consider a map that respects f(G, G)^ab = f(aG, G)^b = f(G, bG)^a = f(aG, bG). Then 3 parties A, B, C, with secret keys a,b,c can agree on a shared key by broadcasting aG, bG, and cG (let's assume that the discrete logarithm is hard in this group). The shared key will be f(aG, bG)^c = f(aG, cG)^b = f(bG, cG)^a = f(G, G)^abc. This was in fact one of the first applications of bilinear maps via the Weil pairing, discovered by Joux [1].
There's an obvious generalization of the concept to N parties with an (N-1)-linear map, but until recently no cryptographically useful maps had been discovered for this effect.
[1] http://link.springer.com/article/10.1007%2Fs00145-004-0312-y...