準同型暗号（格子暗号）の鍵と暗号文ってどのくらいのサイズになるの？

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

> - [秘密計算エンジニアを始めて２年半が経った。](https://qiita.com/kenmaro/items/48059dd60f79e80f5ef8)
> - [秘密計算エンジニアを始めて3年が経った。](https://qiita.com/kenmaro/items/a1d90a074d552b7bf886)


## 概要

今回ですが、前回の
「準同型暗号（格子暗号）の演算」ってどのくらい遅くなるの？

https://qiita.com/kenmaro/items/f51ccfe81e4d6886d608

という記事に付随して、

**「準同型暗号（格子暗号）の鍵と暗号文」ってどのくらいのサイズになるの？**

という質問に答えようと思います。

前回と同じく、前提知識はほとんどすっ飛ばして、
実運用できる中で一番小さい鍵や暗号文の構成で測定してみます。

これから「準同型暗号（格子暗号）」ベースの「秘密計算」について調べようとしている方、学生の方
などは参考にしていただければと思います。


## 忙しい人のために

・暗号状態で計算すると、当たり前だけど**データサイズは大きくなる**よ

- **鍵（18MB）**
- **暗号文（0.3MB）**

・ちなみにこれは、かなり小さい暗号パラメータで作った物（実運用は可能）だよ

・これを与えられたアルゴリズムで**どう小さく保ったまま省メモリ演算するか、が秘密計算エンジニアがやっている実装**だよ



## 前提条件（知りたい人だけ）

この前提条件は、前回の記事と全く同じ内容となっています。

以下のライブラリやマシンスペックで今回測ってみます。
あまり興味のない方や、結論だけ教えてくれ〜、という方はスキップしてください。


#### ライブラリ
**Microsoft SEAL** と呼ばれる、世界で今一番使われている（筆者の経験上ですが）格子暗号のライブラリを使用します。
SEALはマイクロソフトのリサーチグループによって開発、メンテナンスされ、**MITライセンスで公開されているOSSライブラリ**です。

おそらく、自分で実際に格子暗号ベースの「暗号状態での演算」を試してみよう、と思った方は、このライブラリに行き着くのではないでしょうか。

筆者はこれまでいくつも格子暗号ベースのライブラリを触ったり、開発に携わってきましたが、

**結局のところ実運用ではマイクロソフトのSEALを多用しています。**

この辺りのライブラリについて知りたい方がいらっしゃいましたら、

https://qiita.com/kenmaro/items/0654ad4d26e7a4dd919b

ここに（もう２年以上前の記事ですが）まとめていますので是非ご覧ください。


#### 暗号形式

**CKKS形式**を使います。

**CKKS形式を使う理由は、端的にいうと一番使いやすいから**です。

SEALライブラリに実装されている暗号形式は、大きく３つあり、

- BFV形式
- BGV形式
- CKKS形式

となっています。

この中で、**CKKS形式はその形式上、実数を暗号化することができます。**
**一方で、BFV、BGV形式は整数のみ暗号化**できます。

ここでは細部に踏み込みませんが、CKKS形式は演算で発生したノイズを演算時のノイズとして解釈します。
したがって、演算を行う（たとえば足し算とか、掛け算とか）と、とても小さいノイズが答えに付加された状態で出力されます。
この辺りの暗号状態での演算精度については、

https://qiita.com/kenmaro/items/931835476ca8781de9f9

ここにまとめているのでもし興味がある方がいらっしゃいましたらご覧ください。

#### セキュリティレベル

セキュリティビットは**128ビット**を使用しています。

#### 暗号パラメータ

ここも前提知識が多くなってしまうので割愛しますが、
現実的に応用を考えたときに必要な精度を暗号状態で担保し、

その中で **「一番演算が軽い設定」
の元で計測をおこなっています。**



#### 使用マシン

私のMacBookProを使います。
スペックは普通のハイエンドのラップトップです。

とは言ってもスレッディングなどを使用するわけではなく、
**１コアでの性能を測定**
するので、スペックはあまり関係ないかもしれません。

参考までに表記します。

```
MacBook Pro (16-inch, 2019)
Processor: 2.3 GHz 8-Core Intel Core i9
memory: 64 GB 2667 MHz DDR4
```


## 測定


### 鍵について

SEALを使ったことがある人は、鍵にもいろいろな種類があることを知っている人がいると思いますが、
今回は全部の鍵をまとめて「鍵」
として計測します。

実際は、

- **秘密鍵 （復号用の鍵）**
- **公開鍵（暗号化用の鍵）**
- **計算用の鍵**
- **ガロア鍵**

などがありますが、今回はこれをまとめて「鍵」と言います。


### 暗号文について

暗号文は、暗号化をすると１つ生成されますので、こちらのサイズを測定していきます。



## 結果

結果は以下の通りとなりました。


#### 鍵

```
18.3 [MB]
```

また、鍵の大きさの内訳ですが、
ガロア鍵が突出して大きく、その他の鍵は比較的小さいです。

**単位はMBです。**

- **秘密鍵 （復号用の鍵） (0.18)**
- **公開鍵（暗号化用の鍵） (0.36)**
- **計算用の鍵 (0.72)**
- **ガロア鍵   (17)**

グラフも一応貼っておきます。

![Screen Shot 2022-05-24 at 14.56.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519792/2d63bb64-32d1-b248-d51c-e1055689940d.png)



#### 暗号文

```
0.235 [MB]
```

という結果になりました。



## まとめ

今回は、

**「準同型暗号（格子暗号）の鍵と暗号文」ってどのくらいのサイズになるの？**

という質問に答えるために、

世界で一番有名な格子暗号ライブラリ「SEAL」
を用いて鍵や暗号文のサイズを計測してみました。

結果は、

**鍵：　18.3 MB**
**暗号文: 0.235 MB**

となりました。

なぜガロア鍵が大きいのかとか、
どうやったら暗号文を小さくできるのか、
運用時にどのように工夫して省メモリ化を達成して実装しているのかなど、
結構面白い分野だと思っています。

その辺をいろいろとごちゃごちゃ普段やっているので、そのあたりも纏めれればと思っています。


**次回はもっと暗号パラメータを変更しつつ、
パラメータが格子暗号の演算速度、データサイズにどう影響するのかについて書けたらなと思っています。**

　
　

今回はこの辺で。


@kenmaro