| 講演名 | 2016-07-15 省メモリデバイス上での効率的な離散ガウス分布の生成手法 太中 裕貴(NEC), 寺西 勇(NEC), 峯松 一彦(NEC), 青野 良範(NICT), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 格子暗号は, 行列演算によるシンプルな実装が可能である点と, 完全準同型暗号[Gentry09]の構成に代表される高機能性, 量子計算機に対する安全性への期待などから, 近年注目されている. cite{R}に代表される格子暗号は，鍵生成ないし暗号化時に離散ガウス分布からサンプリングした乱数を用いる. 従来のサンプリング方法としては棄却サンプル法, 累積分布を用いた逆関数形式, Knuth-Yao法が存在する. しかしながら, センサなど計算資源が限られたデバイス上で格子暗号を動作させる場合に, 従来サンプリング法の計算時間ないし使用メモリ量が問題と考えられる. 本論文では, 上記の問題を解決する新たな離散ガウス分布のサンプリング方法を提案する. 提案方法は累積分布関数の効率的な近似計算に基づいており, 特に分散値の大きい離散ガウス分布について使用メモリ量と計算時間の双方で効率の良いサンプリングが可能となる. たとえば, 標準偏差が$128$の時, $16$kbitメモリを使用し, 支配的な計算回数が棄却サンプリング法では平均$10回から20回$であるのに対し, 提案方法では, $98$％以上の確率で, $2回から6回$でサンプリングすることができる. |
| 抄録(英) | Lattice-based cryptography has been attracted by features of simple-implementation, quantum-resilient, and high-level functional application such as the fully homomorphic encryption [Gentry09]. Several lattice-based cryptographies use the discrete gaussian sampler in its encryption and signature. The folklore methods for sampling from such distributions are the rejection sampling, the inverse cumulative density function method, and the Knuth-Yao's method, which are not specialized for the discrete gaussian. From the viewpoint of computational cost and space complexity, they are not suitable for implementing in constrained devices such as IoT sensors. In this paper, we propose a new sampling algorithm which is effective in time and space. For example, when the standard derivation is 128, our sampler can generate a discrete gaussian in 7 unit times in average while the standard rejection sampler takes 10 to 20 unit times. Here, the unit time is the complexity to compute the gaussian function $e^{-ax^2}$ within a sufficient accuracy. |
| キーワード(和) | 離散ガウス分布 / 格子暗号 |
| キーワード(英) | Discrete Gaussian distribution / Lattice-based cryptography |
| 資料番号 | ISEC2016-32,SITE2016-26,ICSS2016-32,EMM2016-40 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |
| 研究会情報 | |
| 研究会 | EMM / ISEC / SITE / ICSS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| 開催期間 | 2016/7/14(から2日開催) |
| 開催地（和） | 中市コミュニティーホール Nac |
| 開催地（英） | |
| テーマ（和） | セキュリティ，一般 |
| テーマ（英） | security, etc |
| 委員長氏名（和） | 伊藤 彰則(東北大) / 満保 雅浩(金沢大) / 岡田 仁志(NII) / 三宅 優(KDDI研) |
| 委員長氏名（英） | Akinori Ito(Tohoku Univ.) / Masahiro Mambo(Kanazawa Univ.) / Hitoshi Okada(NII) / Yutaka Miyake(KDDI R&D Labs.) |
| 副委員長氏名（和） | 川村 正樹(山口大) / 日置 尋久(京大) / 小川 一人(NHK) / 藤岡 淳(神奈川大) / 森住 哲也(神奈川大) / 小川 賢(神戸学院大) / 白石 善明(神戸大) / 植田 武(三菱電機) |
| 副委員長氏名（英） | Masaki Kawamura(Yamaguchi Univ.) / Hirohisa Hioki(Kyoto Univ.) / Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) / Yoshiaki Shiraishi(Kobe Univ.) / Takeshi Ueda(Mitsubishi Electric) |
| 幹事氏名（和） | 薗田 光太郎(長崎大) / 岩田 基(阪府大) / 駒野 雄一(東芝) / 水木 敬明(東北大) / 多川 孝央(九大) / 芳賀 高洋(岐阜聖徳学園大) / 高倉 弘喜(NII) / 吉岡 克成(横浜国大) |
| 幹事氏名（英） | Kotaro Sonoda(Nagasaki Univ.) / Motoi Iwata(Osaka Pref. Univ.) / Yuichi Komano(Toshiba) / Takaaki Mizuki(Tohoku Univ.) / Takahiro Tagawa(Kyushu Univ.) / Takahiro Haga(Gifu Shotoku Gakuen Univ.) / Hiroki Takakura(NII) / Katsunari Yoshioka(Yokohama National Univ.) |
| 幹事補佐氏名（和） | 生源寺 類(静岡大) / 藤吉 正明(首都大東京) / 大東 俊博(東海大) / 須賀 祐治(インターネットイニシアティブ) / 猪俣 敦夫(東京電機大) / 川口 嘉奈子(東京藝術大) / 神谷 和憲(NTT) / 笠間 貴弘(NICT) |
| 幹事補佐氏名（英） | Rui Shogenji(Shizuoka Univ.) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Kanako Kawaguchi(Tokyo Univ. of the Arts) / Kazunori Kamiya(NTT) / Takahiro Kasama(NICT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 省メモリデバイス上での効率的な離散ガウス分布の生成手法 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Discrete Gaussian Sampling on Constrained Devices |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 離散ガウス分布 / Discrete Gaussian distribution |
| キーワード(2)（和/英） | 格子暗号 / Lattice-based cryptography |
| 第 1 著者 氏名（和/英） | 太中 裕貴 / Yuki Tanaka |
| 第 1 著者 所属（和/英） | 日本電気株式会社(略称：NEC) NEC Corporation(略称：NEC) |
| 第 2 著者 氏名（和/英） | 寺西 勇 / Isamu Teranishi |
| 第 2 著者 所属（和/英） | 日本電気株式会社(略称：NEC) NEC Corporation(略称：NEC) |
| 第 3 著者 氏名（和/英） | 峯松 一彦 / Kazuhiko Minematsu |
| 第 3 著者 所属（和/英） | 日本電気株式会社(略称：NEC) NEC Corporation(略称：NEC) |
| 第 4 著者 氏名（和/英） | 青野 良範 / Yoshinori Aono |
| 第 4 著者 所属（和/英） | 情報通信研究機構(略称：NICT) National Institute of Information and Communications Technology(略称：NICT) |
| 発表年月日 | 2016-07-15 |
| 資料番号 | ISEC2016-32,SITE2016-26,ICSS2016-32,EMM2016-40 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | ISEC-129,SITE-130,ICSS-131,EMM-132 |
| ページ範囲 | pp.169-175(ISEC), pp.169-175(SITE), pp.169-175(ICSS), pp.169-175(EMM), |
| ページ数 | 7 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |