概要

準同型暗号とは、暗号の中でも、
暗号化したまま計算することが可能な暗号
のことです。

準同型暗号にはいろいろな種類がある一方で、
格子暗号はその中でもよく使われている暗号の種類です。

格子暗号の中にもいくつかの形式が存在し、
よく使われている２つの形式について以前記事を書きました。

この中でも、CKKS形式を用いると、
SIMD演算と呼ばれる手法を用いて高速に線形演算を実行することができます。

今回は、その線形演算の手法について

スロットパッキング
対角パッキング
係数パッキング

と呼ばれる代表的なやり方について解説したいと思います。

以前内積手法について書いた時の記事

数年前にも、暗号状態で内積を計算する時の手法について一度記事を書いています。

この時はHElibという格子暗号ライブラリをよく使っていたので、そのライブラリをもちいて
計算するやり方について書きました。

この記事も合わせてチェックしていただければと思います。

SIMD とはなんなのか？

先ほどCKKS形式はSIMD演算を用いることができるため、
線形演算の計算に適している

と書きましたが、どう言う意味なのでしょうか。

SIMD演算とは、コンピュータサイエンスで使われる専門用語で、
Single Instruction Multiple Data
の略です。

簡単に言えば、一度の演算で複数個のデータに対して演算が実行できるという意味です。

格子暗号におけるSIMDの意味

格子暗号では、平文と暗号文空間に多項式を用います。
多項式の次元は2^10 ~ 2^14　がよく使われます。
これらの多項式に自分の平文（隠したいメッセージ）を埋め込むわけですが、
平文空間が多項式であることから、一度にたくさんのメッセージを埋め込むことができます。
その埋め込み方を工夫すると、計算した時に、埋め込んだ複数のメッセージに対して一度に演算を実行できます。

単純に言えば、Numpyのベクトル演算を暗号状態で行えると思ってください。
暗号化するので、少しだけ工夫が必要ですが、慣れたら当たり前に使われる手法です。

エンコード

先述の通り、複数のメッセージを平文に埋め込むことを、
エンコードする、と言います。

エンコードを実行することで、先ほどの繰り返しになりますが、以下の様なメリットがあります。

複数の数を一つの多項式にエンコードできる
ベクトルを多項式にエンコードできる
一つの暗号で複数の数を暗号化できる
暗号状態でベクトル演算のようなものが可能

エンコードの種類

エンコードにもやり方がいくつかあり、よく使われるのは

CRTパッキング
係数パッキング

の二つです。
それぞれに後述する様なメリットがあり、自分のやりたい演算に合わせて使い分けることが多いです。

CRTパッキング

CRTパッキングのCRTは、
CRT(Chinese Remainder Theorem) の略です。

このCRTという定理を利用すると、
剰余環が部分環の直積で表現されることから複数の数字を一つの剰余環の要素に埋め込むことが可能になります。
剰余環とかいきなり難しい言葉が出てきたのですが、
難しい言葉を用いなければ、

CRTを利用すると、１つの数字や多項式（環と呼ばれる）に数学的な工夫を加えることで、
複数の数字や多項式を同時に存在させることができる。

という意味になります。

例えば、上は非常に簡単な例になりますが、
15で割った時のあまりの空間である剰余環を用いれば、
その要素は3で割った時の剰余環と、5で割った時の剰余環の直積（組み合わせ）で表現できます。
これは、一つの数字をあたかも２つの数字のベクトルである様に表現したものであり、
複数の空間を一つの空間で表しています。

この時、１５で割った空間で演算を行うと、
３で割った空間と５で割った空間でもそれぞれその演算が行われた様に保存されます。
つまり、それぞれの空間内で演算（足し算と掛け算）が保存し、
ベクトルのような計算が可能になります。

この性質を多項式について利用することで、複数のメッセージを一つの暗号で表現し、
演算に対しても１回の演算で複数のメッセージに対して演算を実行するやり方を
CRTパッキングによって実現します。

係数パッキング

CRTパッキングに対して、係数パッキングはとても単純です。

上の様に、1,2,3というベクトルを暗号化したい時、
1,2,3が係数にくる様な多項式をそのまま用意するだけです。
この多項式が平文の多項式になり、この多項式に対して暗号化を実行します。

CRTパッキングの様に、多項式環の性質を利用すると言うよりは、直感的に係数に対してメッセージを入れるだけなので、係数パッキングと呼ばれています。

エンコードに応じた線形演算

CRTパッキング、係数パッキングの二つのエンコード手法について解説しましたが、
これらを元にエンコーディングされた多項式を暗号化すると、
それぞれをベクトルの様に扱えるため、ベクトル同士の

足し算
掛け算
内積計算

などが可能です。

それぞれのエンコーディングに対してこれらの演算をどう実行するかについてみていきます。

CRTパッキング

CRTパッキングで二つのベクトルを暗号化(c1, c2) し、
それらに対して加算や乗算を実行してみます。

加算、乗算

内積

内積については、もう一つだけ演算を導入する必要があります。
それは、「回転」と呼ばれる演算です。

内積を計算したいのであれば、二つのベクトルを乗算した後に、
全ての要素について足し算をする必要があります。
CRTパッキングをして計算すると、それぞれの要素「同士」で足し算や掛け算をすることは
できるのですが、要素を跨いで（別スロットに対して）足し算をすることは普通ではできません。

そこで、回転という演算を導入し、回転させたベクトル同士を足すことで
全ての要素を足し算するという演算を実現します。

上記が、ベクトルに対して回転を実行する時の例です。
平文として使用する多項式の性質を利用して、多項式をxの何乗かで掛け算することで、
内部のスロットの要素をずらすことができます。

上の例では、[8,5,16,9] を左に２回回転させることで
[16,9,8,5] を作っています。
この二つのベクトルを足すことで、もともとのベクトルの０番目の要素と２番目の要素を足し算できたことになります。

同じ様にもう２つ回転ベクトルを用意すれば、この例ではベクトルの要素を全て加算することができます。

上の例では便宜上平文ベクトルを扱っている様に書きましたが、
上の様に回転させたりする操作は「暗号文空間で実行」されています。
よって、ベクトルの加算や乗算、回転、それらを組み合わせた内積
は全て暗号文空間で実行され、それが復号されると、平文の内積結果が得られる仕組みになっています。

係数パッキング

係数パッキングは、ベクトルに対して

要素毎の加算
内積

が実行できます。

要素毎の乗算

は実行が難しいです。

加算

内積

上のスライドが、二つのベクトルに対して
係数パッキングでエンコードして暗号化した後に内積を取るやりかたを解説したものです。
キーポイントは、一方のベクトルは普通にエンコーディングするのに対して、
もう一方のベクトルは逆向きにエンコーディングするというところです。

そうすることで、多項式同士の掛け算で畳み込み演算を実行するという性質を利用し、
内積を１回の掛け算で計算することができます。
CRTパッキングの時と違うのは、回転のような操作が係数パッキングを用いて作ったベクトルにはできないというところです。

回転は比較的重い演算のため、
内積の時に回転をやらなくていいということは係数パッキングのアドバンテージになります。

しかしながら、要素毎の乗算ができないことや、
内積の結果を取り出すためには基本的には一度復号しなければならないことなどから、
多くの場合で選択されるのはCRTパッキングの方です。

エンコードの他の使い所

例えばCKKS形式では、CRTパッキングを暗号化前のエンコードとして基本的に必ず使用します。
このとき、あえて係数パッキングを使ってエンコードすることも可能です。
CKKS形式においてブートストラップと呼ばれる、暗号文のノイズを、暗号を復号することなく小さくするような高度手法においては、
暗号状態でこのCRTパッキングと係数パッキングを行き来する必要があります。
この様に、必要であれば暗号状態でこのパッキング形式を変更し、自身の行いたい演算に有利な様に使い分けることが可能なのです。

このCKKS形式のブートストラップなどについてはまた別記事で言及しようかと思います。

まとめ

今回は格子暗号を用いて線形演算する時に使われる

CRTパッキング
係数パッキング

と呼ばれるエンコード手法と、それらに対する演算の実行方法について解説しました。

ぜひ一度手を動かして実装してみてください。

今回はこの辺で。

@kenmaro