| 講演名 | 2022-03-10 円分体の部分体上におけるRing-LWE問題に対する安全性解析 上杉 慧至(阪大), 奥村 伸也(阪大), 宮地 充子(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 量子計算機が提案されてから, 実用化に向けて着実に開発が進められている. 十分に大規模な量子計算機 の実用化時には, 現在利用されている RSA 暗号や楕円曲線暗号が解読できることが報告されている. そこで, 耐量子 安全な暗号の構築が提案されている. Ring-LWE 問題は多くの現代格子暗号の安全性を支えるが, 安全性の根拠が証 明されたというわけではない. Ring-LWE の安全性を確かめるために既存研究では，円分体上の Ring-LWE 問題や円 分体の部分体の 1 つである分解体上の Ring-LWE 問題が解析されているが, 未解析の Ring-LWE 問題は存在する. 本 研究では, 既存の Ring-LWE 問題とは異なる円分体の部分体上の Ring-LWE 問題に対して Progressive BKZ アルゴリ ズムを用いて格子攻撃を行い, 実験的に安全性を解析した. その結果，著しく成功確率が低くなる部分体が存在するこ とを確認した. |
| 抄録(英) | Since the proposal of the quantum computer, steady progress has been made toward its practical use. It has been reported that RSA cryptography and elliptic curve cryptography, which are currently used, can be broken when the sufficiently large quantum computer is put into practical use. Therefore, the construction of quantum-safe cryptosystems has been proposed. Although the Ring-LWE problem supports the security of many modern lattice cryptosystems, it has not been proven to be secure. In order to verify the security of Ring-LWE, existing studies have analyzed the Ring-LWE problem on cyclotomic fields and the Ring-LWE problem on decomposition fields of cyclotomic fields, but there are still unanalyzed Ring-LWE problems. In this study, we attack the Ring-LWE problem on some subfields of cyclotomic fields, which is different from the existing Ring-LWE problems, by using Progressive BKZ algorithm and experimentally analyze the security of the Ring-LWE problem. As a result of our experiments, we see that the success probability of the attack is significantly low for some subfields. |
| キーワード(和) | 格子暗号 / Ring-LWE / 円分体 / 格子基底簡約アルゴリズム |
| キーワード(英) | Lattice-based Cryptography / Ring-LWE / Cyclotomic Field / Lattice Basis Reduction Algorithm |
| 資料番号 | IT2021-106,ISEC2021-71,WBS2021-74,RCC2021-81 |
| 発行日 | 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 |
| タイトル（和） | 円分体の部分体上におけるRing-LWE問題に対する安全性解析 |
| サブタイトル（和） | |
| タイトル（英） | Crypto Analysis for Ring-LWE Problem on Subfield in Cyclotomic Field |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 格子暗号 / Lattice-based Cryptography |
| キーワード(2)（和/英） | Ring-LWE / Ring-LWE |
| キーワード(3)（和/英） | 円分体 / Cyclotomic Field |
| キーワード(4)（和/英） | 格子基底簡約アルゴリズム / Lattice Basis Reduction Algorithm |
| 第 1 著者 氏名（和/英） | 上杉 慧至 / Satoshi Uesugi |
| 第 1 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：OU) |
| 第 2 著者 氏名（和/英） | 奥村 伸也 / Shinya Okumura |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：OU) |
| 第 3 著者 氏名（和/英） | 宮地 充子 / Atsuko Miyaji |
| 第 3 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：OU) |
| 発表年月日 | 2022-03-10 |
| 資料番号 | IT2021-106,ISEC2021-71,WBS2021-74,RCC2021-81 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | IT-428,ISEC-429,WBS-430,RCC-431 |
| ページ範囲 | pp.138-144(IT), pp.138-144(ISEC), pp.138-144(WBS), pp.138-144(RCC), |
| ページ数 | 7 |
| 発行日 | 2022-03-03 (IT, ISEC, WBS, RCC) |