前置き

ここではASIA CCS 2018で発表した離散対数ベースの準同型暗号（英語の発表資料, SCIS2018での日本語の資料）を紹介します。
準同型暗号には、他に素因数分解ベース、格子ベースなどいくつか種類がありますが、他の方式については触れないのでご了承ください。

初めに

準同型暗号

まず準同型暗号について軽く説明しましょう。
インターネットなどでよく使われている暗号（AESやRSA暗号など）は、データを暗号化し、その暗号文を復号するという機能しかありません。
しかし、クラウド上でデータを隠したまま様々な処理をさせたり、仮想通貨でお金の入出金を隠したまま決済したいなどのニーズが増えています。
それを実現するために考えられている暗号の一つが準同型暗号です。

準同型暗号を使うと、秘密鍵を持たない人が公開鍵を使って暗号文のまま計算できます。

暗号化を「数字をカプセルに入れる操作」に見立てると、準同型暗号はカプセルを開けずにカプセル同士をぶつけることで中の数字を掛けたり足したりした結果の数字が入ったカプセルを作り出します。

「準同型」とは数学の用語で、ある操作をしてから足したり掛けたりしたものが、足したり掛けたりしてからある操作をしたものと同じときにそう呼びます。

ある操作をf(x)とすると、
f(x) + f(y) = f(x + y)
f(x) * f(y) = f(x * y)
を満たすときにfが準同型であるというのです。準同型暗号の場合、fは暗号化処理にあたります。

準同型暗号の種類

準同型暗号にはいくつか種類があります。
暗号文の足し算だけが出来る加法準同型暗号。それから足し算と掛け算の両方が出来る完全準同型暗号です。
足し算と掛け算が出来るだけで「完全」とは仰々しく思えるかもしれませんが、0と1の世界では足し算と掛け算を組み合わせることで任意の処理ができることが知られています。そのため「完全」と呼ばれているのです。

完全準同型暗号はとても便利なのですが、現時点では演算処理、暗号文サイズが非常に大きく、実用するにはなかなか難しいところがあります（研究は日夜進んでいるので数年前に比べて相当効率がよくなってきてはいます）。

種類	加法準同型	somewhat準同型	完全準同型
速度	○（速い）	△	×（遅い）
暗号文サイズ	○(小さい)	△	×（大きい）
機能	△（加法のみ）	○（乗法に制限あり）	◎（任意の操作）

そこで加法準同型暗号と完全準同型暗号の中間の暗号（somewhat準同型暗号あるいはleveled準同型暗号）が研究されています。somewhat準同型暗号は暗号文同士の演算回数に制約を設けることで効率のよい処理を目指します。
今回提案した暗号は足し算は任意回、乗算は1回だけ可能なL2準同型暗号と呼ばれるクラスに属します。

乗算が1回しか出来なくても、複数の暗号文の平均値や分散、内積、最小二乗法などができます。うまく使えばなかなか便利な暗号です。

加法準同型暗号を使った例としては加法準同型暗号を用いて暗号化したまま画像のエッジ検出をするも参照ください。

なお、加法性を使うだけでも
$Enc(x) + Enc(x) = Enc(2x)$,
$Enc(2x) + Enc(x) = Enc(3x)$,...
なので適当な整数$n$に対して$nEnc(x) = Enc(nx)$を計算できることに注意してください。
「乗算ができる」というのは暗号文同士を掛けられるという意味です。

提案方式の特長

今回発表した方式の特長は次の通りです。

L2準同型暗号の中で最も高速で秘密鍵や、暗号文のサイズが小さい。
比較的よく使われる安全性仮定の下で安全性を証明した。
離散対数ベースなのでゼロ知識証明との組み合わせがしやすい。

更に提案アルゴリズムのC++/asm/WebAssemblyによる実装をしています。

WebAssembly（wasm）によるデモ

能書きはそれぐらいにしてデモを見てみましょう。
デモはクライアントで暗号化したデータをサーバに転送し、サーバ側で暗号化したまま積和演算してクライアントに返し、クライアントではその値を復号するシーンを再現します。クライアント、サーバは画面上に擬似的に表示しているだけで、実際にどこかに通信しにいくわけではありません。
Chrome, Firefox, Safariなどの最近のブラウザ（IE除く）で動きます。iPhoneやAndroid上でも動作します。
さらっと書いてますが、準同型暗号がブラウザで動くのは世界初なんじゃないかと思います。

ブラウザのコンソールで試してみる

上記デモが動作することが確認できたら、開発者モード（F12など）のコンソール画面を開いてみましょう。
予めグローバル関数用のshe、秘密鍵sec、公開鍵pubが定義されています。
コンソールで次のようにして試してみましょう。

c1 = pub.encG1(2) // 公開鍵pubで2をG1暗号化
c2 = pub.encG1(4) // 公開鍵pubで4をG1暗号化
c1.dump() // 暗号文を表示
c2.dump()
c3 = she.add(c1, c2) // c1とc2を加算して新しい暗号文c3を作る
c3.dump()
sec.dec(c3) // 秘密鍵secでc3を復号

最後に2と4の和である6が表示されます。
今回の提案方式では乗算はG1暗号化とG2暗号化同士でしかできません。
そのため掛け算は次のようにします。

c1 = pub.encG1(2) // 公開鍵pubで2をG1暗号化
c2 = pub.encG2(4) // 公開鍵pubで4をG2暗号化
c3 = she.mul(c1, c2) // c1とc2を乗算して新しい暗号文c3を作る
c3.dump()
sec.dec(c3) // 秘密鍵secでc3を復号

今度は2と4の積である8が表示されます。

詳細はライブラリの説明書をごらんください。実装はmcl/she.hppです。

応用例

雰囲気が分かったところでいくつか基本的な応用例を紹介しましょう。

電子投票

準同型暗号を使って匿名でアンケート結果の集計をします。

まず集計したい人（A）が公開鍵をみんなに配ります。
アンケートに答える人はそれぞれ賛成（1）または反対（0）を暗号化し、集計サーバに送信します。
集計サーバは暗号文のまま全ての値を足してからその結果を（A）に渡します。
（A）は復号して賛成数を得ます。

ここでいくつか注意点があります。

暗号文から元のデータの情報は何も漏れません。この例では集計サーバは$c_1$と$c_2$、あるいは$c_0$と$c_3$を見ても、それらが同じ値を暗号化したということが分かりません。
仮に4番目の人が「2」を暗号化して送信したら結果がおかしくなってしまいます。この例ではアンケートに答える人は0か1のどちらかしか暗号化してはいけません。そのためにはゼロ知識証明と呼ばれる技術を使います。ゼロ知識証明を使うと集計サーバはある暗号文が「0か1のどちらかを暗号化したものである」ということを検証し、そうでなければ不正とみなして拒絶できます。
このモデルでは集計サーバと（A）が結託（=グル）しないことを仮定します。それができない場合はまた別途対策が必要です。

紛失通信（Oblivious Transfer）

紛失通信とはAさんとBさんの間のプロトコルで、Bさんがn個のテーブルtblを持っているとき

Aさんはi番目のテーブルの値tbl[i]を得るが、他のテーブルの値は得られない
BさんはAさんが何番目の値を取ろうとしたか分からない

という性質を持ちます。

なかなか奇妙な性質ですが、Bさんをデータベースとみなすとクエリ内容を教えずにデータベースのクエリの結果を得る方法とみなせます。
紛失通信の構成方法の一つに準同型暗号を使うやり方があります。

Aさんはk番目だけ1で他は0のn次元ベクトルの各要素を暗号化したn個の暗号文$\{Enc(k_i)\}$をBさんに送ります。
Bさんは$c=x_0 * Enc(k_0) + x_1 * Enc(k_1) + ... + x_{n-1} * Enc(k_{n-1})$を計算してAさんに送ります。
準同型性から$c=Enc(x_0 * k_0 + x_1 * k_1 + ...)=Enc(x_i)$なのでAさんは復号して$x_i$を得ます。

この例でもBさんがAさんが不正をしないように防御したいことがあります。
たとえば$x_i$の範囲が8bit以内と分かっているなら、Aさんは$\{Enc(1), Enc(256), Enc(0), Enc(0), ...\}$を送るとBさんは$Enc(x_0 + 256x_1)$を返してしまうので、Aさんは$x_0$と$x_1$の2個の情報を得られてしまいます。

これを防ぐには電子投票のときと同じく暗号文が0か1のどちらかであることを検証できるゼロ知識証明が必要です。
このように準同型暗号では応用上、暗号文に対する制約が必要なケースがよくあります。

次回

ここまで一般的な準同型暗号のはなしでした。
次に準同型暗号の最前線2（原理編）では提案した方式のアイデアを紹介しましょう。