kenmaroです。
秘密計算、準同型暗号などの記事について投稿しています。

最近格子暗号を理解するためのロードマップを公開しました。格子暗号に興味のある方、勉強してみようかな、という方はぜひご覧ください。

最先端の秘密計算技術、格子暗号スタディロードマップを公開！！（エンジニア、リサーチャー必読）

概要

SEALライブラリは、マイクロソフトリサーチが開発運用している、
おそらく世界で一番今のところよく使われている格子暗号ライブラリです。
オープンソースであり、実装に関しても非常に洗練されています。
また、開発も活発で信頼性が高いOSSです。

SEALライブラリを使用する際、実用上CKKS形式を使う人が多いと思います。
https://github.com/microsoft/SEAL/blob/main/native/examples/4_ckks_basics.cpp
などにexampleコードがあり、詳しくドキュメント化されているのですが、
いまいちscaleなどについてどのように設定すればいいかわからない人も多いと思います。

したがって、
modulus_chain や、scale パラメターによる精度ビットについて、
今一度まとめてみました。

とりあえず動かしたければ

以下の設定を基本的に使えば大体問題ありません。(とりあえず動けばいい、も正義である。）

size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
double scale = pow(2.0, 40);
vector<double> modulus_chain = { 60, 40, 60 }
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, modulus_chain));

これで暗号同士の掛け算が１回実行可能（leveled = 1)
な暗号設定をすることができます。

それぞれのパラメータの意味って？

上で出てきた設定を少しだけ深掘りしていきます。

poly_modulus_degree

size_t poly_modulus_degree = 8192;

poly_modulus_degree は使用する多項式の次元です。
この場合 $2^{13}$ である　$8192$を用いています。

ここの数は基本的に２の乗数を用います。理由は複数ありますが、一番大きいのは多項式同士の乗算を行うときに、
高速フーリエ変換FFTを用いることができるためです。

scaling

double scale = pow(2.0, 40);

この値はスケールと呼ばれます。

CKKS形式では暗号上に加えるノイズを、多項式の係数の下位ビットへと挿入するようになっています。
したがって、暗号化したい多項式の係数の値に一度大きな数を掛け算しておき、（ゲタを履かせるようなイメージです。）
ノイズは小さい値として多項式の係数に足し算をします。
このときにかける値（履かせるゲタの高さ）がスケールです。

この場合は$2^{40}$としています。基本的にあまり精度などを深掘りしたくない場合は、
これをデフォルト値として使用して大丈夫です。

modulus_chain

上の設定では、
modulus_chain は

vector<double> modulus_chain = { 60, 40, 60 }

となっています。
まず、このそれぞれの数は暗号空間で使用するビットの大きさであり、
初めにこの総数についてセキュリティ上の制約が存在します。
例えば、

CoeffModulus::MaxBitCount(8192) returns 218

であり、poly_modulus_degree が$8192$においては、
modulus_chainの総数は218を超えることはできません。
これは１２８ビットセキュリティを使用する際の制約です。

チェインの長さは暗号同士の掛け算回数を意味する（Leveled)

modulus_chain がなぜチェインと呼ばれるかというと、
暗号同士の掛け算を一定回数許容するLeveled準同型暗号において、
掛け算をするたびに、ノイズの爆発を防ぐ（指数的なノイズ増加を線形増加にするため）
ために暗号空間のモジュラスを小さくする必要があるからです。

これは、前もって同じくらいの大きさの素数をレベル分（例えば３回掛け算したいのであれば３つ用意）用意しておき、
掛け算するたびにその素数で全体のモジュラスを割り算することで実現しています。
したがって、上の　{ 60, 40, 60 }　というチェイン設定において、４０がレベルに関連する数であり、
この設定だと１回だけ暗号文同士の掛け算を実行することができます。

チェインは精度ビットにも関係する

チェインの真ん中の数はレベルに関連していました。

では、他の数はどうでしょうか。

最初の数、（この場合６０）
間の数（この場合４０）
最後の数（この場合６０）

はそれぞれ役割が違います。
それぞれ

プライマリビット
スケーリングビット
ラストビット

と呼びます。

プライマリビットは、復号時の精度ビットに直接影響します。
60が推奨値であり、設定できる最大の数のようです。
このビットは暗号空間で使用するビットの大きさになります。
実装ではuint64_tを用いるため、60付近が設定できる最大の値であると考えられます。

スケーリングビットとプライマリビットの関係

スケーリングビットとプライマリビットの大きさにより、復号時の実数値の精度が決まります。

スケーリングビットは、大まかに言えば、

小さくすると浮動小数点前の整数部分の許容度が増えるが、浮動小数点後の少数部分の精度が下がる
大きくすると浮動小数点前の整数部分の許容度が減り、浮動小数点後の少数部分の精度が上がる

というトレードオフの関係になっています。

スケーリングビットの例①

例としては

double scale = pow(2.0, 40);
vector<double> modulus_chain = { 60, 40, 60 }

だった場合、暗号化できる整数部分は 60-40=20 bit 程度の許容範囲があり、ここを以下整数部分ビットと呼びます。
暗号化した後の少数部分で保持される精度は最大40-20=20bit 程度になります。ここを以下少数部分ビットと呼びます。
以上の整数部分ビット、少数部分ビットには

計算中に値が整数部分ビット以上になると暗号空間でオーバーフローが起き、オーバーフローが起きるとC言語などでのオーバーフローと同じように値が完全に壊れるということ。
少数部分ビットには暗号に付与されるノイズが付与されるため、実際の精度は20bitより少しだけ小さくなること。

という点において注意が必要になります。

スケーリングビットの例②

double scale = pow(2.0, 50);
vector<double> modulus_chain = { 60, 50, 60 }

とした場合、以下のようになります。

整数部分ビットは、60-50=10bitとなり、以前の20bitのときに比べてオーバーフローが起きやすくなる。（よって演算時にそれが起きないか注意が必要。）
少数部分ビットは、最大50-10=40bit 程度となり、小数点以下の精度に関しては以前より良くなる。

というように、このチェインの設定によって復号時の精度、Leveledなど、
CKKS形式の格子暗号を使用するときに非常に重要な要素をセッティングすることができます。

まとめ

以上のことを考慮し、
CKKS形式の設定を行うときは

自分が準同型暗号を用いて計算したい演算で必要なビット数などを把握
掛け算を実行したい回数をあらかじめ決める

等計算グラフの設定を行い、計算精度が担保されるか少々地味にトラッキングする必要があります。

担保したいセキュリティビットを考慮すること、担保したい掛け算回数（格子暗号のレベルの数）を考慮する点に関しては
格子暗号を用いた計算ならではの少々泥臭い設定と言えるでしょう。

この辺りは少々経験も必要です。
しかしながらSEALから吐き出されるエラーはそこそこ親切に記述されているため、
少しの試行錯誤があれば慣れていくことも可能だと思います。

もし何か修正が必要な箇所や質問等あれば、コメント等いただければ回答できるかもしれません。
みなさんもよいSEALライブラリライフを！

今回はこの辺で。

kenmaro