加法準同型暗号を用いて暗号化したまま画像のエッジ検出をする

# 初めに
ペアリング暗号ライブラリ[mcl](https://github.com/herumi/mcl)は楕円曲線も扱えます。そして加法準同型暗号の一つであるLifted-ElGamal暗号の機能を持っています。
今回はLifted-ElGamal暗号を用いて、OpenCVで取得したカメラ画像のエッジ検出を暗号化したまま行うデモを紹介します。

# 加法準同型暗号
準同型暗号とは暗号化したまま様々な処理が行える暗号です。
加法準同型暗号とは準同型暗号のうち、特に足し算と引き算だけが行える暗号です。

```math
Enc(a) + Enc(b) = Enc(a + b),\\
Enc(a) - Enc(b) = Enc(a - b)
```

「え～足し算だけ」と思われるかもしれませんが、$Enc(a) + Enc(a) = Enc(2a)$, $Enc(2a) + Enc(a) = Enc(3a)$ですから、平文$n$による整数倍

```math
n Enc(a) = Enc(na)
```

はできます。
加法準同型の詳細は「[暗号文のままで計算しよう - 準同型暗号入門 -](https://www.slideshare.net/herumi/ss-59758244)」を参考にしてください。

# デモの構成
クライアントでデータを暗号化し、サーバで暗号化したままデータを処理（エッジ検出）してもらいます。
今回はエッジ検出ですが、いろいろな計算をサーバに移譲することが考えられます。
<img width="512" alt="model.png" src="https://qiita-image-store.s3.amazonaws.com/0/11872/20b686c2-f49f-9263-53f3-47873200f8f2.png">

# 通常のエッジ検出
画像のエッジ（境界）を検出する方法を紹介します。
エッジはその付近と大きく値が変わっている場所です。
ある点Pに着目するとその点に隣接する値の差が大きいということです。
点Pと上下左右に隣接する点をU, D, L, Rとするとそれぞれの差

```math
(U - P) + (D - P) + (L - P) + (R - P) = U + D + L + R - 4P
```
となります（0以下になったり256以上になるとクリッピングする）。

<img width="515" alt="edge.png" src="https://qiita-image-store.s3.amazonaws.com/0/11872/66bb4ee8-2089-1024-0d4b-95d4001351de.png">

これを各点について計算すればエッジ検出できます。
画像の横幅をwとすると点iに関して右はi + 1, 左はi - 1, 上はi - w, 下はi + wの位置になるのでコード的には次のようになります。

```C++
void getEdge(uint8_t *dst, const uint8_t *src, size_t w, size_t h)
{
	for (size_t y = h - 2; y > 0; y--) {
		for (size_t x = w - 2; x > 0; x--) {
			int v = src[x + y * w] * (-4) + src[x + y * w - 1] + src[x + y * w + 1] + src[x + (y - 1) * w] + src[x + (y + 1) * w];
			v = (v < 0) ? 0 : (v > 255) ? 255 : v;
			dst[x + y * w] = 255 - uint8_t(v);
		}
	}
}
```

# ライブラリの初期化
加法準同型暗号を使うために`mcl/ahe.hpp`をincludeします。192bit/256bitの楕円曲線暗号を使えます。今回はなるべく軽くするために192bit（NIST_P192）を使います。
includeするまえに`MCL_USE_AHE192`を定義してください。

```C++
#define MCL_USE_AHE192
#include <mcl/ahe.hpp>
```

`using namespace mcl:ahe192`したあと

```C++
	initAhe();
	SecretKey sec;
	initSecretKey(sec);
	const int range = 4 * 256;
	sec.setCache(-range, range);
```

で秘密鍵を作ります。setCacheは復号する値の範囲設定をします。Lifted-ElGamal暗号は復号できる範囲が決まっているため、予め範囲を指定する必要があります。今回はモノクロ8bitの値を精々4倍するだけなので`sec.setCache(-1024, 1024)`としました。

# 暗号化したままエッジ検出
通常のエッジ検出を暗号化したまま行います。
処理を簡単にするためクライアント側でキャプチャした画像をモノクロ化し、各点を暗号化します。

```math
c = Enc(p)
```

画像の全点を暗号化したら、その暗号化ベクトルctvをサーバに送ります。
サーバで暗号化したままエッジ検出アルゴリズムを実行します。

```math
Enc(U) + Enc(D) + Enc(L) + Enc(R) - 4Enc(P)
```

対応するmclライブラリでのコードは

```C++
typedef std::vector<CipherText> CipherTextVec;
void getEncEdge(CipherTextVec& edge, const CipherTextVec& encY, size_t w, size_t h)
{
	edge.resize(w * h);
	for (size_t y = h - 2; y > 0; y--) {
		for (size_t x = w - 2; x > 0; x--) {
			size_t i = x + y * w;
			CipherText& t = edge[i];
			t = encY[i];
			t.mul(-4);
			t.add(encY[i + 1]);
			t.add(encY[i - 1]);
			t.add(encY[i + w]);
			t.add(encY[i - w]);
		}
	}
}
```

です。
encYがクライアントから送られてきた暗号化された画像でedgeが暗号化したままエッジ検出をした結果です。`i`番目の位置の入力値`encY[i]`を`mul(-4)`で-4倍し、`add(encY[...])`で隣接する4点の値を暗号化したまま加算します。
これをクライアントに戻して、クライアント側で復号します。

```C++
void decVec(uint8_t *p, size_t  n, const CipherTextVec& ctv, const SecretKey& sec)
{
	for (size_t i = 0; i < n; i++) {
		int v = sec.dec(ctv[i]);
		v = (v < 0) ? 0 : (v > 255) ? 255 : v;
		p[i] = uint8_t(255 - v);
	}
}
```

# サンプルコード
今回はWindows環境のみで動作確認していますがおそらく（多少の修正で）Linux環境でも動くと思います。
[ahe-demo](https://github.com/herumi/ahe-demo)に置きました。
[mcl](https://github.com/herumi/mcl)をcloneしたディレクトリと同じディレクトリにcloneしてください。

```
md work
git clone git@github.com:herumi/xbyak
git clone git@github.com:herumi/cybozulib
git clone git@github.com:herumi/cybozulib_ext
git clone git@github.com:herumi/mcl
git clone git@github.com:herumi/ade_demo
```

USBカメラで画像を取得して表示するためにOpenCV 3.1を使っています。そちらも各自インストールしてください。インストールできたら`ade_demo/mk.bat`の`OPENCV_INC`と`OPENCV_LIB`をOpenCVをインストールしたディレクトリに修正して`mk.bat`を実行してください。

まず`server.exe`を実行し、次にクライアントアプリの`main.exe`を実行するとUSBカメラで取得した画像を表示するウィンドウが開きます（処理時間の都合で小さいです。すいません）。

キー操作は次の通りです。

- q : 終了
- t : 通常のエッジ出力（トグルで元に戻ります）
- e : その瞬間の画像を暗号化してserverに送ります。serverがエッジ検出してmainに戻し、そこで復号して表示します。しばらくお待ちください。
- c : 動きを再開します。

# まとめ
足し算しかできない加法準同型暗号でも意外とできることは多いです。
ガウシアンフィルタも単に、各点に重みを掛けて足すだけなので暗号化したまま処理できると思います（計算時間はかかりますが）。興味ある方は試してみてください。