The Polynomial Learning With Errors problem (PLWE) serves as the background of two of the four cryptosystems standardised in July 2022 by the National Institute of Standards and Technology to replace non-quantum resistant current primitives like those based on RSA, finite field based Diffie-Hellman and its elliptic curve analogue. Although PLWE is highly believed to be quantum resistant, unlike other post-quantum proposals like multivariate and some code based ones, this fact has not yet been established. Moreover, several vulnerabilities have been encountered for a number of specific instances. In a search for more flexibility, it becomes fully relevant to study the robustness of PLWE based on other polynomials, not necessarily cyclotomic. In 2015, Lauter et al. found a good number of attacks based on different features of the roots of the polynomial. In the present talk we present an overview of the approximations made against PLWE derived from these work, along with several new attacks which refine those by Lauter exploiting the order of the trace of roots over finite extensions of the finite field under the three scenarios laid out by Lauter et al, allowing to generalize the setting in which the attacks can be carried out. This is joint work with I. Blanco-Chacón and R. Durán.
In the last decade, Locally Recoverable Codes (LRC) have been a critical topic in communication and distributed storage. In addition to the minimum distance, dimension and length of a code, LRCs also consider the locality parameter, i.e. the minimum number of entries needed to recover a given entry for any codeword. The parameters of LRCs are subject to a general Singleton bound and codes achieving the bound are called optimal LRCs. Constructions are known when the underlying field size of the code is larger than the length of the code. However, still little is known about the existence of optimal LRCs over small underlying field sizes. In this talk, I will show how we established new bounds that depend on locality and the field size of code using a duality theory of LRCs and the combinatorial structure of the code. This talk is based on joint work with A. Gruica and A. Ravagnani.
Page content by: webmaster-math [at] list [dot] aalto [dot] fi