GGH暗号の解析

ref:M. S. Lee and S. G. Hahn “Analysis of the GGH Cryptosystem” (SCC 2008).
予稿のコピーを頂いたので読んだ.

GGH暗号 (CRYPTO 1997) の復習.

セキュリティパラメータ (格子の次元) をnとする. (n=200〜400を想定する.)

鍵生成

Rを比較的直交している基底とし, Bを歪んだ基底とする. (適当なユニモジュラー行列Tを取って, B=TRとする. L(R)=L(B).)

暗号化

m∈{-128,...,+127}^nを平文とする. e∈{+σ,-σ}^nとして, c=mB+eが暗号文. (σ=3を想定.)

Nguyenの攻撃 (CRYPTO 1999) の復習.

s = (σ,...,σ)とする. すると, c + s = mB + e + s = mB (mod 2σ). m'B = mB (mod 2σ)を解いて, m' = m mod 2σを得る. この段階で平文の部分情報を得ることが出来ている.
さて, c - m'B = (m-m')B + eである. 両辺2σで割れば, (c - m'B)/2σ = ((m - m')/2σ)B + e/2σ. 今, m'' = (m - m')/2σは整数ベクトルである. また, e/2σの長さは高々√n/2である. よってよりエラーベクトルが短いCVPインスタンスを得ることが出来た. なのでこれを別の基底に埋め込んでSVPの問題だと思ってLLLやらHKZとかで解くと, e/2σが得られることが多い. そこから逆算してmを得て, n=200〜350のチャレンジの解読に成功したと.

予稿の話

平文の一部を知っているときに攻撃がし易くなっているかどうか考えよう.
今, m = (m1 m2)だとしよう. (m1, m2はそれぞれk次元, n-k次元のベクトル.) また, B = (B1 B2)^Tと書ける. よって, mB = m1 B1 + m2 B2である. もしm1を知っているならば, c = mB + eなので, c - m1B1 = m2B2 + eが計算出来る. 今, L(B2) ⊆ L(B)とB2が張る格子はL(B)の部分格子. ガウスのヒューリスティックな概算を使うと, L(B2)のギャップがL(B)のギャップより大きくなり易い. また, B2の方はrankがn - kに減っている. なので, より解けそうなCVPインスタンスを得ることが出来る. というのがメインのアイデア. あとはNguyenと同様の方法でSVPインスタンスに埋め込んで解く.

実験によると, k=1, 2の場合でも結構ギャップが大きくなるらしい. Nguyenがn=400の場合のチャレンジについてm (mod 2σ)を求めている. そこから, mの先頭の要素が絞れるので, 全通り試して攻撃したと. n=400の場合にも解けたという実験報告が載っている. (数日掛ったらしい.)

最後の議論のところでNTRUの話も出ている. NTRU格子で考えた場合は次元が削れるのは同様だが部分格子のギャップがあんまり大きくならないので微妙そう, という話.

というわけで予稿を頂いたおかげで色々分かりました. ありがとうございます.