| Presentation | 2022-03-10 Reconsideration of Attacks on the Search Ring-LWE Problem by Trace Map on Finite Field Tomoka Takahashi, Shinya Okumura, Atsuko Miyaji, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Lattice-based cryptography has attracted a great deal of attention due to the standardization of Post-Quantum Cryptography by NIST. The Ring-Learning with Error (Ring-LWE) problem is one of the mathematical problems in lattice-based cryptosystems. Chen et al. proposed an attack method by transforming the Ring-LWE problem over $R_q$ to a finite field problem $F_{q^f}$ and then performing statistical tests on $F_{q^f}$. On the other hand, a method to reduce the number of tests by applying cosets, and to reduce the number of samples required for the attack by performing the tests on $F_q$, was proposed separately for the cases where the residue degree $f$ is even, arbitrary, or composite. In this paper, we propose a more efficient attack method by applying the Homomorphism Theorem to the mappings embedded in the test space. Experimental results show that the decoding time can be reduced by up to $94.6%$. Further reduction in decoding time is expected when the residue degree and modulus parameters are large. We compare the scope of the attacks and the samples used by each attack. We also discuss the residue degree to which our attacks are particularly effective. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | post-quantum cryptograph / Ring-LWE / search attack / Trace Map / finite field |
| Paper # | IT2021-105,ISEC2021-70,WBS2021-73,RCC2021-80 |
| Date of Issue | 2022-03-03 (IT, ISEC, WBS, RCC) |
| Conference Information | |
| Committee | IT / ISEC / RCC / WBS |
|---|---|
| Conference Date | 2022/3/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Joint Meeting of ISEC, IT, RCC, and WBS |
| Chair | Tadashi Wadayama(Nagoya Inst. of Tech.) / Tetsuya Izu(Fujitsu Labs.) / HUAN-BANG LI(NICT) / Masanori Hamamura(Kochi Univ. of Tech.) |
| Vice Chair | Tetsuya Kojima(Tokyo Kosen) / Noboru Kunihiro(Tsukuba Univ.) / Goichiro Hanaoka(AIST) / Shunichi Azuma(Nagoya Univ.) / Koji Ishii(Kagawa Univ.) / Takashi Shono(INTEL) / Masahiro Fujii(Utsunomiya Univ.) |
| Secretary | Tetsuya Kojima(Saitamai Univ.) / Noboru Kunihiro(Yamaguchi Univ.) / Goichiro Hanaoka(Fujitsu Labs.) / Shunichi Azuma(Ibaraki Univ.) / Koji Ishii(CRIEPI) / Takashi Shono(Osaka Univ.) / Masahiro Fujii(National Defence Academy) |
| Assistant | Masanori Hirotomo(Saga Univ.) / Takahiro Matsuda(AIST) / SHAN LIN(NICT) / Masaki Ogura(Osaka Univ.) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Sun Ran(Ibaraki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Theory / Technical Committee on Information Security / Technical Committee on Reliable Communication and Control / Technical Committee on Wideband System |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reconsideration of Attacks on the Search Ring-LWE Problem by Trace Map on Finite Field |
| Sub Title (in English) | |
| Keyword(1) | post-quantum cryptograph |
| Keyword(2) | Ring-LWE |
| Keyword(3) | search attack |
| Keyword(4) | Trace Map |
| Keyword(5) | finite field |
| 1st Author's Name | Tomoka Takahashi |
| 1st Author's Affiliation | Osaka University(Osaka Univ.) |
| 2nd Author's Name | Shinya Okumura |
| 2nd Author's Affiliation | Osaka University(Osaka Univ.) |
| 3rd Author's Name | Atsuko Miyaji |
| 3rd Author's Affiliation | Osaka University(Osaka Univ.) |
| Date | 2022-03-10 |
| Paper # | IT2021-105,ISEC2021-70,WBS2021-73,RCC2021-80 |
| Volume (vol) | vol.121 |
| Number (no) | IT-428,ISEC-429,WBS-430,RCC-431 |
| Page | pp.pp.130-137(IT), pp.130-137(ISEC), pp.130-137(WBS), pp.130-137(RCC), |
| #Pages | 8 |
| Date of Issue | 2022-03-03 (IT, ISEC, WBS, RCC) |