### Smoothing Codes and Lattices: Systematic Study and New Bounds

Thomas Debris-Alazard, Léo Ducas, Nicolas Resch, and Jean-Pierre Tillich

##### Abstract

In this article we revisit smoothing bounds in parallel between lattices \emph{and} codes. Initially introduced by Micciancio and Regev, these bounds were instantiated with Gaussian distributions and were crucial for arguing the security of many lattice-based cryptosystems. Unencumbered by direct application concerns, we provide a systematic study of how these bounds are obtained for both lattices \emph{and} codes, transferring techniques between both areas. We also consider various spherically symmetric noise distributions. We found that the best strategy for a worst-case bound combines Parseval's Identity, the Cauchy-Schwarz inequality, and the second linear programming bound, and this for both codes and lattices, and for all noise distributions at hand. For an average-case analysis, the linear programming bound can be replaced by a tight average count. This alone gives optimal results for spherically uniform noise over random codes and random lattices. This also improves previous Gaussian smoothing bound for worst-case lattices, but surprisingly this provides even better results for uniform noise than for Gaussian (or Bernouilli noise for codes). This counter-intuitive situation can be resolved by adequate decomposition and truncation of Gaussian and Bernouilli distribution into a superposition of uniform noise, giving further improvement for those cases, and putting them on par with the uniform cases.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Code-based cryptographylattice-based cryptographysmoothing parameter
Contact author(s)
thomas debris @ inria fr
L Ducas @ cwi nl
Nicolas Resch @ cwi nl
jean-pierre tillich @ inria fr
History
Short URL
https://ia.cr/2022/615

CC BY

BibTeX

@misc{cryptoeprint:2022/615,
author = {Thomas Debris-Alazard and Léo Ducas and Nicolas Resch and Jean-Pierre Tillich},
title = {Smoothing Codes and Lattices: Systematic Study and New Bounds},
howpublished = {Cryptology ePrint Archive, Paper 2022/615},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/615}},
url = {https://eprint.iacr.org/2022/615}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.