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 ?

mightbe 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:15standardassumptions, not newfangled ones that you just made up. Indeed, the authors say so in the paper. $\endgroup$ – Timothy Chow Feb 4 '14 at 15:182more comments