8
$\begingroup$

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 ?

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ I'd like to tell you, but the article is, well, a bit hard to make out. $\endgroup$
    – Will Jagy
    Commented Feb 4, 2014 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
    Commented Feb 4, 2014 at 5:03
  • 4
    $\begingroup$ Maybe you should ask this on cstheory.stackexchange.com $\endgroup$
    – Amritanshu Prasad
    Commented Feb 4, 2014 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
    Commented Feb 4, 2014 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
    Commented Feb 4, 2014 at 15:18

1 Answer 1

Reset to default
9
$\begingroup$

"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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think the actual question was to describe what the scheme is, not the question from the title. $\endgroup$
    – Aurel
    Commented Nov 8, 2016 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
    Commented Nov 8, 2016 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
    Commented Nov 8, 2016 at 16:19
  • 1
    $\begingroup$ Fair enough :-) $\endgroup$
    – Aurel
    Commented Nov 8, 2016 at 16:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .