alxdavids

lyon and obfuscation

I spent the early part of my PhD committing time to developing protocols for computing private set operations. These constructs allow two parties to swap characteristics of data sets that they hold without giving the whole set. The function of these protocols is founded in situations where it may be beneficial to swap data — but where releasing too much information carries negative consequences. The work I did on these protocols involved developing asymptotically optimal designs of both known set operations and those of novel functionality (basically computation is linear in the size of the input sets).

In my recent work I have trudged a path into slightly more theoretical climbs. I've spent a lot of time navigating the cryptographic wizardry implied by conjectured indistinguishability obfuscation (IO). Essentially an obfuscated program prevents someone from seeing the inner workings of the program while still providing a correct output for a given input. The result is that you can hide secret stuff in the program and anyone who access should not be able to infer anything about the secret content.1

There are a multitude of problems that are encountered in constructing obfuscators for certain functions. Notably, these include impossibility results for the ideal form (VBB) of obfuscation and the use of non-standard assumptions in constructing IO obfuscators for all circuits. In particular, recent IO constructions have been shown to be susceptible to attacks that target the reliance of all known designs on cryptographic graded encoding schemes. The current state is that security can only be proven in strange and suspicious models. I have been helping to keep track of the state of the field in general at malb.io/are-graded-encoding-schemes-broken-yet.html.

However, I was in Lyon2 for 15-16 December attending the monthly lattice meetings hosted by ENS (these are really great by the way — lattice people should go!). Zvika Brakerski gave a talk on his recent work where he and others show that VBB obfuscation is possible for a specific class of functions known as conjunctions. The most impressive facet of their work is that they can prove security via an encoding scheme that can be based on a standard an almost standard assumption (the entropic ring-LWE assumption). The construction is a super commendable piece of work. I have a feeling that if any more seismic movements are to be made in the field of obfuscation then this work will be fairly important...

  1. IO does not actually guarantee this immediately but it can be used to similar effect.

  2. I took this picture on my Nexus 5X, I think it turned out pretty well.