Lattice-based cryptography relies in great part on the use of the Learning With Errors (LWE) problem as hardness foundation. Its algebraic variants, Ring-Learning with Errors (RLWE) and Polynomial Learning with Errors (PLWE), gain in efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the smearing condition, a condition for attacks on PLWE and RLWE introduced in by Elias et al. We demonstrate the parallels between the smearing condition and the Coupon Collector's Problem and develop recursive methods for computing the probability of smearing. We also present an algorithm on the PLWE decision problem with small parameters using the smearing condition. This is joint work with Ariana Chin, Aaron Kirtland, Vladyslav Nazarchuk, and Esther Plotnick.
The Polynomial Learning With Errors Problem and the Smearing Condition
Liljana Babinkostova, Boise State University
2022 AWM Research Symposium
Mathematics of Cryptography