✅
問題(1)解説
弊社で実際に使われている加法的秘密分散法と言う技術を用いたアルゴリズムを紹介します。
加法的秘密分散法のアイデアを簡単に説明すると、登場人物が 人いる時、他者に知られたくない数 を を満たすように 個の数 個に分割し、 番目の人には だけを配布すると言うものです。
分割された を の Share と呼び、逆に を Share の真値と呼びます。
今回の例に当てはめると、太郎くんは各 に対し を を満たすように二つの数に分割し、花子さんに のみを伝えます。
この時分割の方法は太郎くんしか知らないため、花子さんは から についての情報は一切得ることができません。
同様にして花子さんは 各 に対し を を満たすように二つの数に分割し、太郎くんに のみを伝えます。
次に以下で説明する BMT アルゴリズムを用いて、各 に対し の Share (すなわち が成立)をそれぞれ太郎くんと花子さんに配布します。
最後に、太郎くんと花子さんはそれぞれ と の値を公開します。
この時
より、内積 を求めることが出来ます。
BMT(Beaver Multiplication Triples)
人1が Share 、人2が Share を持っているとします。( が成立)
この時, 各人の持っている数の値を完全に他者に秘密にしたまま、 の Share をそれぞれ人1, 2に配布するアルゴリズムを以下で紹介します。
まず、人1でも人2でもないあなたが を満たす を秘密裏に生成します。
次にそれらをそれぞれ Share に分割し, 人 に に配布します。
人 は Share を受け取り(それぞれ の Share である) を相手に公開します。(あなたには公開されません。あなたの役割は を配布したところまでです。)
この操作によって人が についての情報を一切得ることが出来ないことに注意してください。(例えば人2は を知らないため、公開された の値から の値を求めることが出来ません)
各人は集まった Share と自分の持つ Share を合わせることで の値を復元し, 以下のようにして を求めます。
この時 より が
の Share であることが確認できます。
後ろの等号は普通に計算してもよいですが、以下の図から直感的に理解することも出来ます。
![](https://s3.ap-northeast-1.amazonaws.com/wraptas-prod/acompany-recruit/6432e68c-1bc0-4969-b177-e17c1690ee32/0f1b5546af08bf4131758117882bef18.png)
最後に、BMT における仮定が元の問題設定とは異なっていることに触れておきます。
BMT の仮定で人1は の値を知らないですが、問題の太郎くんは の値を知っています。(花子さんについても同様ですが、二人の持つ情報量は対称的なので太郎くんについてのみ注目しています)
一見すると BMT の方が問題よりも仮定が少ないだけなので、問題を解くために BMT を用いることに特に懸念はないように思えます。
ですが見方を変えると、BMT では「人1は を知らない」と言う問題には無い仮定を置いているとも言えます。
つまり、太郎くんが を知っている状態で BMT を行なっても一連の流れで太郎くんが についての情報を一切得られないことについては再度確認する必要があると言うことです。
このように秘密計算のアルゴリズムを扱う上では、アルゴリズムを動かすのに必要な情報を持っているかだけでなく、アルゴリズムの秘密性を損なわせてしまう類の情報を持っていないかを毎度確認する必要があることに注意しなければなりません。
秘密計算を扱う際はアルゴリズムを学んだりデザインした段階で「アルゴリズムを動かすために各人が初めに持っていなければならない情報」だけでなく「アルゴリズムを動かす段階で各人が追加で持っていても問題ない(それによって新たに秘密情報が何も漏れない)情報」も列挙しておくことが大事です。
参考文献
発展問題
- BMT の特殊ケースとして、二乗の場合(つまり )を考えます。
BMT では三つの数 の Share を配布していましたが、二乗の場合には配布する数を二つに減らすことが可能です。
そのようなアルゴリズムを考えてください。
- 二乗の場合のアルゴリズムを用いて太郎くんと花子さんのために作ったアルゴリズムの効率を改善してください。
ヒント
を用います。
問題(2)に進む