7
$\begingroup$

I have recently developed interest about obfuscation, and I see that (all?) the proposals use multilinear maps. What's the reason to this? As I also that many of the multilinear map proposals get broken too. Are there any other approaches to achieve obfuscation, that use other mathematical structures?

$\endgroup$
10
$\begingroup$

Multilinear map is a very natural candidate to build obfuscation: it allows to perform operations on values in an oblivious way, and is in addition enhanced with a "zero-test" procedure, that can be used to obtain the result of a computation, but which should (hopefully) not reveal the intermediate steps of the computation. Hence, it gives a candidate for indistinguishability obfuscation (iO) of small enough circuits. From there, one can bootstrap to arbitrary circuits using fully homomophic encryption with a "small enough" decryption circuit: the circuit evaluation is done obliviously over the ciphertexts, and decryption of the result is performed using the multilinear map (informally).

So, the most obvious reason is that it feels natural. But there is a deeper reason: iO can be shown to imply multilinear maps, as proven is this recent paper. Some care must be taken here: multilinear maps are objects, like encryption schemes are. But one cannot talk about a primitive "implying" another primitive: the security properties that we considered must be taken into account. What the paper shows is that iO implies semantically secure multilinear maps, which were recently shown to also imply iO (see e.g. this paper). Therefore, up to some other classical primitives used in the various constructions, iO and semantically secure multilinear maps are essentially equivalent: if you have one, you have the other.

This does not mean that multilinear maps are necessarily the starting point of any iO construction, just that this starting point will necessarily be "as strong" as multilinear maps. For example, there is a rich line of works in building iO from functional encryption.

Finally, you mention that candidate multilinear maps have been broken. Again, one must treat this with care: one does not break an object, but a security assumption on this object. So, many security assumptions on multilinear maps have been broken, in various settings. For a long time, all these attacks relied on "encodings of zero", which are not used in iO constructions, so those attacks, while breaking mmaps in some sense, did not break iO. More recently, there have been some more powerful attacks (called annihiliation attacks) that threaten iO in some settings. But many of the most recent iO constructions, with more recent candidates of mmaps, remain unbroken. Still, these variety of attacks suggest that we are yet far from deeply understanding what can make iO secure; researchers do not show a considerable confidence in the security of current candidates, but recall that this is a young area, subject to many ongoing research.

$\endgroup$
3
+50
$\begingroup$

The paper Lattice-Based SNARGs and Their Application to More Efficient Obfuscation by Dan Boneh, Yuval Ishai, Amit Sahai and David J. Wu was accepted for publication at the upcoming EuroCrypt 2017.

It offers a much more efficient approach to iO, but still using multilinear maps (as Geoffroy Couteau kindly pointed out; best read his comment). Time will show, if it can withstand the attacks, but looking at the list of authors, chances are good that at least it opens up new directions for implementing iO.

$\endgroup$
  • 1
    $\begingroup$ An extremely warm welcome to crypto.SE, itsme. We can certainly do with more answers like the last three. $\endgroup$ – Maarten Bodewes Apr 4 '17 at 17:40
  • $\begingroup$ Also interesting is another recent work which relaxed the requirement to bilinear maps (plus "local" PRGs). $\endgroup$ – Occams_Trimmer Apr 4 '17 at 18:27
  • $\begingroup$ That was a lot helpful @itsme I also checked construction of io using MIFE by Prabhanjan Ananth . It's quite interesting to see the relation between iO and FE. $\endgroup$ – user38956 Apr 4 '17 at 20:47
  • 2
    $\begingroup$ The paper does not provide an approach to iO without mmaps! (Don't get me wrong, it's a wonderful paper and the result is very interesting). What it gives is an obfuscation-complete primitive, id est, a primitive $X$ so that any obfuscation of $X$ can be bootstrapped to get iO for all circuits. But although it is way more efficient than previously, the method does not differ, as we still need multilinear maps to obfuscate $X$. Previously, we had constructions of iO from iO for NC1, or functional encryption for NC1, all requiring multilinear maps. This paper is a new bootstrapping theorem. $\endgroup$ – Geoffroy Couteau Apr 5 '17 at 8:17

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.