Cryptanalysis of plwe based on zero-trace quadratic roots
Abstract
Abstract We extend two of the attacks on the PLWE problem presented by Elias, Lauter et al. to a ring R q = F q [ x ] / ( f ( x ) ) ${R}_{q}={\mathbb{F}}_{q}\left[x\right]/\left(f\left(x\right)\right)$ where the irreducible monic polynomial f ( x ) ∈ Z [ x ] $f\left(x\right)\in \mathbb{Z}\left[x\right]$ has an irreducible quadratic factor over F q [ x ] ${\mathbb{F}}_{q}\left[x\right]$ of the form x 2 + ρ with ρ of suitable multiplicative order in F q ${\mathbb{F}}_{q}$ . Our attack exploits the fact that the trace of the root is zero and has overwhelming success probability as a function of the number of samples taken as input. An implementation in Maple and some examples of our attack are also provided.
Fields of Study & Subjects
Coding theory and cryptography
Analytic Number Theory Research
Algebraic Geometry and Number Theory
Publication details
- Journal / source
- Journal of Mathematical Cryptology
- Publisher
- Walter de Gruyter GmbH
- Volume
- 20
- Issue
- 1
- Publication date
- 1 January 2026
- Language
- EN