Title : Polynomial Time Bounded Distance Decoding near Minkowski's bound in Discrete Logarithm Lattices
Speaker: Leo Ducas
Affiliation: CWI, Amsterdam
Time: 13:00 Wednesday, 31 January, 2018
Location: 303-257
[Joint work with Cecile Pierrot.] The construction of lattices which admit efficient Bounded Distance Decoding (BDD) algorithm is the computational variant of the sphere packing problem, and is motivated by error correction over *analog* noisy channels. While quasi-optimal lattices are known for sphere packing (i.e. lattices almost reaching Minkowski's bound on the minimal distance), the computational results fall short: the best known polynomial-time algorithm (Micciancio-Nicolesi 2008) only achieves a decoding radius that is a factor O(n^(1/4)) away from Minkowski's bound, where n denotes the dimension of the lattice. In this presentation, we will revisit the lattice and the decoding algorithms underlying the deprecated knapsack-based cryptosystem of Chor and Rivest (1988). Properly parametrized, and up to a few extra tricks, we obtain a lattice with a polynomial-time BDD algorithm achieving a decoding radius only a factor O(log n) away from Minkowski's bound.

Seminar list