問題（１）解説

2023/10/13 0:322023/10/30 3:03

弊社で実際に使われている加法的秘密分散法と言う技術を用いたアルゴリズムを紹介します。

加法的秘密分散法のアイデアを簡単に説明すると、登場人物が人いる時、他者に知られたくない数をを満たすように個の数個に分割し、番目の人にはだけを配布すると言うものです。

分割されたをの Share と呼び、逆にを Share の真値と呼びます。

今回の例に当てはめると、太郎くんは各に対しをを満たすように二つの数に分割し、花子さんにのみを伝えます。

この時分割の方法は太郎くんしか知らないため、花子さんはからについての情報は一切得ることができません。

同様にして花子さんは各に対しをを満たすように二つの数に分割し、太郎くんにのみを伝えます。

次に以下で説明する BMT アルゴリズムを用いて、各に対しの Share （すなわちが成立）をそれぞれ太郎くんと花子さんに配布します。

最後に、太郎くんと花子さんはそれぞれとの値を公開します。

この時

より、内積を求めることが出来ます。

BMT（Beaver Multiplication Triples）

人1が Share 、人2が Share を持っているとします。（が成立）

この時, 各人の持っている数の値を完全に他者に秘密にしたまま、の Share をそれぞれ人1, 2に配布するアルゴリズムを以下で紹介します。

まず、人1でも人2でもないあなたがを満たすを秘密裏に生成します。

次にそれらをそれぞれ Share に分割し, 人にに配布します。

人は Share を受け取り（それぞれの Share である）を相手に公開します。（あなたには公開されません。あなたの役割はを配布したところまでです。）

この操作によって人がについての情報を一切得ることが出来ないことに注意してください。（例えば人2はを知らないため、公開されたの値からの値を求めることが出来ません）

各人は集まった Share と自分の持つ Share を合わせることでの値を復元し, 以下のようにしてを求めます。

この時よりがの Share であることが確認できます。

後ろの等号は普通に計算してもよいですが、以下の図から直感的に理解することも出来ます。

最後に、BMT における仮定が元の問題設定とは異なっていることに触れておきます。

BMT の仮定で人1はの値を知らないですが、問題の太郎くんはの値を知っています。（花子さんについても同様ですが、二人の持つ情報量は対称的なので太郎くんについてのみ注目しています）

一見すると BMT の方が問題よりも仮定が少ないだけなので、問題を解くために BMT を用いることに特に懸念はないように思えます。

ですが見方を変えると、BMT では「人1はを知らない」と言う問題には無い仮定を置いているとも言えます。

つまり、太郎くんがを知っている状態で BMT を行なっても一連の流れで太郎くんがについての情報を一切得られないことについては再度確認する必要があると言うことです。

このように秘密計算のアルゴリズムを扱う上では、アルゴリズムを動かすのに必要な情報を持っているかだけでなく、アルゴリズムの秘密性を損なわせてしまう類の情報を持っていないかを毎度確認する必要があることに注意しなければなりません。

秘密計算を扱う際はアルゴリズムを学んだりデザインした段階で「アルゴリズムを動かすために各人が初めに持っていなければならない情報」だけでなく「アルゴリズムを動かす段階で各人が追加で持っていても問題ない（それによって新たに秘密情報が何も漏れない）情報」も列挙しておくことが大事です。

BMT では三つの数の Share を配布していましたが、二乗の場合には配布する数を二つに減らすことが可能です。

そのようなアルゴリズムを考えてください。

ヒント

を用います。