問題（１）

2023/10/13 0:312023/10/31 2:59

太郎くんは次元ベクトルを持っています。

花子さんは次元ベクトルを持っています。

二人は二つのベクトルの内積を知りたいと思っています。

ただし太郎くんはの値を花子さんと共有することを除いて、 についての情報を花子さん含め他者に一切知られたくありません。（具体的な値だけでなく、例えばの偶奇性のような少しの情報も知られてはいけません）

花子さんも同様に、の値を太郎くんと共有することを除いて、 についての情報を太郎くん含め他者に一切知られたくありません。

二人の希望を実現するアルゴリズムを考えてください。

まず次元ベクトルはここでは単に数 つ組みのことです．

例えばの場合であれば太郎くんがのような数4つ組みを持ち、花子さんも同様にのような数4つ組みを持っていると考えてください。

そして内積は二人の持つ4つ組みの同じ場所に位置する数同士を掛け算した値の合計ことです。

例えば上の例だとなので、二人が「お互いの持っている4つ組みの同じ場所に位置する数同士を掛け算した値の合計が」と知ることがゴールになります。

もちろん花子さんが太郎くんに「私の持っている数はです」と伝えられれば太郎くんは自分で計算してを求めることが出来ますが、二人とも自分の持ってる値を一切明かさずにこの値を求める方法は？というのが本問題になります。