Representation technique - Applications to lattice problems, decoding problems and the subset sum problem

Talk by Anja Becker

Date: 18.11.13  Time: 11.00 - 12.00  Room:

The subset sum problem, coding problems and lattice problems allow to design cryptographic systems whose security relies on the intractability of the before mentioned problems. We will focus on a recently developed algorithmic technique that applies to the problems and allows for improved asymptotic running times.

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1, thereby improving a 30 year-old algorithm by Shamir and Schroeppel. The paper presented a new algorithmic approach which solves the original problem by first identifying and solving exploitable subproblems. Our research generalized the technique and allowed for an additional drop of the complexity.

In a follow-up project, we developed a way to use this representation (or decomposition) technique in the domain of linear codes. The new algorithm permits to solve the syndrome decoding problem for random linear codes within the framework of information set decoding.

Our most recent work is an algorithm that solves the shortest vector and closest vector problem for random lattices. The technique is orthogonal to state-of-the-art methods based on sieving or enumeration.

All the above algorithms are probabilistic and are based on heuristics. The alternative technique improves the running times by exponential factors using an exponentially large amount of memory. Our experiments show that the algorithms works well in practice for accessible dimensions. The exponential gain in theory can therefore not necessarily be observed in practice for current dimensions due to polynomial factors. The crossover points are yet to be determined.

Joined work with J-S Coron, N Gama, A Joux, A May, A Meurer