| Presentation | 2021-03-04 An Attack on Search Ring-LWE Problem for Even Relative Degree Yasuhisa Okumura, Shinya Okumura, Atsuko Miyaji, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Ring-LWE problem is used to construct homomorphic encryption and has attracted much attention because of its quantum security. Chen et al. proposed a search attack by converting the Ring-LWE problem on the ring of integers of an algebraic number field into a problem on a small finite field, which reduces the search range. They also improved the attack in the case where the relative degree of the modulus prime in the algebraic field is 2. Okumura et al. extend Chen et al.'s improvement to the case where the relative degree is even, and propose a efficient decision attack using trace map and appropriate sample selection. In this paper, we propose an extension of the decision attack proposed by Okumura et al. to a search attack. We also propose a more efficient search attack using coefficients under different conditions. Furthermore, we attack the extension of the cyclotomic field, which is vulnerable to these attacks. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Ring-LWE / attack |
| Paper # | IT2020-122,ISEC2020-52,WBS2020-41 |
| Date of Issue | 2021-02-25 (IT, ISEC, WBS) |
| Conference Information | |
| Committee | WBS / IT / ISEC |
|---|---|
| Conference Date | 2021/3/4(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Joint Meeting of WBS, IT, and ISEC |
| Chair | Masanori Hamamura(Kochi Univ. of Tech.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Shoichi Hirose(Univ. of Fukui) |
| Vice Chair | Takashi Shono(INTEL) / Masahiro Fujii(Utsunomiya Univ.) / Tetsuya Kojima(Tokyo Kosen) / Tetsuya Izu(Fujitsu Labs.) / Noboru Kunihiro(Tsukuba Univ.) |
| Secretary | Takashi Shono(Okayama Univ. of Science) / Masahiro Fujii(National Defence Academy) / Tetsuya Kojima(Yamaguchi Univ.) / Tetsuya Izu(Saga Univ.) / Noboru Kunihiro(Tsukuba Univ.) |
| Assistant | Duong Quang Thang(NAIST) / Masafumi Moriyama(NICT) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Takahiro Ohta(Senshu Univ.) / Kazuki Yoneyama(Ibaraki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Wideband System / Technical Committee on Information Theory / Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Attack on Search Ring-LWE Problem for Even Relative Degree |
| Sub Title (in English) | |
| Keyword(1) | Ring-LWE |
| Keyword(2) | attack |
| 1st Author's Name | Yasuhisa Okumura |
| 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 | 2021-03-04 |
| Paper # | IT2020-122,ISEC2020-52,WBS2020-41 |
| Volume (vol) | vol.120 |
| Number (no) | IT-410,ISEC-411,WBS-412 |
| Page | pp.pp.66-72(IT), pp.66-72(ISEC), pp.66-72(WBS), |
| #Pages | 7 |
| Date of Issue | 2021-02-25 (IT, ISEC, WBS) |