end of the last multilinear map?

[D. J. Bernstein]

In https://eprint.iacr.org/2015/1037, Coron describes a "cryptanalysis
of the GGH15 graph-induced multilinear maps from lattices". Apparently
"cryptanalysis" here means a very fast, very reliable attack.

Are all multilinear-map proposals broken now?

---Dan

[Christopher J Peikert]

It depends on what problem you want to be hard -- i.e., what assumption you want to make about the MLM.

All "direct" constructions of multi-partite key agreement from MLMs are broken.  That is, the multi-party analogue of the Diffie-Hellman assumption is false for all MLM candidates to date.

However, many proposed obfuscators based on MLMs still remain unbroken.  In short, this is because the key-agreement attacks exploit public "low-level encodings of zero," but obfuscators don't give out such encodings (at least not directly).

Whether the attacks can be extended to work against obfuscators is obviously a very important question...

Chris

[D. J. Bernstein]

Christopher J Peikert writes:
> Whether the attacks can be extended to work against obfuscators is obviously a
> very important question...

A new paper says that it presents "the first polynomial-time
cryptanalysis of candidate iO schemes over GGH13":

https://eprint.iacr.org/2016/147

It's not immediately obvious to me what the attack algorithm does to,
e.g., GGH13-based point obfuscation, or what its performance might be
against the 25-gigabyte point-obfuscation challenge that Apon, Huang,
Katz, and Malozemoff announced at the Crypto 2014 rump session. The
current speed record for attacks is our paper

https://eprint.iacr.org/2015/151

which broke the challenge in 19 minutes using 21 PCs.

---Dan