概要

かなり学術よりの論文にはなりますが、マイクロソフトリサーチは格子暗号ベースの準同型暗号を用いたライブラリ開発に力を入れています。
そのなかで、秘密計算の応用先としてかなりニーズが高いものが、「マルチキー」を用いた格子暗号です。これは、複数のデータオーナーがそれぞれ異なる秘密鍵を持ちデータを暗号化して共有した際に、別々の鍵で暗号化されたデータ同士の演算を行うことができる工夫のことです。これにより、暗号化してデータ共有をし、その共有されたデータを１つのビッグデータとして解析を行いつつ、計算結果をデータオーナー同士の同意のもとで復号できます。その結果、複数のデータオーナーはもともと秘密鍵を共有する必要がなく、共有するデータを共有先に見られる心配はありません。あくまでもオーナー同士で同意して復号される対象は、お互いの暗号文を計算した結果出てくる暗号文です。

参考文献

今回読んで見たのが、マイクロソフトリサーチ発の、

Efficient Multi-Key Homomorphic Encryption
with Packed Ciphertexts with Application
to Oblivious Neural Network Inference

という論文です。

細かいところまで書いていくと大変なことになるので、それぞれの詳しい話は別記事にいつかまとめるとして、大枠をかいつまんで書きます。興味のある方は原論文をぜひ読んで見てください。

大枠の内容

SEALで実装されているBGVとCKKSの２つの格子暗号スキームにおいて、マルチキーを用いた時のRelinearlizationの新しい手法を考案した。
Proof of Concept として、SEALを用いてこの２つのスキームにマルチキー計算をするプログラムを実装した。（オープンにはしていない）
ベンチマークとして、MNISTを使った機械学習モデルの推論をマルチキーで行なった。このときの構成は、手書き数字の画像を持っているデータオーナーと、機械学習モデルをもっているモデルオーナーがそれぞれ別々の鍵でデータを暗号化してクラウド上に置き、MNISTの推論をマルチキー計算で行った時のパフォーマンス評価である。

イントロでは、MPCで複数のデータオーナーが入力を暗号化した後に、既存のプロトコルで計算を行い、演算関数の出力結果だけがデータオーナーに返されるシステムでの、サーバー間コミュニケーションの増大によるデメリットに言及した後、HEでのマルチキーアプローチについて議論しています。基本的に既存の実装ではマルチキーの実装はなく、理論的にも２つ程度の論文がマルチキーにフォーカスしており、それらはBGV形式のマルチキーに取り組んでいる、と書いています。

彼らの貢献として、

始めてマルチキーの具体的な実装を行なったこと、
BGV形式だけでなくCKKS形式に関してもマルチキーでの手法を確立したこと、
Relinearizationの手法が既存の手法よりよりシンプルで高速なこと

を挙げています。

基本的に、論文のメインポイントは複数パーティがそれぞれ別の鍵を使って暗号化したデータに対して乗算をしたとき、どうやってRelinearizationを行うか、それのプロトコルづくりに終始しています。

また、先行研究としては

Li, N., Zhou, T., Yang, X., Han, Y., Liu, W., Tu, G.: Efficient multi-key fhe with short extended ciphertexts
and directed decryption protocol. IEEE Access 7, 56724–56732 (2019)
Chen, L., Zhang, Z., Wang, X.: Batched multi-hop multi-key FHE from Ring-LWE with compact ciphertext extension. In: Theory of Cryptography Conference. pp. 597–627. Springer (2017)

などを挙げています。

ここに書いてあるように、まずはマルチキー形式での演算をできるようにすることを最初の取り組みとしており、Relinearization ではシングルキーのときには$sk^2$ を$sk$のもとで暗号化したものが必要で、それをKeySwitchに使っていたように、マルチキー形式ではパーティの数だけ並んだ秘密鍵のテンソル積に対してRelinearizationを行う準備が必要だと言っています。これを実現するために、Common Reference String (CRS) modelというものを仮定し、全パーティメンバで共通のベクトル$a$を共有しておきます。そしてそれぞれのパーティメンバーは$a$を元にしてそれぞれのEvaluation Keyを作り、これおを$D$とします。また、それぞれのパーティから公開鍵として公開されている$b$とこの$D$を用いて行列$K$を生成し、マルチキーでの暗号文同士を乗算して出てきたテンソル積のKeySwithchingを行います。

これをベースとして、２つの手法でRelinearizationを実施する手法を解説してありますが、本質的にやっていることは違いがなく、$K$を作って保持しておくか、Relinearizationをするタイミングで$K$に相当するものを一回一回演算して使うか、という違いになります。

Common Reference String (CRS) modelを仮定したスキームとして、以下のステップに沿います。

ここでの共通ベクトルの$a$の導出は、

のように書かれていますが、書いてある通り、この手法はGSWなどでも使われる比較的普通の手法です。（例えばBitDecompositionなど）

復号の際には、下に書かれている通り、各ユーザが対応した暗号文をそれぞれの鍵で復号し、それらを持ち寄って和をとることで復号プロセスを実行しています。

実装結果として、各鍵の生成に要した時間を、BFV, CKKS形式の各パラメータ毎に示しています。

さらに、実装のベンチマークとして、MNISTデータセットの推論をマルチキー形式で行なっています。この際、入力画像をもつデータオーナーと、モデルをクラウドにおいているサービスプロバイダーが別々の鍵でデータを暗号化し推論を行なっている、というシナリオになっています。

まとめ

秘密計算を行う際に、異なるパーティ間でデータの共有を行いたい、というのは大きなモチベーションの１つです。FHEでこれを実現するためのマルチキー形式が実装され始めているということは大きな成果だと思います。実装されているコード自体は提供されてはいませんが、近い将来にSEALライブラリにも実装新しい昨日の１つとして実装されてくることでしょう。それは大変楽しみなことで、ユースケースがさらに拡張されそうです。今回はこの辺で。

おわり。