[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. |