The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
La récente décision du National Institute of Standards and Technology (NIST) de normaliser la cryptographie basée sur le réseau a encore accru la demande d'analyse de sécurité. Le problème Ring-Learning with Error (Ring-LWE) est un problème mathématique qui constitue de tels cryptosystèmes en réseau. Il possède de nombreuses propriétés algébriques car il est considéré dans l'anneau des entiers, R, d'un champ numérique, K. Ces propriétés algébriques rendent les schémas basés sur Ring-LWE efficaces, bien que certains d'entre eux soient également utilisés pour des attaques. Lorsque le module, q, n'est pas ramifié dans K, on sait que le problème Ring-LWE, pour déterminer les informations secrètes s ∈ R/qR, peut être résolu en déterminant s (mod q) ∈ Fqf pour tous les idéaux premiers q qui recouvrent q. Le χ2-l'attaque détermine s (mod q) ∈Fqf en utilisant des tests du chi carré sur R/q ≅ Fqf. Le χ2-l'attaque est améliorée dans le cas particulier où le degré de résidu f est deux, ce qui est appelé degré à deux résidus χ2-attaque. Dans cet article, nous étendons le degré χ à deux résidus2-Attaque à l'attaque qui fonctionne efficacement pour n'importe quel degré de résidu. En conséquence, le temps d'attaque contre un champ vulnérable en utilisant notre attaque proposée avec le paramètre (q,f)=(67, 3) durait 129 secondes sur un PC standard. Nous évaluons également la vulnérabilité des champs cyclotomiques à deux puissances.
Tomoka TAKAHASHI
Osaka University
Shinya OKUMURA
Osaka University
Atsuko MIYAJI
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
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) ∈ Fqf for all prime ideals q lying over q. The χ2-attack determines s (mod q) ∈Fqf using chi-square tests over R/q ≅ Fqf. The χ2-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ2-attack. In this paper, we extend the two-residue-degree χ2-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
Copier
@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) ∈ Fqf for all prime ideals q lying over q. The χ2-attack determines s (mod q) ∈Fqf using chi-square tests over R/q ≅ Fqf. The χ2-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ2-attack. In this paper, we extend the two-residue-degree χ2-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},}
Copier
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) ∈ Fqf for all prime ideals q lying over q. The χ2-attack determines s (mod q) ∈Fqf using chi-square tests over R/q ≅ Fqf. The χ2-attack is improved in the special case where the residue degree f is two, which is called the two-residue-degree χ2-attack. In this paper, we extend the two-residue-degree χ2-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 -