Smoothing Bounds: From Lattices to Codes, and back to lattices


Séminaire AMAC: CASC

16/12/2021 - 09:30 Thomas Debris-Alazard (Inria) Salle 106 - Batiment IMAG

In either a code or a lattice, smoothing refers to fact that, as the error distribution grows wider and wider, the associated syndrome distribution tends towards a uniform distribution. In other words, the error distribution, reduced modulo the code or the lattice, becomes essentially flat. This phenomenon is pivotal in arguing security of many cryptosystems. In information theoretic literature, it is also sometimes referred to as flatness. 
Informally, by a ``smoothing bound'' we are referring to a result which lower bounds the amount of noise which needs to be added so that the smoothed distributions approximates well the desired distribution. In lattice-based cryptography, the literature ubiquitously uses Gaussian distributions for errors, and smoothness is guaranteed for an error growing as the inverse of the minimum distance of the dual lattice. In this work we generalize this result to codes and for any distributions. As we show, we improve smoothing bounds that are currently known. Interestingly, we also show that for lattices the Gaussian distribution is not the best choice for getting smoothing bounds. 

This is a joint work with Léo Ducas, Nicolas Resch and Jean-Pierre Tillich