On the Weakness of Non-Dual Ring-LWE Mod Prime Ideal q by Trace Map

Tomoka TAKAHASHI; Shinya OKUMURA; Atsuko MIYAJI

doi:10.1587/transinf.2022ICP0017

On the Weakness of Non-Dual Ring-LWE Mod Prime Ideal q by Trace Map

Tomoka TAKAHASHI, Shinya OKUMURA, Atsuko MIYAJI

Full Text Views

0

Cite this

Summary :

The recent decision by the National Institute of Standards and Technology (NIST) to standardize lattice-based cryptography has further increased the demand for security analysis. The Ring-Learning with Error (Ring-LWE) problem is a mathematical problem that constitutes such lattice cryptosystems. It has many algebraic properties because it is considered in the ring of integers, R, of a number field, K. These algebraic properties make the Ring-LWE based schemes efficient, although some of them are also used for attacks. When the modulus, q, is unramified in K, it is known that the Ring-LWE problem, to determine the secret information s ∈ R/qR, can be solved by determining s (mod q) ∈ F_q^f for all prime ideals q lying over q. The χ²-attack determines s (mod q) ∈F_q^f using chi-square tests over R/q ≅ F_q^f. The χ²-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ²-attack. In this paper, we extend the two-residue-degree χ²-attack to the attack that works efficiently for any residue degree. As a result, the attack time against a vulnerable field using our proposed attack with parameter (q,f)=(67, 3) was 129 seconds on a standard PC. We also evaluate the vulnerability of the two-power cyclotomic fields.

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.9 pp.1423-1434

Publication Date: 2023/09/01

Publicized: 2023/07/13

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022ICP0017

Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)

Category

Authors

Tomoka TAKAHASHI
  Osaka University
Shinya OKUMURA
  Osaka University
Atsuko MIYAJI
  Osaka University

Keyword

Ring-LWE, prime ideal, trace map, attack

Cite this

Copy

Tomoka TAKAHASHI, Shinya OKUMURA, Atsuko MIYAJI, "On the Weakness of Non-Dual Ring-LWE Mod Prime Ideal q by Trace Map" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 9, pp. 1423-1434, September 2023, doi: 10.1587/transinf.2022ICP0017.
Abstract: The recent decision by the National Institute of Standards and Technology (NIST) to standardize lattice-based cryptography has further increased the demand for security analysis. The Ring-Learning with Error (Ring-LWE) problem is a mathematical problem that constitutes such lattice cryptosystems. It has many algebraic properties because it is considered in the ring of integers, R, of a number field, K. These algebraic properties make the Ring-LWE based schemes efficient, although some of them are also used for attacks. When the modulus, q, is unramified in K, it is known that the Ring-LWE problem, to determine the secret information s ∈ R/qR, can be solved by determining s (mod q) ∈ F_q^f for all prime ideals q lying over q. The χ²-attack determines s (mod q) ∈F_q^f using chi-square tests over R/q ≅ F_q^f. The χ²-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ²-attack. In this paper, we extend the two-residue-degree χ²-attack to the attack that works efficiently for any residue degree. As a result, the attack time against a vulnerable field using our proposed attack with parameter (q,f)=(67, 3) was 129 seconds on a standard PC. We also evaluate the vulnerability of the two-power cyclotomic fields.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022ICP0017/_p

Copy

@ARTICLE{e106-d_9_1423,
author={Tomoka TAKAHASHI, Shinya OKUMURA, Atsuko MIYAJI, },
journal={IEICE TRANSACTIONS on Information},
title={On the Weakness of Non-Dual Ring-LWE Mod Prime Ideal q by Trace Map},
year={2023},
volume={E106-D},
number={9},
pages={1423-1434},
abstract={The recent decision by the National Institute of Standards and Technology (NIST) to standardize lattice-based cryptography has further increased the demand for security analysis. The Ring-Learning with Error (Ring-LWE) problem is a mathematical problem that constitutes such lattice cryptosystems. It has many algebraic properties because it is considered in the ring of integers, R, of a number field, K. These algebraic properties make the Ring-LWE based schemes efficient, although some of them are also used for attacks. When the modulus, q, is unramified in K, it is known that the Ring-LWE problem, to determine the secret information s ∈ R/qR, can be solved by determining s (mod q) ∈ F_q^f for all prime ideals q lying over q. The χ²-attack determines s (mod q) ∈F_q^f using chi-square tests over R/q ≅ F_q^f. The χ²-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ²-attack. In this paper, we extend the two-residue-degree χ²-attack to the attack that works efficiently for any residue degree. As a result, the attack time against a vulnerable field using our proposed attack with parameter (q,f)=(67, 3) was 129 seconds on a standard PC. We also evaluate the vulnerability of the two-power cyclotomic fields.},
keywords={},
doi={10.1587/transinf.2022ICP0017},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - On the Weakness of Non-Dual Ring-LWE Mod Prime Ideal q by Trace Map
T2 - IEICE TRANSACTIONS on Information
SP - 1423
EP - 1434
AU - Tomoka TAKAHASHI
AU - Shinya OKUMURA
AU - Atsuko MIYAJI
PY - 2023
DO - 10.1587/transinf.2022ICP0017
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2023
AB - The recent decision by the National Institute of Standards and Technology (NIST) to standardize lattice-based cryptography has further increased the demand for security analysis. The Ring-Learning with Error (Ring-LWE) problem is a mathematical problem that constitutes such lattice cryptosystems. It has many algebraic properties because it is considered in the ring of integers, R, of a number field, K. These algebraic properties make the Ring-LWE based schemes efficient, although some of them are also used for attacks. When the modulus, q, is unramified in K, it is known that the Ring-LWE problem, to determine the secret information s ∈ R/qR, can be solved by determining s (mod q) ∈ F_q^f for all prime ideals q lying over q. The χ²-attack determines s (mod q) ∈F_q^f using chi-square tests over R/q ≅ F_q^f. The χ²-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ²-attack. In this paper, we extend the two-residue-degree χ²-attack to the attack that works efficiently for any residue degree. As a result, the attack time against a vulnerable field using our proposed attack with parameter (q,f)=(67, 3) was 129 seconds on a standard PC. We also evaluate the vulnerability of the two-power cyclotomic fields.
ER -