# Indistinguishability obfuscation for secure software

**Question: What happened to make secure software suddenly seem possible?**

**Allison Bishop Lewko**: The short answer is that in 2013, six researchers—Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters—published

*a paper*showing for the first time that it is possible to obfuscate software in a mathematically rigorous way using a new type of mathematical structure called

*multilinear maps*(see sidebar for definition). This means I can take a software program and put it through the mathematical structure provided by these multilinear maps and encrypt software to the machine level while preserving its functionality. Anyone can take this obfuscated software and run it without a secret key and without being able to reverse-engineer the code. To see what’s happening in the code requires solving the hard problem of breaking these multilinear maps.

**How does obfuscation differ from encryption?**

**How so? Do you use the same methods to encrypt data to obfuscate code?**

**Is having two matrices for every slot a way to add randomness?**

**What does obfuscated software look like?**

**Indistinguishability obfuscation is said to provide a richer structure for cryptographic methods. What does that mean?**For a dozen years it was an open problem on how to extend bilinear maps to multilinear maps in the realm of algebraic geometry, but elliptic curves didn’t seem to have a more computationally efficient structure on which to build. During this time, Craig Gentry (now at IBM) was working on * fully homomorphic encryption*, which allows someone to perform computations on encrypted data (the results will also be encrypted). Gentry was using lattices, a type of mathematical structure from number theory, an entirely different mathematical world than algebraic geometry.

*Candidate Multilinear Maps from Ideal Lattices*where the authors were able to make a sharp threshold between easy and hard problems within lattice problems. They did it by taking something like a fully homomorphic scheme and giving out a partial secret key; one that lets you do this one thing at level 10 but not at level 11. These partial keys, which are really weak secret keys, add more nuance, but it’s extremely tricky. If you give out a weak key, you may make things easy that you don’t want to be easy. You want it to break a little but not too badly. This is another source of inefficiency.

**How soon before obfuscated software becomes a reality?***this-uses-math-and-it-looks-like-we-don’t-know-how-to-break-it.*

**Is that the purpose of the Center for Encryption Functionalities?**

**What is your role?**

**Have there been any attempts to “break” indistinguishability obfuscation?**

**Were you surprised that the problem was broken?**

*Do the breaks shake your faith in indistinguishability obfuscation?**Indistinguishability Obfuscation for Turing Machines with Unbounded Memory*at STOC, which replaces circuits with a Turing machine to show conceptually that we can do obfuscation for varying input sizes.

Proposal for fully homomorphic encryption grounded in the known math around regular lattices:

*A Fully Homomorphic Encryption Scheme*, PhD thesis by Craig Gentry (now at IBM).

Multilinear maps from ideal lattices to supply hard problems for cryptography:

*Candidate Multilinear Maps from Ideal Lattices*by Sanjam Garg, Craig Gentry, Shai Halevi. This paper in particular proposed a new mathematical building block, generating an explosion of papers. Most of exciting was which was:

*Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits*by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters.

**Hiding secrets inside software.**

If software can be made unintelligible, other information like passwords, digital signature, and encryption keys can be hidden inside software. Two possibilities are immediately obvious. Anything can be a password, including an email. And passwords would not have to be exchanged ahead of time before sending the message.

**Protecting software patches**. Security updates, or patches, intended to plug security holes may serve as a convenient pointer to the vulnerability being fixed, which hackers can then exploit in devices not yet updated.

**Entrusting software to the cloud**, or otherwise distributing proprietary or valuable algorithms. Valuable, sensitive, or proprietary software, once obfuscated, can be distributed without fear it will be reverse-engineered. Financial institutes can distribute trading algorithms. Software on captured military drones will remain unreadable. Manufacturers could distribute encrypted DVDs.