📝
問題(1)
太郎くんは 次元ベクトル を持っています。
花子さんは 次元ベクトル を持っています。
二人は二つのベクトルの内積 を知りたいと思っています。
ただし太郎くんは の値を花子さんと共有することを除いて、 についての情報を花子さん含め他者に一切知られたくありません。(具体的な値だけでなく、例えば の偶奇性のような少しの情報も知られてはいけません)
花子さんも同様に、 の値を太郎くんと共有することを除いて、 についての情報を太郎くん含め他者に一切知られたくありません。
二人の希望を実現するアルゴリズムを考えてください。
![](https://s3.ap-northeast-1.amazonaws.com/wraptas-prod/acompany-recruit/fb1d9a1e-a204-4bce-a3fc-b9f0f7ad6df1/84998e83b12c5c64075132688dc532a5.png)
数式に慣れていない人向けの補足
まず 次元ベクトルはここでは単に数 つ組みのことです.
例えば の場合であれば太郎くんが のような数4つ組みを持ち、花子さんも同様に のような数4つ組みを持っていると考えてください。
そして内積は二人の持つ4つ組みの同じ場所に位置する数同士を掛け算した値の合計ことです。
例えば上の例だと なので、二人が「お互いの持っている4つ組みの同じ場所に位置する数同士を掛け算した値の合計が 」と知ることがゴールになります。
もちろん花子さんが太郎くんに「私の持っている数は です」と伝えられれば太郎くんは自分で計算して を求めることが出来ますが、二人とも自分の持ってる値を一切明かさずにこの値を求める方法は?というのが本問題になります。
問題(1)解説2023/10/13 0:322023/10/30 3:03