| 講演名 | 2018-07-26 A New Embedding Method for Generalized LWE 王 偉尭(東大), 王 贇?(東大), 高安 敦(東大), 高木 剛(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Estimating the computational cost for solving learning with errors (LWE) problem is an indispensable research topic to use lattice-based cryptography in practice. For the purpose, the embedding approach is usually employed. The technique first constructs a basis matrix by embedding an LWE instance. At this stage, Kannan's and Bai-Galbraith's embedding is believed to be the most efficient approach for the standard and the binary LWE with secret vectors in Zn and {0,1}^n, respectively. Indeed, both methods work well with sufficiently many LWE samples. After the embedding phase, solving the unique SVP in the lattice spanned by the basis matrix results in solving LWE. Recently, to realize efficient implementations, there are several lattice-based schemes whose secret vectors have special distributions, e.g., small elements and/or sparse vectors. In this paper, to capture such settings and more, we study the LWE problem in a general setting. We analyze the LWE whose secret vectors are sampled from arbitrary distributions. Furthermore, we also study the problem when the number of samples is restricted. We believe that our work provides more general understanding on the hardness of LWE. Technically, we propose half-twisted embedding that contains the existing two embedding methods as special cases. The modification enables us to analyze in a generic manner and sometimes provides improved attacks. |
| キーワード(和) | |
| キーワード(英) | Post-quantum cryptographylattice-based cryptographylearning with errorsembedding techniqueshortest vector problem |
| 資料番号 | ISEC2018-46,SITE2018-38,HWS2018-43,ICSS2018-49,EMM2018-45 |
| 発行日 | 2018-07-18 (ISEC, SITE, HWS, ICSS, EMM) |
| 研究会情報 | |
| 研究会 | HWS / ISEC / SITE / ICSS / EMM / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| 開催期間 | 2018/7/25(から2日開催) |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 |
| テーマ（英） | Security, etc. |
| 委員長氏名（和） | 松本 勉(横浜国大) / 藤岡 淳(神奈川大) / 森住 哲也(神奈川大) / 白石 善明(神戸大) / 岩村 惠市(東京理科大) |
| 委員長氏名（英） | Tsutomu Matsumoto(Yokohama National Univ.) / Atsushi Fujioka(Kanagawa Univ.) / Tetsuya Morizumi(Kanagawa Univ.) / Yoshiaki Shiraishi(Kobe Univ.) / Keiichi Iwamura(TUC) |
| 副委員長氏名（和） | 川村 信一(東芝) / 池田 誠(東大) / 盛合 志帆(NICT) / 廣瀬 勝一(福井大) / 小川 賢(神戸学院大) / 大谷 卓史(吉備国際大) / 高倉 弘喜(NII) / 吉岡 克成(横浜国大) / 栗林 稔(岡山大) / 小嶋 徹也(東京高専) |
| 副委員長氏名（英） | Shinichi Kawamura(Toshiba) / Makoto Ikeda(Univ. of Tokyo) / Shiho Moriai(NICT) / Shoichi Hirose(Univ. of Fukui) / Masaru Ogawa(Kobe Gakuin Univ.) / Takushi Otani(Kibi International Univ.) / Hiroki Takakura(NII) / Katsunari Yoshioka(Yokohama National Univ.) / Minoru Kuribayashi(Okayama Univ.) / Tetsuya Kojima(NIT,Tokyo College) |
| 幹事氏名（和） | 三浦 典之(神戸大) / 国井 裕樹(セコム) / 大東 俊博(東海大) / 江村 恵太(NICT) / 川口 嘉奈子(東京藝術大) / 壁谷 彰慶(東洋英和女学院大) / 神谷 和憲(NTT) / 笠間 貴弘(NICT) / 姜 玄浩(東京高専) / 村田 晴美(中京大) |
| 幹事氏名（英） | Noriyuki Miura(Kobe Univ.) / Hiroki Kunii(SECOM) / Toshihiro Ohigashi(Tokai Univ.) / Keita Emura(NICT) / Kanako Kawaguchi(Tokyo Univ. of the Arts) / Akiyoshi Kabeya(Toyo Eiwa Univ.) / Kazunori Kamiya(NTT) / Takahiro Kasama(NICT) / Kan Hyonho(NIT, Tokyo) / Harumi Murata(Tyukyo Univ.) |
| 幹事補佐氏名（和） | / 面 和成(筑波大) / 須賀 祐治(インターネットイニシアティブ) / 加藤 尚徳(KDDI総合研究所) / 吉永 敦征(山口県立大) / 鈴木 大助(北陸大) / 山田 明(KDDI labs.) / 木藤 圭亮(三菱電機) / 秋山 寛子(長野高専) / 金田 北洋(キヤノン) |
| 幹事補佐氏名（英） | / Kazunari Omote(Tsukuba Univ.) / Yuuji Suga(IIJ) / Hisanori Kato(KDDI Research) / Nobuyuki Yoshinaga(Yamaguchi Pref Univ.) / Daisuke Suzuki(Hokuriku Univ.) / Akira Yamada(KDDI labs.) / Keisuke Kito(Mitsubishi Electric) / Hiroko Akiyama(National Institute of Technology, Nagano College) / キタヒロ カネダ(CANON) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Hardware Security / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Technical Committee on Enriched MultiMedia / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | A New Embedding Method for Generalized LWE |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / Post-quantum cryptographylattice-based cryptographylearning with errorsembedding techniqueshortest vector problem |
| 第 1 著者 氏名（和/英） | 王 偉尭 / Weiyao Wang |
| 第 1 著者 所属（和/英） | 東京大学(略称：東大) University of Tokyo(略称：Univ. Tokyo) |
| 第 2 著者 氏名（和/英） | 王 贇? / Yuntao Wang |
| 第 2 著者 所属（和/英） | 東京大学(略称：東大) University of Tokyo(略称：Univ. Tokyo) |
| 第 3 著者 氏名（和/英） | 高安 敦 / Atsushi Takayasu |
| 第 3 著者 所属（和/英） | 東京大学(略称：東大) University of Tokyo(略称：Univ. Tokyo) |
| 第 4 著者 氏名（和/英） | 高木 剛 / Tsuyoshi Takagi |
| 第 4 著者 所属（和/英） | 東京大学(略称：東大) University of Tokyo(略称：Univ. Tokyo) |
| 発表年月日 | 2018-07-26 |
| 資料番号 | ISEC2018-46,SITE2018-38,HWS2018-43,ICSS2018-49,EMM2018-45 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | ISEC-151,SITE-152,HWS-153,ICSS-154,EMM-155 |
| ページ範囲 | pp.363-370(ISEC), pp.363-370(SITE), pp.363-370(HWS), pp.363-370(ICSS), pp.363-370(EMM), |
| ページ数 | 8 |
| 発行日 | 2018-07-18 (ISEC, SITE, HWS, ICSS, EMM) |