# Is this obfuscation scheme unbreakable?

I've just come across this popular article about a breakthrough (which can be purchased here), published in Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium by a team of cryptographers (Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai and Brent Waters) showing that the workings of a computer programme can be obfuscated. The author writes :

This obfuscation scheme is unbreakable, the team showed, provided that a certain newfangled problem about lattices is as hard to solve as the team thinks it is.

Would someone care to share with us the problem about lattices that is alluded to here ?

• I'd like to tell you, but the article is, well, a bit hard to make out. Commented Feb 4, 2014 at 4:29
• Aww, and that was my second draft. I was trying to say something funny along the lines of the paper about obfuscation having been obfuscated itself...My first try was just Eschew Obfuscation. Commented Feb 4, 2014 at 5:03
• Maybe you should ask this on cstheory.stackexchange.com Commented Feb 4, 2014 at 10:59
• It might be the shortest vector problem for ideal lattices. Finding the shortest vector in a lattice is, in general, computationally infeasible. You can base a cryptosystem on a computationally infeasible problem, provided you have a "trapdoor". For lattices that come from ideals, there's a way to do computations efficiently and have a trapdoor. The question is whether the shortest vector problem is as hard for ideal lattices as for general lattices. Commented Feb 4, 2014 at 12:15
• It's not the shortest vector problem for ideal lattices; that wouldn't be newfangled. The authors define something called a Multilinear Jigsaw Puzzle scheme and assume that Jigsaw generators produce computationally indistinguishable output. The details are complicated and I'm not sure what the point is of trying to explain it in non-specialist terms. As far as cryptographic assumptions are concerned, innovation is a defect and not a virtue. You want your cryptographic system to depend on standard assumptions, not newfangled ones that you just made up. Indeed, the authors say so in the paper. Commented Feb 4, 2014 at 15:18

"Is this obfuscation scheme unbreakable?"

"Well.. no." said people a couple of years later.

1. On GGHRSW13 specifically: Cryptanalyses of Candidate Branching Program Obfuscators