Smoothing Codes and Lattices: Systematic Study and New Bounds
- 16 May 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (9) , 6006-6027
Abstract
In this article we revisit smoothing bounds in parallel between lattices 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 and codes, transferring techniques between both areas. We also consider multiple choices of 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 holds for both codes and lattices and all noise distributions at hand. For an average-case analysis, the linear programming bound can be replaced by an expected value computation. This alone gives optimal results for spherically uniform noise over random codes and random lattices. This also improves prior Gaussian smoothing bounds for worst-case lattices, but surprisingly this provides even better results with uniform ball noise than for Gaussian (or Bernoulli noise for codes). This counterintuitive situation can be resolved by adequate decomposition and truncation of Gaussian and Bernoulli distributions into a superposition of uniform noise, giving further improvement for those cases, and putting them on par with the uniform cases.Keywords
All Related Versions
Funding Information
- French Agence Nationale de la Recherche through ANR JCJC COLA (ANR-21-CE39-0011)
- ERC H2020 (74079 (ALGSTRONGCRYPTO))
This publication has 27 references indexed in Scilit:
- Worst‐Case to Average‐Case Reductions Based on Gaussian MeasuresSIAM Journal on Computing, 2007
- Uniform Bounds for Bessel FunctionsJournal of Applied Analysis, 2006
- Bounds on Distance Distributions in Codes of Known SizeIEEE Transactions on Information Theory, 2005
- New upper bounds on sphere packings IAnnals of Mathematics, 2003
- Estimates of the Distance Distribution of Codes and DesignsElectronic Notes in Discrete Mathematics, 2001
- Strong asymptotics for Krawtchouk polynomialsJournal of Computational and Applied Mathematics, 1998
- Association schemes and coding theoryIEEE Transactions on Information Theory, 1998
- Random random walks on ℤ2 dProbability Theory and Related Fields, 1997
- Krawtchouk polynomials and universal bounds for codes and designs in Hamming spacesIEEE Transactions on Information Theory, 1995
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977