تقرير
Smoothing Codes and Lattices: Systematic Study and New Bounds
العنوان: | Smoothing Codes and Lattices: Systematic Study and New Bounds |
---|---|
المؤلفون: | Debris-Alazard, Thomas, Ducas, Léo, Resch, Nicolas, Tillich, Jean-Pierre |
سنة النشر: | 2022 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Computer Science - Information Theory, Computer Science - Cryptography and Security |
الوصف: | 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 distribution. 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 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 with uniform ball noise than for Gaussian (or Bernoulli noise for codes). This counter-intuitive 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. |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2205.10552 |
رقم الأكسشن: | edsarx.2205.10552 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |