LoginSignup
1
1

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-06-20

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

勝手に秘密計算アドベントカレンダーについて

この記事は

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

概要

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

「レベル」準同型暗号とは

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

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

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

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

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

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

レベルと実行速度の関係

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

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

レベル準同型暗号と最適化

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

  • どういう計算をするか把握
  • 何回乗算が発生するか理解
  • 適切な「レベル」を持った暗号パラメータを設定
  • 暗号状態での演算を実装

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

どのくらいレベルによって実行時間が変化するか

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

ここでは、実際にレベル1〜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

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

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

まとめ

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

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

今回はこの辺で。

@kenmaro

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1