Paper 2022/615

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.

Metadata
Available format(s)
PDF
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
2022-05-23: received
Short URL
https://ia.cr/2022/615
License
Creative Commons Attribution
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.