| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-07-15 13:00 省メモリデバイス上での効率的な離散ガウス分布の生成手法 ○太中裕貴・寺西 勇・峯松一彦（NEC）・青野良範（NICT）  ISEC2016-32 SITE2016-26 ICSS2016-32 EMM2016-40 |
|
| 抄録 | （和） | 格子暗号は, 行列演算によるシンプルな実装が可能である点と, 完全準同型暗号[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 / / / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 129, ISEC2016-32, pp. 169-175, 2016年7月. | |
| 資料番号 | ISEC2016-32 | |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2016-32 SITE2016-26 ICSS2016-32 EMM2016-40 |
|
| 研究会情報 | |
| 研究会 | EMM ISEC SITE ICSS IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2016-07-14 - 2016-07-15 |
| 開催地（和） | 中市コミュニティーホール Nac |
| 開催地（英） | |
| テーマ（和） | セキュリティ，一般 |
| テーマ（英） | security, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2016-07-EMM-ISEC-SITE-ICSS-CSEC-SPT |
| 本文の言語 | 日本語 |
| タイトル（和） | 省メモリデバイス上での効率的な離散ガウス分布の生成手法 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Discrete Gaussian Sampling on Constrained Devices |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 離散ガウス分布 / Discrete Gaussian distribution |
| キーワード(2)（和/英） | 格子暗号 / Lattice-based cryptography |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-07-15 13:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2016-32, SITE2016-26, ICSS2016-32, EMM2016-40 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.129(ISEC), no.130(SITE), no.131(ICSS), no.132(EMM) |
| ページ範囲 | pp.169-175 |
| ページ数 | 7 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]