Help us understand the problem. What is going on with this article?

格子暗号とマルチキー

概要

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

参考文献

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

という論文です。

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

大枠の内容

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

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

などを挙げています。

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

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

Common Reference String (CRS) modelを仮定したスキームとして、以下のステップに沿います。
Screen Shot 2019-12-28 at 13.31.51.png
ここでの共通ベクトルの$a$の導出は、
Screen Shot 2019-12-28 at 13.33.34.png

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

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

実装結果として、各鍵の生成に要した時間を、BFV, CKKS形式の各パラメータ毎に示しています。
Screen Shot 2019-12-28 at 14.57.58.png
Screen Shot 2019-12-28 at 14.58.15.png

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

まとめ

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

おわり。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした