「レベル」準同型暗号によるレベルと演算速度の関係 #秘密計算

@kenmaroです。
普段は主に秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。

秘密計算エンジニアを始めて２年半が経った。

秘密計算エンジニアを始めて3年が経った。

この記事は

の「4日目」の記事
としようかと思っています。
興味のある方はアドベントカレンダー参加してみませんか？
ご連絡お待ちしております。

概要

今回ですが、シンプルに、
「レベル」準同型暗号（格子暗号）の演算について計算速度を簡単に測定してみようと思います。

幾度となく言及してきましたが、マイクロソフトリサーチが開発、メンテナンスしている
マイクロソフト SEALは、BFV形式、BGV形式、CKKS形式の格子暗号が実装されています。

このいずれの形式も、「レベル」準同型暗号と呼ばれます。
英語では、Leveled homomorphic encryption　です。

この「レベル」がどういう意味かというと、乗算の回数を「レベル回」までに限定した準同型暗号という意味です。

例を挙げた方がわかりやすいと思います。
たとえば、暗号状態である計算を実行したいときに、掛け算を２回する必要があります。
その時は、レベル「２」の鍵ペアを生成します。

レベル「２」の鍵を生成すると、この鍵で暗号化された暗号は、２回乗算を行うことが可能です。
それ以上の乗算を実行しようとするとエラーとなります。

このレベルは、理論上いくらでも大きくすることができます。
たとえば、レベル「１０」とすると、暗号化した後に１０回掛け算を行うことが可能な暗号を生成可能です。

以上の話を聞くと、設定時の「レベル」は大きい方が便利な気がします。
暗号状態で「１回」しか乗算できない「レベル１」の暗号を生成するよりも、
暗号状態で「５回」乗算できる「レベル５」の暗号を生成した方が便利ですよね。

しかし、レベルの大きさは演算速度に大きく影響してしまいます。
基本的には「レベルの大きさ」は実行時間とトレードオフの関係にあります。
レベルが大きい暗号は、生成に時間もかかりますし、乗算などを実行するときにも大きな時間がかかってしまうのです。

以上のことから、準同型暗号（ここでは格子暗号での話です）を用いた演算を実装するときに、以下のプロセスが必要となります。

例えば、暗号状態で行いたい演算に、乗算が「２回」含まれているとすると、
生成するべき暗号のレベルは「２」となります。
レベル１の暗号を生成しては計算を最後まで実行できませんし、
レベル２が必要である際に、レベル３の暗号をわざわざ作って実行速度を低下させるメリットはないからです。

ここまでで、準同型暗号（格子暗号）を用いた演算を実装する時は、
演算にどのくらいのレベルが必要なのかについてきちんと把握しておく必要がある、ということを理解していただけたかと思います。

ここでは、実際にレベル１〜6の鍵ペアをSEALライブラリを用いて生成し、それぞれの設定で

の実行時間について計測してみたいと思います。

以下に結果をまとめています。
単位は全て（秒）です。

レベル	鍵生成	暗号化	復号	加算	乗算	回転	シリアライズ	デシリアライズ
1	0.12	0.005	0.0014	0.0003	0.0045	0.0013	0.0008	0.001
2	0.213	0.007	0.0021	0.0004	0.007	0.0025	0.003	0.0015
3	0.72	0.020	0.006	0.0012	0.021	0.009	0.009	0.0034
4	1.04	0.023	0.0077	0.0015	0.027	0.0125	0.012	0.0044
5	1.41	0.027	0.0096	0.0018	0.034	0.016	0.015	0.005
6	1.87	0.030	0.011	0.0021	0.041	0.022	0.017	0.0055

先述の通り、レベルの大きな暗号パラメータを使用するにつれて、
各演算の実行速度が増加していることがわかると思います。

ざっくりですが、レベル１からレベル５になると、全ての演算は１０倍程度になるということがわかりました。

今回は、「レベル」準同型暗号の演算について、各演算の実行速度がレベルの変化に伴ってどのように変化するか、
ということについてまとめました。

準同型暗号を用いた演算を考える時は、一度この表を見ることで実行時間の見積りができる可能性がありますので、
ぜひ参考にしてみてください。

今回はこの辺で。