量子耐性をもつ格子暗号まとめ2などに記事を書かせていただきましたが、その中でも我々は格子暗号を使ったプラットフォームの研究開発を行っています。格子暗号を使う際に一番のネックになるのが計算量が増えることです。いう演算を暗号文で行う時、それぞれの数を数千次元(時には一万以上の次元)で記述される多項式にエンコードして演算を行う必要があります。有名な格子暗号ライブラリの使用感をまとめてみた。書いたような準同型暗号のライブラリは、この多次元の多項式の演算をNTLなどのライブラリを使って高速化しているわけですが、やはりボトルネック感はかなりあります。これらの計算を機械学習などに応用しようとするときの線形代数的な演算には、乗算や加算が大量に含まれているため、これらの演算をいかにして少なくするか、もしくは効率的に行うかが、準同型暗号の実用化への鍵となるわけです。そこで、格子暗号の特徴でもあるパッキング(バッチングとも呼ばれる)を用いてベクトルとベクトルの内積を格子暗号下でいかに高速化するか、というトピックについて書いていきます。HElibの解説になります。内積を格子暗号を用いて計算するときの例について書いていきます。20でかけるわけですよね。暗号文を用いて内積を取ろうと考えると、このような書き方は一切できなくなります。b$の各要素を暗号化し、リストとして持たせます。そのあとにfor文で各要素ごとの掛け算をして、結果を最後に足し合わせます。HElibでのコードは以下のようになります。result[0];これだと、ベクトルの長さを$N$とした時に、$O(N^2)$で計算オーダー(暗号文同士の乗算)が増加していきます。エレメントごとに暗号化を行う必要があるので、ベクトルの長さが大きくなればなるほどそれにかかる時間や、メモリ消費量が増大していきます。これでは行列計算など、特に機械学習などの大きな次元のベクトルに対しては計算コストやメモリ使用量がスケールしません。そこで、パッキングと呼ばれる手法を使います。計算パッキングでは、ベクトルの要素をそのまま多項式の係数に埋め込みます。HElibでは、これはNTLの関数のSetCoeffを使って実現できます。2x^2$と多項式にエンコードします。する代わりに$4+3+2x^2$としています。b$の係数のうちの1つに入っています。係数を復号後に抽出することで内積の結果を得ることができます。CRTパッキングによる手法CRTパッキングは、多項式の係数にパッキングをする係数パッキングとは違い、使用している多項式環の部分環に数字を入れ込む形になります。Theorem)を使っているので、CRTパッキングと呼ばれています。これを用いると、一つの暗号文の部分空間に数字を複数入れ込むことができ、足し算や掛け算などの演算も、その部分空間で行われるので、いつものベクトルのような感覚で演算が行えます。部分空間を使うことの制約も往々にして存在します。CRTパッキングした暗号文にユニークな演算としてローテーションというものが存在します。ローテーションは、部分空間に入れ込まれた数字の位置をずらすことができる演算です。$a=[1,2,3]$としてパッキングしたものを一回右にローテーションすると、$a=[3,1,2]$となります。これは実際実用上たくさん使います。CRTパッキングをしたあとに、すべてのパッキングした要素を合計したい時は、ローテーションを1回ずつして、足し合わせることで、各要素の総和を得ることができます。これを利用してベクトルの内積を取るときのコードが以下になります。result[0];どれだけ高速化されるのか以上の3つのメソッドを用いて内積計算を行った時の速度比較が以下になります。メソッド1の要素ごとの暗号化、乗算を行なってしまうと大幅に計算量が増加してしまうため、高速化を考えるときにはパッキングが必須になることが容易に想像できます。CRTパッキングは暗号文がベクトルのように扱えるため、幾つもの演算を行いやすいことも多いですが、その分ローテーションなどの演算が大量に挟まってくるので結果として高速化が思った以上に望まないこともあります。係数パッキングは、係数のどこに結果が落ちてくるかをしっかりとおわなければならないので、複数の演算をするのには向きませんが、いくつかの場面ではCRTパッキングで行うようなローテーションが要らないので、計算量としては低く抑えられることもあります。まとめこのように、格子暗号を用いた演算では、内積を取る際、いろいろな制約を踏まえていろいろなメソッドを駆使して計算をおこなう必要があります。この操作を気をつけながら行うことはかなり難しいですし、骨の折れる作業ですが、これをすることで演算の高速化や、省メモリ化に取り組んで行くのは非常に重要です。弊社では、このような高速化のアルゴリズム(この内積計算など)を駆使して、秘密計算の高速化を図っています。このように格子暗号を用いた秘密計算では、どのようにパッキングを駆使して計算を高速化するかが非常に大切になってくるので、これからも多くの工夫がひつようになってきますね。