Trace-based cryptanalysis of cyclotomic Rq,0 × Rq-PLWE for the non-split case

Iván Blanco-Chacón; Raúl Durán-Díaz; Rahinatou Yuh Njah Nchiwo; Beatriz Barbero-Lucas

doi:10.46298/cm.11153

Trace-based cryptanalysis of cyclotomic R_q,0 × R_q-PLWE for the non-split case

Iván Blanco-Chacón, Raúl Durán-Díaz, Rahinatou Yuh Njah Nchiwo, Beatriz Barbero-Lucas

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

55 Downloads (Pure)

Abstract

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 F_q [x]/(Φ_pk (x)) with k > 1 in the case where q ≡ 1 (mod p) but Φ_pk (x) is not totally split over F_q. Our attack uses the fact that the roots of Φ_pk (x) over suitable extensions of 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.

Original language	English
Pages (from-to)	115-135
Number of pages	21
Journal	Communications in Mathematics
Volume	31
Issue number	2
DOIs	https://doi.org/10.46298/cm.11153
Publication status	Published - 2023
MoE publication type	A1 Journal article-refereed

Keywords

Lattice-based
Polynomial Learning With Errors
Ring Learning With Errors

Access to Document

10.46298/cm.11153Licence: CC BY-SA

SCI_Blanco-Chacon_etal_Communications_in_Mathematics_2023Final published version, 404 KBLicence: CC BY-SA

Cite this

@article{622d13d2a8194a88876fcc1eff68b9db,

title = "Trace-based cryptanalysis of cyclotomic Rq,0 × Rq-PLWE for the non-split case",

abstract = "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 Fq [x]/(Φpk (x)) with k > 1 in the case where q ≡ 1 (mod p) but Φpk (x) is not totally split over Fq. Our attack uses the fact that the roots of Φpk (x) over suitable extensions of Fq 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.",

keywords = "Lattice-based, Polynomial Learning With Errors, Ring Learning With Errors",

author = "Iv{\'a}n Blanco-Chac{\'o}n and Ra{\'u}l Dur{\'a}n-D{\'i}az and Nchiwo, {Rahinatou Yuh Njah} and Beatriz Barbero-Lucas",

note = "Funding Information: I. Blanco-Chac{\'o}n is partially supported by the Spanish National Research Plan, grant no MTM2016-79400-P, by grant PID2019-104855RBI00, funded by MCIN / AEI / 10.13039 / 501100011033 and by the University of Alcal{\'a} grant CCG20/IA-057. R. Dur{\'a}n-D{\'i}az is partially supported by grant P2QProMeTe (PID2020-112586RB-I00), funded by MCIN / AEI / 10.13039 / 501100011033. R.Y. Njah Nchiwo is supported by a PhD scholarship from the Magnus Ehrnrooth Foundation, Finland, in part by Academy of Finland, grant 351271 (PI: C. Hollanti) and in part by MATINE Finnish Ministry of Defence, grant #2500M-0147 (PI: C. Hollanti). B. Barbero-Lucas is partially supported by the University of Alcal{\'a} grant CCG20/IA-057. Publisher Copyright: {\textcopyright} 2023 Iv{\'a}n Blanco-Chac{\'o}n, Ra{\'u}l Dur{\'a}n-D{\'i}az, Rahinatou Yuh Njah Nchiwo and Beatriz Barbero-Lucas.",

year = "2023",

doi = "10.46298/cm.11153",

language = "English",

volume = "31",

pages = "115--135",

journal = "Communications in Mathematics",

issn = "1804-1388",

publisher = "University of Ostrava",

number = "2",

}

TY - JOUR

T1 - Trace-based cryptanalysis of cyclotomic Rq,0 × Rq-PLWE for the non-split case

AU - Blanco-Chacón, Iván

AU - Durán-Díaz, Raúl

AU - Nchiwo, Rahinatou Yuh Njah

AU - Barbero-Lucas, Beatriz

N1 - Funding Information: I. Blanco-Chacón is partially supported by the Spanish National Research Plan, grant no MTM2016-79400-P, by grant PID2019-104855RBI00, funded by MCIN / AEI / 10.13039 / 501100011033 and by the University of Alcalá grant CCG20/IA-057. R. Durán-Díaz is partially supported by grant P2QProMeTe (PID2020-112586RB-I00), funded by MCIN / AEI / 10.13039 / 501100011033. R.Y. Njah Nchiwo is supported by a PhD scholarship from the Magnus Ehrnrooth Foundation, Finland, in part by Academy of Finland, grant 351271 (PI: C. Hollanti) and in part by MATINE Finnish Ministry of Defence, grant #2500M-0147 (PI: C. Hollanti). B. Barbero-Lucas is partially supported by the University of Alcalá grant CCG20/IA-057. Publisher Copyright: © 2023 Iván Blanco-Chacón, Raúl Durán-Díaz, Rahinatou Yuh Njah Nchiwo and Beatriz Barbero-Lucas.

PY - 2023

Y1 - 2023

N2 - 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 Fq [x]/(Φpk (x)) with k > 1 in the case where q ≡ 1 (mod p) but Φpk (x) is not totally split over Fq. Our attack uses the fact that the roots of Φpk (x) over suitable extensions of Fq 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.

AB - 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 Fq [x]/(Φpk (x)) with k > 1 in the case where q ≡ 1 (mod p) but Φpk (x) is not totally split over Fq. Our attack uses the fact that the roots of Φpk (x) over suitable extensions of Fq 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.

KW - Lattice-based

KW - Polynomial Learning With Errors

KW - Ring Learning With Errors

UR - http://www.scopus.com/inward/record.url?scp=85166507129&partnerID=8YFLogxK

U2 - 10.46298/cm.11153

DO - 10.46298/cm.11153

M3 - Article

AN - SCOPUS:85166507129

SN - 1804-1388

VL - 31

SP - 115

EP - 135

JO - Communications in Mathematics

JF - Communications in Mathematics

IS - 2

ER -

Trace-based cryptanalysis of cyclotomic R_q,0 × R_q-PLWE for the non-split case

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Hollanti NT: Number-theoretic well-rounded lattices

MATINE_Hollanti_2022-2023: Kvanttiturvallisten hilasalausmenetelmien analyysi ja verifiointi

Cite this

Trace-based cryptanalysis of cyclotomic Rq,0 × Rq-PLWE for the non-split case

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Hollanti NT: Number-theoretic well-rounded lattices

MATINE_Hollanti_2022-2023: Kvanttiturvallisten hilasalausmenetelmien analyysi ja verifiointi

Cite this

Trace-based cryptanalysis of cyclotomic R_q,0 × R_q-PLWE for the non-split case