✅
問題（２）解説
問題（１）の解説と同様に加法的秘密分散法を用います。
もし加法的秘密分散法を知らない方は先に問題（１）の解説をご覧ください。
また、ここでは整数 を Share に分割する際は必ず が整数であるように分割するとします。
まず, 本問題は以下の LTZ アルゴリズムがあれば解けることを示します。
LTZ（Less Than Zero）
ある自然数 について を満たす整数 に対して、人 1,2 がそれぞれ Share を持っているときに が成り立つかどうかを求めるアルゴリズム。
ただしこのアルゴリズムにおいて、 か否かを人 1,2 が知ることを除き、 についての情報は一切漏れない。
太郎くんと花子さんは問題（１）と同様にそれぞれ の 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 の要件を満たすもの、すなわち整数であること及び等式 が成立することを示します。
整数性については と から従います。
等式については
より を示せば十分です。
これは を移項して と同値であり
より示すことが出来ます。
参考文献
発展問題
問題（１）（２）では Share を保持するのは太郎くんと花子さんの二人でした。
Share を保持するのが3人以上の場合でも問題（１）の BMT や問題（２）の RS が動作するように、各アルゴリズムを適切に修正してください。