Trace-based cryptanalysis of cyclotomic \(R_{q,0}\times R_q\)-PLWE for the non-split case

We describe a decisional attack against a version of the PLWE problem in which the samples are taken from a certain proper subring of large dimension of the cyclotomic ring \(\mathbb{F}_q[x]/(\Phi_{p^k}(x))\) with \(k>1\) in the case where \(q\equiv 1\pmod{p}\) but \(\Phi_{p^k}(x)\) is not totall...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-07
Main Authors: Blanco-Chacón, Iván, Durán-Díaz, Raúl, Rahinatou Yuh Njah Nchiwo, Barbero-Lucas, Beatriz
Format: Article
Language:English
Subjects:
Cryptography
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a decisional attack against a version of the PLWE problem in which the samples are taken from a certain proper subring of large dimension of the cyclotomic ring \(\mathbb{F}_q[x]/(\Phi_{p^k}(x))\) with \(k>1\) in the case where \(q\equiv 1\pmod{p}\) but \(\Phi_{p^k}(x)\) is not totally split over \(\mathbb{F}_q\). Our attack uses the fact that the roots of \(\Phi_{p^k}(x)\) over suitable extensions of \(\mathbb{F}_q\) have zero-trace and has overwhelming success probability as a function of the number of input samples. An implementation in Maple and some examples of our attack are also provided.
ISSN:2331-8422
DOI:10.48550/arxiv.2209.11962