| 講演名 | 2022-03-10 有限体上のトレース写像を用いたSearch Ring-LWE問題への攻撃の再考 高橋 朋伽(阪大), 奥村 伸也(阪大), 宮地 充子(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | NISTによる耐量子計算機暗号の標準化により，格子暗号は脚光を浴びている．Ring-Learning with Error（Ring-LWE）問題は格子暗号を構成する数学問題の１つである．Chen らは整数環$R_q$上のRing-LWE問題を有限体$F_{q^f}$上の問題へ変換し，有限体$F_{q^f}$上の統計的検定による攻撃手法を提案した．これに対し，剰余類の適用により検定回数を，さらに素体$F_q$上で検定を行うことで攻撃に必要なサンプル数を削減する手法が，相対次数$f$が偶数・任意・合成数の場合に分けて提案された．本投稿では検定空間に埋め込む写像に対し準同型定理を適応することにより，さらに効率化した攻撃手法を提案する．実験の結果，最大で$94.6%$の解読時間の削減が確認された．相対次数・モジュラスパラメータ—が大きい場合はさらなる解読時間の削減が見込まれる．さらに各手法の攻撃対象範囲と利用するサンプルの比較，攻撃が特に有効な相対次数についても考察を行う． |
| 抄録(英) | 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. |
| キーワード(和) | 耐量子暗号 / Ring-LWE / 探索攻撃 / トレース写像 / 有限体 |
| キーワード(英) | post-quantum cryptograph / Ring-LWE / search attack / Trace Map / finite field |
| 資料番号 | IT2021-105,ISEC2021-70,WBS2021-73,RCC2021-80 |
| 発行日 | 2022-03-03 (IT, ISEC, WBS, RCC) |
| 研究会情報 | |
| 研究会 | IT / ISEC / RCC / WBS |
|---|---|
| 開催期間 | 2022/3/10(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | ISEC・IT・RCC・WBS合同研究会 |
| テーマ（英） | Joint Meeting of ISEC, IT, RCC, and WBS |
| 委員長氏名（和） | 和田山 正(名工大) / 伊豆 哲也(富士通研) / 李 還幇(NICT) / 浜村 昌則(高知工科大) |
| 委員長氏名（英） | Tadashi Wadayama(Nagoya Inst. of Tech.) / Tetsuya Izu(Fujitsu Labs.) / HUAN-BANG LI(NICT) / Masanori Hamamura(Kochi Univ. of Tech.) |
| 副委員長氏名（和） | 小嶋 徹也(東京高専) / 國廣 昇(筑波大学) / 花岡 悟一郎(産総研) / 東 俊一(名大) / 石井 光治(香川大) / 庄納 崇(インテル) / 藤井 雅弘(宇都宮大) |
| 副委員長氏名（英） | 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.) |
| 幹事氏名（和） | 松田 哲直(埼玉大) / 野崎 隆之(山口大) / 山本 大(富士通研) / 米山 一樹(茨城大) / 加川 敏規(電中研) / 林 直樹(阪大) / 中村 僚兵(防衛大) / 小室 信喜(千葉大) |
| 幹事氏名（英） | Tetsunao Matsuta(Saitamai Univ.) / Takayuki Nozaki(Yamaguchi Univ.) / Dai Yamamoto(Fujitsu Labs.) / Kazuki Yoneyama(Ibaraki Univ.) / Toshinori Kagawa(CRIEPI) / Naoki Hayashi(Osaka Univ.) / Ryohei Nakamura(National Defence Academy) / Nobuyoshi Komuro(Chiba Univ.) |
| 幹事補佐氏名（和） | 廣友 雅徳(佐賀大) / 松田 隆宏(産総研) / 単 麟(NICT) / 小蔵 正輝(阪大) / 木下 雅之(千葉工大) / 孫 冉(茨城大) |
| 幹事補佐氏名（英） | Masanori Hirotomo(Saga Univ.) / Takahiro Matsuda(AIST) / SHAN LIN(NICT) / Masaki Ogura(Osaka Univ.) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Sun Ran(Ibaraki Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Theory / Technical Committee on Information Security / Technical Committee on Reliable Communication and Control / Technical Committee on Wideband System |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 有限体上のトレース写像を用いたSearch Ring-LWE問題への攻撃の再考 |
| サブタイトル（和） | |
| タイトル（英） | Reconsideration of Attacks on the Search Ring-LWE Problem by Trace Map on Finite Field |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 耐量子暗号 / post-quantum cryptograph |
| キーワード(2)（和/英） | Ring-LWE / Ring-LWE |
| キーワード(3)（和/英） | 探索攻撃 / search attack |
| キーワード(4)（和/英） | トレース写像 / Trace Map |
| キーワード(5)（和/英） | 有限体 / finite field |
| 第 1 著者 氏名（和/英） | 高橋 朋伽 / Tomoka Takahashi |
| 第 1 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 2 著者 氏名（和/英） | 奥村 伸也 / Shinya Okumura |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 3 著者 氏名（和/英） | 宮地 充子 / Atsuko Miyaji |
| 第 3 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 発表年月日 | 2022-03-10 |
| 資料番号 | IT2021-105,ISEC2021-70,WBS2021-73,RCC2021-80 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | IT-428,ISEC-429,WBS-430,RCC-431 |
| ページ範囲 | pp.130-137(IT), pp.130-137(ISEC), pp.130-137(WBS), pp.130-137(RCC), |
| ページ数 | 8 |
| 発行日 | 2022-03-03 (IT, ISEC, WBS, RCC) |