完全準同型暗号の論文を読む - GSW 編 (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

さて、前回予告した通り、今回は GSW の論文の解説をします。

前回は完全準同型暗号とはどういうものなのか解説しました。
そして、GSW はその完全準同型暗号の手法の１つとして 2013 年に提案された論文です。

こちらは高校数学レベルの線形代数（行列・ベクトル）の知識があれば理解できますので、
先に高校数学レベルの行列とベクトルの要点だけおさらいしておきましょう。
GSW の仕組みのカギとなる、固有値と固有ベクトルの性質について簡単にまとめます。

大変申し訳ないのですが、基本的な定義や計算などについては高校数学についての
参考書的なサイトがいくつもありますので、そちらも参考にしてみてください。

固有値と固有ベクトル

行列 A とベクトル v と実数 \lambda があるとき、
Av=\lambda v が成り立つ v を固有ベクトル、 \lambda を固有値と呼びます。

要するに、固有ベクトル v を行列 A で線形変換した時、
元のベクトル v の長さが \lambda 倍になって、方向は変わらない。ということです。

行列 A を主体で考えると、A による線形変換で、
向きが変わらずに長さだけ変わる方向が、固有ベクトルで、
その拡大率が固有値。と言い換えることもできます。

ここで注目したいのは、共通の固有ベクトル v を持つ行列 A と B があり、
それぞれの固有値を \lambda 、 \omega としたとき、
(A+B)v=Av+Bv=\lambda v+\omega v=(\lambda+\omega)v
が成り立つため、行列 A+B の固有ベクトルは v のまま変わらず、固有値は和になります。
(A \cdot B)v=A(Bv)=A(\omega v)=\omega(Av)=\omega(\lambda v)=\lambda \omega v
と計算できるため、行列 A \cdot B の固有ベクトルも v のまま変わらず、固有値は積になります。

共通の固有ベクトルを持つ行列が２つあると、
その積も和も、固有ベクトルは変化せず、固有値は積や和になります。

勘のいい方はこの辺で、どうやって完全準同型にするのか、
想像がつくのではないでしょうか。

そうです、固有値を平文、固有ベクトルを秘密鍵、行列を暗号文としてしまうのです。

LWE 問題

さて、完全準同型「暗号」というからには、暗号文から平文に戻すのが
難しくなければなりません。

このままでは、暗号文である行列から固有値固有ベクトルを計算するのは容易です。

そこで出てくるのが LWE 問題（Learning With Errors Problem）です。

まず、n 個の変数でできた一次方程式が、特定の条件で n 個あれば連立方程式として解けます。

n 個の連立方程式を行列の形で Ax=b と書き直して
（A は n \times n 正方行列、x, b は n 次元ベクトル）、
A^{-1} を求めることができれば（これが「特定の条件」）、 x=A^{-1}b で解けます。

では、ここに変数を１つ加えましょう。
Ax+e=b （e も n 次元ベクトル）。

これだけで、 e を知らない人にとっては x を求めることはできなくなります。
この e は小さい値で十分です。要するに誤差成分ですね。連立方程式に誤差を加えた問題。
これを LWE 問題と呼びます。この問題は量子コンピュータを使っても解けません。
つまり量子耐性がある問題なのです。

秘密の情報を知らないと解けない問題。これは暗号に使えますね。
というわけで、これを応用するのが LWE 暗号です。

GSW の原型を組み立てる

行列を暗号文、固有値を平文、固有ベクトルを秘密鍵とする考え方をそのままに、
元の式、Av=\lambda v に誤差成分を足します。Av=\lambda v+e と。

この e が存在することによって、 A からは v も \lambda も、求められなくなります。

復号するには、 A から好きな行を取り出して、秘密鍵 v との内積を取ります。
そして、 v の同じ行の要素で割ります。すると得られるのが \frac{A_i \cdot v}{v_i}=\lambda+\frac{e_i}{v_i} 。

\lambda が復号で得たい平文なので、平文λは常に整数だという制約を加えた上で、
\frac{e_i}{v_i} の部分が -0.5～0.5 の間に収まっていれば
\lambda+\frac{e_i}{v_i} を四捨五入することで平文 \lambda が得られます。

e の要素が小さすぎると、 A から固有値固有ベクトルの近似値が求まってしまうので、
ある程度 v の要素を大きくして、 \frac{e_i}{v_i} を小さいままに e を大きくする必要があります。

まとめ

今回は GSW の論文で提案されている完全準同型暗号の原型まで解説しました。
次回はこのアルゴリズムの問題点と制限についてお話します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。