省メモリデバイス上での効率的な離散ガウス分布の生成手法

• Item type: SIG Technical Reports(1)
• 公開日: 2016-07-07
• タイトル: 省メモリデバイス上での効率的な離散ガウス分布の生成手法
• タイトル / 言語: en
• タイトル: Efficient Discrete Gaussian Sampling on Constrained Devices
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電気株式会社
• 著者所属: 日本電気株式会社
• 著者所属: 日本電気株式会社
• 著者所属: 情報通信研究機構
• 著者所属(英): en
• 著者所属(英): NEC Corporation
• 著者所属(英): en
• 著者所属(英): NEC Corporation
• 著者所属(英): en
• 著者所属(英): NEC Corporation
• 著者所属(英): en
• 著者所属(英): NICT
• 著者名: 太中, 裕貴; 寺西, 勇; 峯松, 一彦; 青野, 良範
• 著者名(英): Yuki, Tanaka; Isamu, Teranishi; Kazuhiko, Minematsu; Yoshinori, Aono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 格子暗号は，行列演算によるシンプルな実装が可能である点と，完全準同型暗号 [4] の構成に代表される高機能性，量子計算機に対する安全性への期待などから，近年注目されている．[9] に代表される格子暗号は，鍵生成ないし暗号化時に離散ガウス分布からサンプリングした乱数を用いる．従来のサンプリング方法としては棄却サンプル法，累積分布を用いた逆関数形式，Knuth-Yao 法が存在する．しかしながら，センサなど計算資源が限られたデバイス上で格子暗号を動作させる場合に，従来サンプリング法の計算時間ないし使用メモリ量が問題と考えられる．本論文では，上記の問題を解決する新たな離散ガウス分布のサンプリング方法を提案する．提案方法は累積分布関数の効率的な近似計算に基づいており，特に分散値の大きい離散ガウス分布について使用メモリ量と計算時間の双方で効率の良いサンプリングが可能となる．たとえば，標準偏差が 128 の時，16kbit のメモリを使用することで，支配的な計算回数が棄却サンプリング法では平均 10 回から 20 回であるのに対し，提案方法では，98％以上の確率で，2 回から 6 回でサンプリングすることができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Lattice-based cryptography has been attracted by features of simple-implementation, quantum-resilient, and high-level functional application such as the fully homomorphic encryption [4]. 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. Prom 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-ax2 within a sufficient accuracy.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2016-CSEC-74, 号 27, p. 1-7, 発行日 2016-07-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会