問題(2)解説


問題(1)の解説と同様に加法的秘密分散法を用います。
もし加法的秘密分散法を知らない方は先に問題(1)の解説をご覧ください。
また、ここでは整数 を Share に分割する際は必ず が整数であるように分割するとします。
 
まず, 本問題は以下の LTZ アルゴリズムがあれば解けることを示します。

LTZ(Less Than Zero)

ある自然数 について を満たす整数 に対して、人 1,2 がそれぞれ Share を持っているときに が成り立つかどうかを求めるアルゴリズム。
ただしこのアルゴリズムにおいて、 か否かを人 1,2 が知ることを除き、 についての情報は一切漏れない。

太郎くんと花子さんは問題(1)と同様にそれぞれ の Share を作成し、互いに配布します。
この時、太郎くんと花子さんはそれぞれ を求めることが出来ます。
これは の Share であるため、 として LTZ を適用することで 、すなわち であるか否かを求めることが出来ます。
同様に二人は の Share を求めることで であるか否かも求めることが出来ます。
以上の結果から、 の大小関係を求めることが出来ました。
以下では LTZ を解説します。

LTZ

まず LTZ は以下の RS アルゴリズムがあれば解けることを示します。

RS(Right Shift)

整数 に対して人 1,2 がそれぞれ Share を持っているときに の Share をそれぞれ人 1,2 に配布するアルゴリズム。( 以下の最大の整数を表します。例えば 以下で最大の整数である になります。)
ただしこのアルゴリズムにおいて の情報は一切漏れない。

の Share に対して RS を行うことで人 1,2 は の Share を持ちます。
この Share に対してさらに RS を行うことで人 1,2 は の Share を持ちます。
同様にして 回の操作を行うことで、人 1,2 は の Share を持ちます。
ここで について以下の式が成り立ちます。
したがって、人1,2が の Share を互いに公開し の真値を求め、その値を確認することで か否かを求めることが出来ます。
以下では RS を解説します。

RS

整数 に対し のパリティ、すなわち が偶数の時 が奇数の時 とします。
また、 に対し の排他的論理和、すなわち
とします。
これは と同値です。
まず BMT の時と同様に人1でも人2でもないあなたが を秘密裏に生成し、その Share をそれぞれ人 1,2 に配布します。( は要求されていないことに注意)
を計算し、その値を共有することで を互いに求めます。
とおき、 を以下で定めます。
この が RS の要件を満たすもの、すなわち整数であること及び等式 が成立することを示します。
整数性については から従います。
等式については
より を示せば十分です。
これは を移項して と同値であり
より示すことが出来ます。

参考文献

発展問題

問題(1)(2)では Share を保持するのは太郎くんと花子さんの二人でした。
Share を保持するのが3人以上の場合でも問題(1)の BMT や問題(2)の RS が動作するように、各アルゴリズムを適切に修正してください。