九州大学学術情報リポジトリ
Kyushu University Institutional Repository
Efficient Implementation and Performance
Evaluation of Lattice/based Cryptography over Memory/Constrained Environments
袁, ヤ
https://doi.org/10.15017/4060003
出版情報：九州大学, 2019, 博士（機能数理学）, 課程博士 バージョン：
権利関係：
（様式６－２）
氏 名 袁 ヤ
論 文 名 Efficient Implementation and Performance Evaluation of Lattice-based Cryptography over Memory-Constrained Environments (格子暗号方式のメモリ制限下での効率的な実装法および性能評価) 論文調査委員 主査 東京大学 教 授 高木 剛
副査 九州大学 教授 溝口佳寛 副査 九州大学 准教授 安田 雅哉
副査 日立製作所 研究開発グループ 主任研究員 佐藤 尚宜
論 文 審 査 の 結 果 の 要 旨
本博士論文では、格子暗号で利用される多項式環の効率的な演算法および乱数の高速な生成法に 関して考察している。現在普及している RSA 暗号や楕円曲線暗号の安全性は素因数分解や離散対数 問題の困難性を根拠にしているが、Shor の量子アルゴリズムにより多項式時間で解読されることが 知られている。そのため、量子コンピュータによる解読に耐性があると考えられる数学問題を基に した耐量子計算機暗号(Post-Quantum Cryptography: PQC)の研究が進められている。PQC の代表的 な暗号方式として、格子上の最短ベクトル問題(SVP)の困難性に基づく格子暗号が知られている。
米国標準技術研究所 NIST が 2016 年から推進している PQC の標準化プロジェクトにおいても格子暗 号は代表的な方式となる。
格子暗号を実社会で利用するためには、暗号方式を実装するディバイスに向けて暗号アルゴリズム の処理量を効率化する必要がある。特に、暗号方式は IC カードなどの IoT 機器で実装されることもあ り、メモリが制限された計算環境において効率的な実装法が求められる。格子暗号における主要な演 算処理としては、整数剰余環 Z/qZ 上の多項式剰余環 Z/qZ[x]/(f(x))における演算および離散ガウス分 布による乱数の生成がある。格子暗号が安全となるパラメータでは、数百次以上の剰余多項式 f(x)に よる多項式剰余環が利用されるため、大きな次数の多項式に対する高速な演算アルゴリズムが必要と なる。通常の n 次多項式の乗算では O(n2)の計算量を必要とするが、数論変換(Number Theoretic Transform: NTT)において、剰余多項式として円分多項式を選択した場合、乗算が O(n log n)の計算量 で計算可能となる。また、整数剰余環における高速な乗算法として、Montgomery アルゴリズムがある。
一方、離散ガウス分布による乱数生成法は多くのアルゴリズムが提案されており、Knuth-Yao アルゴリ ズムが効率的な実装に利用されている。
本論文においては、メモリが制限された計算環境として、暗号コプロセッサを搭載しない Java Card，
JavaScript が実行可能な IoT プラットフォーム、電力送電網で利用される Raspberry Pi において、格 子暗号を高速実装し性能評価を行った。はじめに、Java Card の実装で用いた標準規格 Platform Specification 2.2.2 では、RAM サイズが高々10 Kbytes であり、利用できる整数型は boolean, byte, short のみとなる。このようなメモリが制限された計算環境において、国際会議 Eurocrypt 2010 で提 案された格子暗号となる LPR—LWE 方式の実装を行った。128 ビットの安全性を持つ LPR-LWE 方式のパラ メータとして、整数剰余環 Z/qZ は q=7681、多項式剰余環の剰余多項式 xn+1 の次数は n=256、離散ガウ ス分布の分散は s=11.31 を選択した。本論文では、予備計算テーブルを用いて離散ガウス分布に従っ て乱数を生成する Knuth-Yao アルゴリズムに対して、テーブルのメモリ参照を非零のみの桁表示を用
いて削減することにより数倍の高速化を実現した。数論変換では、多項式剰余環の元を NTT 空間へ変 換する際に、多項式係数の整数剰余環の演算において Montgomery アルゴリズムを組み込む高速化を提 案した。これらの提案アルゴリズムを Java Card で実装した結果、LPR-LWE 方式の計算時間は、暗号化 16.1 秒、復号 7.3 秒と高速なデータが得られた。次に、IoT 機器でも実行可能となる JavaScript を用 いて、米国標準技術研究所 NIST の PQC 標準化プロジェクトに提案された格子暗号 (Frodo, NewHope, Kyber, Lizard)を実装した。Frodo は LWE 問題、NewHope は ring-LWE 問題、Kyber は module-LWE 問題、
Lizard は LWR 問題と言われる計算困難問題を利用した方式である。JavaScript が実行可能な標準的な IoT 機器として Tessel 2 (580Mhz, 64MB RAM)を用い、上記の Java Card における LPR-LWE 方式の実装 で利用した多項式剰余環の数論変換 NTT および離散ガウス分布の Knuth-Yao アルゴリズムを、それぞ れの格子暗号の方式に対して適応させた改良アルゴリズムを提案した。その結果、128 ビットセキュリ ティにおいて NewHope が最も高速な実装データとなり、暗号化および復号の計算時間は 1 秒程度とな った。最後に、電力送電網で用いられるデータ通信規格 IEC 61850 において、GOOSE メッセージに対 する暗号機能部分を格子暗号により実装して性能の評価を行った。標準的な IoT 実装環境として Raspberry Pi Model 3 B+ (ARM Cortex-A53 1.4GHz)を用いて、128 ビットセキュリティの格子暗号の Keyber (暗号化機能)と Dilithium (ディジタル署名機能)を実装した。その結果、既存結果の標準的な 2048 ビットの RSA 暗号の実装では署名生成が 3.6 秒であったのに対して、Dilithium を実装した署名 生成の計算時間は 1.8 秒を実現した。以上から、NIST が標準化を進める格子暗号は、RSA 暗号と比較 しても十分に高速な実装が可能となる知見を得ることができた。
本 博 士 論 文 の 結 果 は 、 2017 年 に 国 際 会 議 IEEE International Symposium on Hardware Oriented Security and Trust (HOST'17) 、 2018 年 に 論 文 誌 Security and Communication Networks において発表しており、論文誌 IET Power Electronics に投稿中である。
以上の結果は、メモリが制限された計算環境においても格子暗号を動作可能とする効率的な実装 方法を考慮したものであり、暗号分野において学術的に高く評価できる研究業績である。
よって、本研究者は博士（機能数理学）の学位を受ける資格があるものと認める。
