概要

格子理論は、めちゃくちゃ奥が深い。格子にはいろいろな用途があり、１つは格子暗号の構成であるが、もう１つは格子を使った既存暗号への攻撃である。これを理解するために、
LLLアルゴリズムについて今一度調べてみようと思う。また、その際にHowgrave-Grahamの補題にも出くわしたので簡単にまとめてみる。
参考文献は、國廣さんの論文であり、とてもわかりやすいので
これを読むのをお勧めします。

内容

簡単にまとめると、

格子は基底を整数倍したものの和で張られる点の集合のことである。
格子を使ってRSA暗号を攻撃することができる。
格子の重要概念である基底を簡約化するアルゴリズムがLLLである。
LLLでRSA暗号を攻撃できる。
その時にHowgrave-Grahamの補題が出てくる。

です。

LLL アルゴリズム

格子には基底（線形独立なベクトル）が存在し、それらに整数の係数をつけて線形和をとった時に張られる点の集合のことを格子と呼んでいるのだが、それらの基底は複数存在する。それらの中で、それらのノルムの和が最小となるものを最小基底と呼ぶが、それを求める問題はミンコフスキーの定理より、NP困難である。

LLLアルゴリズムは、その格子の最小基底を近似的に求めるアルゴリズムであり、それが多項式時間内に解けることが特徴である。また、格子の次元が低いときは、基底簡約によって最小基底の厳密解が求まることが多い。LLLアルゴリズムの本質は、Gram-Schmidtの直行化の演算を整数演算で近似することである。
具体的なアルゴリズムのステップに関しては、ウィキペディアなどを参照すると書いてある。

RSA暗号を格子がどう攻撃するか

格子は、線形独立なベクトルの集合によって定
義される加群である。格子は、暗号攻撃と暗号構
成の双方に用いられてきた。
格子を暗号攻撃の手段として用いる場合、1982
年に提案された LLL アルゴリズム(14)が良く用いら
れる。LLL アルゴリズムは、ナップザック暗号や
特殊なパラメータを用いる場合の RSA 暗号に適
用されてきた。

とあるように、格子理論は暗号攻撃と、暗号構成の２つの側面がある。

攻撃という側面では、格子を使うことである条件下で、RSA暗号の秘密鍵を計算可能であることが知られている。
深くは踏み込まないが、簡単にRSA暗号をおさらいすると、$p, q$を異なる素数として、$N=pq$とし、公開鍵を$(e,N)$、 **秘密鍵を$d$**とする。このとき、これらは$ed=1 (mod (p-1)(q-1))$を満たしている。これがRSA暗号の基本である。この鍵ペアを用いて、暗号化は　$C=M^e mod N$、復号は　$M = C^d mod N$で求められる。
格子理論が解くことのできる条件とは、この秘密鍵$d$が比較的小さいパターンの時であり、$ d = N^\sigma$と書く時に、$\sigma < 0.292$の時である。したがって、全ての場合に攻撃できるわけではないが、この条件下では秘密鍵を求めることができる。

ここでは詳細を省くが、先ほどの鍵ペアが満たす方程式$ed=1 (mod (p-1)(q-1))$を変形すると、$ed-1-k(A-s) = 0 (mod e)$となる。これは$x(A+y) +1 = 0 (mod e) $という方程式に一般化されるが、この方程式は２変数法付方程式と呼ばれる。この方程式の解を$\overline{x}, \overline{y} $とした時、これらの解が、$|\overline{x}| < e^\sigma, |\overline{y}| < e^{1/2} $という条件を満たす時、この解を求めることをSmall Inverse Problemという。ここに格子を使うことができる。
これを求めることは、RSA暗号において秘密鍵を特定の条件下で解けることになるため、格子がRSA暗号を攻撃できるということである。

このときに出てくるのがLLLとHowgrave-Grahamの補題

上で出てきたような法付きの方程式を解く時には２つのアプローチがある。　

解を直接格子の最短ベクトルに埋め込み、最短ベクトルを導出する方法
法が外れた代数的にに独立な方程式を複数本導出し、その連立方程式の解を求める方法

である。1では、格子の最短ベクトルを求めるSVP問題を解くオラクルが必要になり、一般的にこの問題はNP困難（多項式時間で答えが計算できない）であるが、２では理論上は多項式時間内に計算を収めることができる。ここで法付きの方程式から法を外す時に使われるのが、Howgrave-Grahamの補題である。

法付き方程式のSmall Inverse Problemの解vを使い、それらで構成される基底を設定、つまり格子を決める。その設定された基底を、LLLアルゴリズムで簡約化し、最小基底を求める。これにより、最終的に解を求めることができるのである。

おわりに

細かい導出などは上の参考文献や、ウィキペディアなどにたくさん式が書いてあるのでそちらを参照していただきたいが、格子は暗号構成だけでなく、RSA暗号の攻撃に使われるなど、とても面白かった。もっと勉強していきたい。

おわり。