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 ?

  • 8
    $\begingroup$ I'd like to tell you, but the article is, well, a bit hard to make out. $\endgroup$ – Will Jagy Feb 4 '14 at 4:29
  • 4
    $\begingroup$ 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. $\endgroup$ – Will Jagy Feb 4 '14 at 5:03
  • 4
    $\begingroup$ Maybe you should ask this on cstheory.stackexchange.com $\endgroup$ – Amritanshu Prasad Feb 4 '14 at 10:59
  • 3
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 4 '14 at 12:15
  • 6
    $\begingroup$ 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. $\endgroup$ – Timothy Chow Feb 4 '14 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

See also (concurrent, similar flavor):

  1. Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

  2. Zeroizing Attacks on Indistinguishability Obfuscation over CLT13

Some interesting candidates for secure obfuscation do remain.

See, for instance:

a) Secure Obfuscation in a Weak Multilinear Map Model

b) Preventing CLT Zeroizing Attacks on Obfuscation

  • $\begingroup$ I think the actual question was to describe what the scheme is, not the question from the title. $\endgroup$ – Aurel Nov 8 '16 at 16:14
  • $\begingroup$ The question, as-asked: "Would someone care to share with us the problem about lattices that is alluded to here?" ...is difficult to answer directly. The point is that there is no hard lattice problem underlying the proposed scheme's security. $\endgroup$ – Daniel Apon Nov 8 '16 at 16:18
  • 1
    $\begingroup$ By the time you arrive at the current state-of-the-art (and a lattice problem, or other hard problem, worth stating), the answer would be very off-topic to the question.. In any case, it seemed worth answering the dangling question from two years ago. $\endgroup$ – Daniel Apon Nov 8 '16 at 16:19
  • 1
    $\begingroup$ Fair enough :-) $\endgroup$ – Aurel Nov 8 '16 at 16:20

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.