@kenmaroです。
普段は主に秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。
概要
今回ですが、シンプルに、
「準同型暗号（格子暗号）の演算」ってどのくらい遅くなるの？
という質問に答えようと思います。
いろいろな前提知識はすっ飛ばして、速度のみピンポイントで計測してみますので、
これから「準同型暗号（格子暗号）」ベースの「秘密計算」について調べようとしている方、学生の方
などは参考にしていただければと思います。
忙しい人のために
・暗号状態で計算すると、当たり前だけど速度はとても遅くなるよ
- 足し算（630倍）
- 掛け算（4300倍）
・これを与えられたアルゴリズムでどう効率良く計算するか、が秘密計算エンジニアがやっている実装だよ
前提条件（知りたい人だけ）
以下のライブラリやマシンスペックで今回測ってみます。
あまり興味のない方や、結論だけ教えてくれ〜、という方はスキップしてください。
ライブラリ
Microsoft SEAL と呼ばれる、世界で今一番使われている（筆者の経験上ですが）格子暗号のライブラリを使用します。
SEALはマイクロソフトのリサーチグループによって開発、メンテナンスされ、MITライセンスで公開されているOSSライブラリです。
おそらく、自分で実際に格子暗号ベースの「暗号状態での演算」を試してみよう、と思った方は、このライブラリに行き着くのではないでしょうか。
筆者はこれまでいくつも格子暗号ベースのライブラリを触ったり、開発に携わってきましたが、
結局のところ実運用ではマイクロソフトのSEALを多用しています。
この辺りのライブラリについて知りたい方がいらっしゃいましたら、
ここに（もう２年以上前の記事ですが）まとめていますので是非ご覧ください。
暗号形式
CKKS形式を使います。
CKKS形式を使う理由は、端的にいうと一番使いやすいからです。
SEALライブラリに実装されている暗号形式は、大きく３つあり、
- BFV形式
- BGV形式
- CKKS形式
となっています。
この中で、CKKS形式はその形式上、実数を暗号化することができます。
一方で、BFV、BGV形式は整数のみ暗号化できます。
ここでは細部に踏み込みませんが、CKKS形式は演算で発生したノイズを演算時のノイズとして解釈します。
したがって、演算を行う（たとえば足し算とか、掛け算とか）と、とても小さいノイズが答えに付加された状態で出力されます。
この辺りの暗号状態での演算精度については、
ここにまとめているのでもし興味がある方がいらっしゃいましたらご覧ください。
セキュリティレベル
セキュリティビットは128ビットを使用しています。
暗号パラメータ
ここも前提知識が多くなってしまうので割愛しますが、
現実的に応用を考えたときに必要な精度を暗号状態で担保し、
その中で 「一番演算が軽い設定」
の元で計測をおこなっています。
使用マシン
私のMacBookProを使います。
スペックは普通のハイエンドのラップトップです。
とは言ってもスレッディングなどを使用するわけではなく、
１コアでの性能を測定
するので、スペックはあまり関係ないかもしれません。
参考までに表記します。
MacBook Pro (16-inch, 2019)
Processor: 2.3 GHz 8-Core Intel Core i9
memory: 64 GB 2667 MHz DDR4
測定内容
実際に以下のプロセスの実行時間を測定してみます。
- 鍵生成
- 暗号化
- 復号
- 暗号同士の足し算
- 暗号同士の掛け算
- 暗号のシリアライズ
- 暗号のデシリアライズ
このうち、最後の二つは本質とはずれますが、
実際のシステムを考える際には、暗号文はクライアント側で生成され、サーバ側に送信されますので、
シリアライズ（つまりバイト配列にする）工程と、
デシリアライズ（バイト配列から戻す）工程がオーバーヘッドとしてかかってきます。
そのため、念の為測定してみます。
なお、測定は３０回実行した時の平均値を取っています。
また、単位は全て[秒] です。
結果
結果は以下の通りとなりました。
鍵生成
0.117
暗号化
0.0054
復号
0.0012
暗号同士の足し算
0.00030
暗号同士の掛け算
0.0041
暗号のシリアライズ
0.00074
暗号のデシリアライズ
0.0011
結果のグラフ
結果のプロットをします。
鍵の生成が圧倒的に大きいので、一旦そのほかでプロットしてみます。
参考（平文比）
参考までに、平文で（普通にPythonで）
- 足し算（１＋１）
- 掛け算（2 * 3）
もやって演算時間を測定してみます。
1 + 1
4.764e-07
2 * 3
9.53e-07
となりました。
したがって、単純な平文、暗号文での演算時間比は、
足し算
630倍
掛け算
4300倍
という結果になりました。
まとめ
今回は、
「準同型暗号の演算」ってどのくらい遅くなるの？
という質問に答えるために、
もっとも有名な格子暗号ライブラリ「SEAL」
を用いて各演算の実行時間測定をしてみました。
結果は、
足し算で630倍、
掛け算で4300倍
という結果になりました。
この数百倍から数千倍をどう捉えるかは人によって違うと思いますが、
実際はこの暗号文にうまく複数の数字を入れることによって、「全体としての演算時間」
を効率化（高速化）することが可能です。
その辺をいろいろとごちゃごちゃ普段やっているので、そのあたりも纏めれればと思っています。
また、次回は、
「準同型暗号の暗号文サイズ」について簡単にまとめようと思います。
今回はこの辺で。