STNB2026 (39th edition)
Extension of root-based attacks against fully-split PLWE instances via isomorphisms
Presenters
Rodrigo Martín Sánchez-Ledesma
Abstract
In this talk, we present some results concerning the generalization of attacks on the Polynomial Learning With Errors problem that we provisionally offered in [1]. In these attacks, knowledge of a root of the generating polynomial of the polynomial ring over a certain (finite) base field is used to obtain algorithms that can solve, under certain conditions, the PLWE problem in its decision variant. Now our goal is to extend these attacks by constructing morphisms based on instances vulnerable to the attacks described above. Our results indicate that if the generating polynomial is totally factorizable over the base field, it is not possible to find new vulnerabilities.
To prove this, the key idea is to construct explicit isomorphisms between fully factorizable polynomials and show that such isomorphisms always distort the samples in such a way that the transformed samples cannot be used as an advantage for the decision-making attack. In other words, they do not allow us to distinguish whether such samples come from a PLWE-type distribution or from a purely uniform distribution, so that the attack is ineffective. Furthermore, we show that any isomorphism must be one of the explicitly constructed, thus showing that this approach cannot yield any new vulnerabilities, in a fully-split setting.
[1] I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma, A Generalized Approach to Root-based Attacks against PLWE, Cryptography and Communications (QuRCry). doi:10.1007/s12095-025-00849-9.
Files
No files available for download
