/ CRYPTOGRAPHY

格子暗号(LWE)に関する読みやすい資料まとめ

本記事は”量子コンピュータの解読に耐えうる暗号アルゴリズム「格子暗号」の最新動向”をベースにしています.

各内容について分かりやすく説明されているpaperをあげているので,私の言葉での説明というよりむしろこんなpaperがあるよという紹介になってしまった ()

量子暗号と耐量子暗号

量子暗号

2020/10/19,東芝が量子暗号通信を用いた事業の開始を発表したことで,にわかに盛り上がっている.
いわゆる量子暗号は,量子力学の理論を用いたもので,軽く調べた感じでは鍵共有(量子鍵配送)に用いられることが多いようだ.
光子が観測されるとその状態が変化する性質を利用し,観測されたことを検知すると新しい鍵を再生成するという仕組みを持つものがあるらしい.

耐量子暗号

現在主流の RSA 暗号と楕円曲線暗号は、それぞれ「素因数分解問題」と「楕円曲線離散対数問題」と呼ばれる数学的問題を利用している.これらは量子コンピュータが実現すると容易に解けることが知られている[1][2].
耐量子暗号は,高い計算処理能力をもつ量子コンピュータでも解読できない(=利用する数学的問題に対する多項式時間での効率的なアルゴリズムが見つかっていない)と期待されている暗号方式で,量子力学とはあまり関係がない.
シンドローム復号問題を解く計算の困難性を利用した符号に基づく暗号技術や,多変数多項式に基づく公開鍵方式である多変数公開鍵暗号(MPKC)などがあるが,格子探索問題を安全性の根拠とする格子暗号は特に注目されている(と思う). 私が研究するのも格子暗号であり,光子のことは正直よく知らない.

格子暗号

格子暗号は「格子点探索問題」と呼ばれる数学的問題(詳細は後述)を安全性の根拠として利用する公開鍵暗号の総称.その実現方式の一つにLWE方式がある.

格子暗号のメリット

  • 耐量子性が期待されている
  • (完全準同型性を持てば)データを暗号化したまま任意の演算を行うことができ,統計情報などを取得できるものがある(秘匿計算)

    格子暗号のデメリット

  • 現在主流のRSAや楕円曲線暗号と同程度の安全性を確保するのに数倍から数兆倍の鍵長が必要となる

格子点探索問題

格子が与えられたうえで,ある条件を満たす格子点を探索する問題である.
探索条件の内容により複数の問題が存在し,

  • SVP(Shortest Vector Problem:最短ベクトル問題)
    原点に最も近い格子点を求める問題
  • CVP(Closest Vector Problem:最近ベクトル問題)
    ある点に最も近い格子点を求める問題
  • LWE(Learning With Errors)問題
    秘密情報に関するランダムな線形の”近似値”が与えられたときに,その秘密情報を復元する問題[6]

などがある.
先に述べたLWE方式は,LWE問題を安全性の根拠とする.

格子点探索問題の難しさ(直感的な解釈)

格子暗号に利用される格子には,同じ格子を構成する基底は複数個存在するという重要な性質がある.
そして,基底はその特徴により「直行型」「非直行型」に大別できる.

(図表12.直交型と非直交型の基底の例(2 次元空間の場合)を参照)(転載できないので)

ベクトルの長さが短く,互いに直交に近ければ,格子の全体像を把握しやすいので,ある種”より良い”基底と言えるだろう.
直行型の基底を知っている場合は格子の全体像を把握しやすいので,ある条件を満たす格子点を探索しやすい.
一方,非直行型の基底のみ知っている場合は全体像が把握しづらいので,条件を満たす格子点を探索しづらい.

この性質を”公開鍵から秘密鍵を現実的な時間で求めるのは難しい”という一方向性にあてはめ,
直行型の基底を公開鍵,非直行型の基底を秘密鍵にして,格子暗号は公開鍵暗号を構成している.

LWE方式,LWE問題

2009年,RegevはLWE問題に安全性が帰着できるLWE方式を提案し,LWE問題はSVPに関する最悪時計算量の計算量的困難性の仮定の下で安全であることを証明している[3].

LWE問題は,最悪時の探索版LWE問題(sLWE)と,判定版LWE問題(dLWE)があるが,今回はsLWEを紹介する.詳しくは,[4]を参照されたい.

\[\begin{array}{|c|c|} \hline m & サンプル数 \\ \hline n & 次元数 \\ \hline q & 法 \\ \hline \end{array}\]

正の整数 \(q\) に対して,\(\mathbb{Z}_q\) = \(\mathbb{Z}/q\mathbb{Z} = \{0, 1,..., q − 1\}\)(\(0からq-1\)までの整数全体の集合)とする.
\(m×n\)行列\(A \in \mathbb{Z}^{m×n}\)とランダムなベクトル\(s \in \mathbb{Z}^{n×1}_q\)に対して, 標準偏差 \(σ\) と平均 \(0\) の離散ガウス分布 \(χ_\sigma\) から生成される整数エラーベクトル \(e \in χ^{m}_{\sigma}\) を用いて,

\[\boldsymbol{b} = \boldsymbol{As} + \boldsymbol{e} \pmod{q}\]

とする.\(\boldsymbol{e}\)は,格子点\(\boldsymbol{As}\)を格子から”ずらす”ために加算されている.

lattice2.

def:LWE問題

\(\boldsymbol{b} = \boldsymbol{As} + \boldsymbol{e} \pmod{q}\)
与えられた行列 \(A\) とベクトル \(\boldsymbol{b}\) に対して,ベクトル \(\boldsymbol{s}\) を求める問題[5].

もし,\(e\)がなければ \(\boldsymbol{b} = \boldsymbol{As} \pmod{q}\)となり,ガウスの消去法により多項式時間で簡単に解を求められる点に注意する.即ち,与えられる誤差\(\boldsymbol{e}\)の度合いがLWE問題をより難しくしている[6].

LWE方式では,上記の\(n\)個の整数の組\((\boldsymbol{s},\boldsymbol{e})\)を秘密鍵,\(\boldsymbol{b}\)を公開鍵として利用する.攻撃者は,公開鍵\(\boldsymbol{b}\)から格子点\(\boldsymbol{As}\)を計算できれば,秘密鍵\(\boldsymbol{e}\)を容易に計算できるほか,秘密鍵\(\boldsymbol{s}\)も求めることができる.しかし,ある点\(\boldsymbol{b}\)から格子点\(\boldsymbol{As}\)を求めるには格子点探索問題(=格子の中からある条件を満たす格子点をみつける問題)を解かなければならない.ここで,格子暗号は,直行型の基底を公開鍵,非直行型の基底を秘密鍵にしていることを思い出すと,これが困難であることが分かる.即ち,格子点探索問題を現実的な時間内に解けなければ,LWE方式は公開鍵暗号の安全性を担保する.

格子暗号に対する攻撃

格子点探索問題を解く一般的なアプローチは,
(i)探索範囲の絞り込み(格子基底簡約)
(ii)しらみつぶしに探索
の処理からなる.

(i)探索範囲の絞り込み(格子基底簡約)

文字通り格子上で暗号文に最も近い格子点の候補が存在する確率の高い格子の範囲を絞り込む操作である.
格子基底簡約(lattice basis reduction)とは,格子\(L\)の基底\(\boldsymbol{b}=\{b_1,b_2,...,b_n\}\)が与えられたとき,基底をなすそれぞれのベクトルの大きさ(Euclid norm)が小さくかつ互いのベクトルが直交に近い同じ格子に対する別の基底をみつける魔法のような操作である.この操作を行うことにより,非直行型な基底を格子点探索問題の章で扱った”より良い”基底に変換できる.つまり,公開鍵から秘密鍵に近いものを探すことができる(見つかるとは言っていない).

  • LLL基底簡約 : 最も有名な格子基底簡約アルゴリズムで,SVPを効率的に解くことができるが,最短な非零ベクトルを必ず見つけるわけではなく,第一逐次最小λ1(L)にある指数因子をかけた値よりも小さいノルムを持つベクトルを見つけるアルゴリズムである点は注意したい.
  • BKZ基底簡約 : LLL基底簡約の一般化である.格子をブロック化してその中の最短非零ベクトルの数え上げとLLL基底簡約を組み合わせた手法であるため,LLL基底簡約に比べより短い格子ベクトルを見つけることができるが,ブロックサイズに関して指数関数的に実行時間が長くなる.

正直,この辺の数学的なバックグラウンドはあまり理解できていない…
幸い,(日本語の!)書籍[7]に詳述されているのでいつか復習したい.

(ii)しらみつぶしに探索

探索範囲の絞り込みを行った後,条件を満たす格子点をしらみつぶしに探索する.
基本的な手法としてKannan’s embedding法[8],列挙法(Extreme-Pruning)[9]がある.


LWE問題に対する標準的な解読法として,LWE問題をq-ary格子に埋め込み,SVPに帰着するSIS(Short Integer Solution)攻撃,Babai’s nearest plane アルゴリズムによりCVPに帰着するBDD(Bounded Distance Decoding)攻撃がある.
[5]ではLWE問題をBDD問題に帰着させ,BDD攻撃をKannan’s embedding法によりunique-SVPに帰着して解く方法と列挙法により解く方法が最も高速なアルゴリズムとされている.
Kannan’s embedding法に帰着させる方法は[5][10]を.また,これらを読むにあたり登場するq-ary格子やHNF,BKZなどについての予備知識は[11]で勉強できる(日本語)(これもかなり難解だった…).

まとめ

格子暗号は格子点探索問題を安全性の根拠としている.そのうちのRegevが提案したLWE方式は完全準同型暗号方式であり,安全性が注目されているだけでなく,暗号化したまま加法乗法ができる(∵FHE)性質も持っているため秘匿計算への応用も期待されている.LWE暗号への攻撃方法として,LWE問題の入力に対してq-ary格子を考えることでLWE問題→BDD問題→unique-SVPへ帰着させ,BKZ格子基底簡約アルゴリズムを適用して秘密鍵(\(\boldsymbol{s}\),\(\boldsymbol{e}\))を計算する方法を紹介した.
bootstrappingやらmodulus-switchingやらRing-LWEやらまだまだ書くべきことはあるが,疲れたのでこの辺で.
秘匿計算についてはまたいつか…

参考

[1] P.W.Shor, Atgorithms for quantum computation: Discrete $\log$ and factoring, Proc. of the 35th Annual IEEE Symp on Foundations of Computer Science, pp.124-134, 1994.
[2] P.W.Shor, Poiynomial-time aigorithms for prime factorization and discrete logarithms on a computer, SIAM Journal on Computing, vo1.26, no.5, pp.1484-1509, 1997.

[3]Regev, Oded. “On lattices, learning with errors, random linear codes, and cryptography.” Journal of the ACM (JACM) 56.6 (2009): 1-40.
[4]完全準同形暗号の概要
[5]ポスト量子暗号の更生法とその安全性評価
[6]格子問題等の困難性に関する調査
[7]格子暗号解読のための数学的基礎―格子基底簡約アルゴリズム入門―
[8]Domich, P., Kannan, R., Trotter, L.: Hermite normal form computation using modulo determinant arithmetic. Math. Oper. Res. 12, 50–59 (1987)
[9]Gama, Nicolas, Phong Q. Nguyen, and Oded Regev. “Lattice enumeration using extreme pruning.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2010.
[10]Yuntao Wang, Yoshinori Aono, and Tsuyoshi Takagi. An experimental study of kannan’s embedding technique for the search lwe problem. In International Conference on Information and Communications Security, pp. 541–553. Springer, 2017.
[11]耐量子計算機暗号の研究動向調査報告書

teahat

teahat

I'm t3ahat.

Read More

Tags

Latest Posts