Gentry暗号の簡単な解説

抽象的なことしか書きません. 詳しいことはACMに$10払うかフルヴァージョンを待つかしましょう.
Gentryの論文は格子の説明が無く初学者に厳しいので, その部分を補うためのノートに使ってください. ただし線形代数多項式環の知識は仮定します. (といっても学部で習う基本しか使いません.)

暗号方式が3つ出てきますが, 最初の1つだけ気持ちを伝えます.
fを整数係数モニックなn次多項式として環R=Z[x]/f(x)を考えてください. 和と積はZ[x]上で計算してf(x)で剰余を取れば良いです. 更にこの環のイデアルIを1つ持ってきます. 面倒だったらI=(2)とか考えといてください. RとIが共通パラメータです. 公開鍵はIと互素なイデアルJの歪んだ基底Hです. 秘密鍵はこのJの綺麗な基底Bです.
暗号文はコセット m + I の要素 m + i を考えて, c = m + i mod Hです. 復号は綺麗な基底を使って, m + iを取り出して, mod Iを取れば, mが求められます.
なんのこっちゃ.

準備

格子

格子というのは, Z^n中の離散な加法的部分群のことです. なんのこっちゃ. b_1,...,b_n in Z^nが線形独立だとしましょう. B=[b_1,...,b_n]を正方行列として, L = {Bv : v in Z^n} = {\sum_{i} v_i b_i : v_i in Z}ってのが, 格子です. これだと分かり易い. 格子Lに対して, Bのことを基底と言います. そのまんまですね. 1つの格子Lに対して, 基底は無限に存在します. なぜなら, ユニタリ整数要素行列Uを使って, L = {BUv' : v' in Z^n}と書けるからです. まぁ, UはZ^nの線形な1対1写像になっているので良いわけですよ.

多項式環とZ^nの同一視

ベクトル的に考えるのが重要なので, こうしましょう. R=Z[x]/f(x)はZ^nと同一視できます. 具体的には多項式a(x) = a_0 + a_1 x + ... + a_{n-1} x^nをベクトルa = (a_0,a_1,...,a_{n-1})^Tと同一視します. 和はそのまんま. あとZ^{n}の方に対応する積を入れればOKです. これは巡回行列のアイデアを使うと綺麗に書けます. まず, aに対して回転関数を定義します. rot(a) = a(x)・x (mod f)とすればOK. 更に, Rot(a) = [a, rot(a), ..., rot^{n-1}(a)] と定義すると, a(x)・b(x) = a * b = Rot(a)・bと対応が付けられます.

イデアル格子

イデアル格子を定義します. 格子Lがイデアル格子であるとは, Lと同型な環RのイデアルIが存在することです. L = {2Id v: v in Z^n}なんてのはイデアル格子です. なぜなら, 対応するイデアル (2) = {2v : v in R}が存在するから. 逆にイデアルからイデアル格子を定義するのも簡単です. イデアル(a_1,...,a_m)を考えると, 行列[Rot(a_1), ..., Rot(a_m)]とnm本のベクトルを考えて, 適当に直して基底を作って, 格子を作れば良いと.

綺麗な基底と歪んだ基底

GGH暗号方式をMicciancioが改良したもの (CaLC 2001) を思い出します.

鍵生成
秘密鍵は綺麗な基底 B=\sqrt{n}I + R (Rはランダムな小さい要素の行列). 公開鍵はその歪んだ基底H. ここでは, エルミート標準形を使います.
暗号化
平文vを{0,1,2,3}^nの要素とします. 暗号文はc = v mod H.
復号
綺麗な基底Bを知っていると, vが短いベクトルであれば, v mod Hからvに戻せます. 下図を参照のこと.

Gentryの暗号方式その1についてもう1度

簡単に言うとイデアル版Micciancio-GGH+ランダム化です.
平文空間を{0,1}^n mod Iとします. BをイデアルJの綺麗な基底, HをイデアルJの歪んだ基底とします. s in Iを(s)がJと互素になるように選びます. (sは短いベクトル.)
公開鍵は, (R, I, s, H), 秘密鍵はBです.

暗号化
rをRからランダムに選んで,  c = m + r s \bmod{H}. これはm + Iというコセットのランダムな要素 m + iをJで剰余を取ったものです. (ただしrが小さい必要あり.)
復号
 m = (c \bmod{B}) \bmod{I}. 気持ちとしては, (c mod B)でR上でcをm+rsに戻してやる. 後, mod Iを取れば, rsはイデアルIに含まれるので消えて, m mod Iが求められます. この辺はGGHやNTRUと同じですね.

n次元の絵は描けないので2次元で.
まず, m+rsを考えます.

m+rs mod Hだとぐちゃぐちゃ.

m+rs mod Bだと綺麗に四隅に入るので, 戻せそうな気がしてきます. n次元でもm+rsと基底の長さによってちゃんと戻せることが証明できます.

特徴としては簡単に準同型性が言えます.

  • (m + rs) mod H + (m' + r's) mod H = (m + m') + (r + r')s mod H
  • (m + rs mod H)(m' + r's mod H) = (m m' + (m' r + m r' + r r' s) s) mod H

です.
問題は, mとrがそこそこ短くないと復号できないという点です. 足し算したくらいではそんなに長くなりません. しかし, 掛け算すると上の式から分かる通り, 平文ベクトルも乱数ベクトルも長くなります. これを称してエラーが溜まるというわけです.
このエラーの溜まり方は厄介で, 復号回路をシミュレートしようとして和と積を繰り返すと, 結果的に得られる暗号文の平文と乱数が復号できる範囲を超えてしまいます. これは困ったと.

あともう一つの問題は仮定です. R mod H上の一様分布と, rs mod Hが識別不可能という, 決定版CVP問題が難しいことを仮定しています. ちょっと強めの仮定ですね.

解決策

こっからはアブストにあるくらいのことしか話しません.
まず頑張って暗号方式を変形して復号回路の計算量を減らします. がらりと暗号化、復号が変わるのでここ元論文を読んでください. すると深さが減ります. そうなると, 掛算の回数が減るので嬉しいわけです.
KDM安全性を仮定して, (pk1, sk1), (pk2, sk2)を考えます. d = Enc_{pk1}(sk2)が公開されているとします. pk2で暗号化された暗号文e = Enc_{pk2}(m)があったとしましょう. eをもう一度pk1で暗号化すると, e~ = Enc_{pk1}(e)です. これとdを使うと, pk2側の復号回路がpk1側でシミュレート出来ならば, e~ = Enc_{pk1}(m)が計算できます. Enc_{pk1}関数が新しく追加するエラーが小さければ, これを繰り返し行うことでいろいろ出来そうなわけです.