(57)【要約】      （修正有）【課題】安全にかつ効率的に秘匿積和演算を行うことができる秘密情報分散秘匿演算システムを提供する。【解決手段】ｎを整数、ｋをｎ以下の整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて第１の整数と第２の整数間の秘匿演算を行う秘密情報分散秘匿演算システムは、ネットワーク１０を介して相互に接続された入力者装置と複数のマシンからなる。入力者装置は、秘密情報に０でない値を加算した値に０でない乱数を乗じ、その乗算結果をそのまま各マシンに送信する。各マシンはｋ台以上のマシンが協力して秘匿積和演算を行い、その結果をメモリに保存する。入力者装置はどれかのマシンから取得した秘匿積和演算結果から積和演算結果を計算する。【選択図】図１
2019144405.tif 000002
【特許請求の範囲】
【請求項１】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値を加算した値に０でない値の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする入力者装置。
【請求項２】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値の第１の乱数を加算する手段と、その値に０でない値の第２の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする演算支援装置。
【請求項３】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値の乱数を秘匿加算する手段と、その秘匿加算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする演算支援装置。
【請求項４】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、１個以上の第１の乱数を生成する手段と、第１の乱数の各々を秘密分散した分散値の各々にかける手段と、を有することを特徴とする装置。
【請求項５】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、請求項４による異なる乱数がかかった分散値に請求項１〜請求項３の装置によって公開された秘匿化秘密情報を作用させる手段と、その手段の出力である同一の秘密情報に対して異なる乱数を作用させた分散値を用いて演算する手段を有することを特徴とする秘匿演算装置。
【請求項６】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、用いる秘匿演算装置の数をｔ、入力数をｕとしたとき、ｎをｕ（ｋ−１）＋１以上として秘密分散を行う手段と、その分散値をｎ／ｔ個毎に分割して異なる乱数を乗算する手段と、その異なる乱数が乗じられた分散値ｎ／ｔ個から少なくとも１つの分散値を秘匿演算装置に配布する手段と、を有することを特徴とした入力者装置。
【請求項７】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、分散値同士の乗算を行う手段と、乱数がかけられた分散値同士の積から乱数を削除する手段と、乱数が削除された分散値に対して次数変換処理を１回以上繰り返す手段と、を有することを特徴とする秘匿演算装置。
【請求項８】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、請求項１〜３による秘匿化秘密情報から請求項１〜３で加算された定数を秘匿減算する手段と、その秘匿減算結果が０であるかを検証する手段と、０でないときに秘匿減算された値からその逆数を生成する手段と、を有する秘匿演算装置。
【請求項９】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、異なる乱数がかかった分散値を他の分散値と同じ乱数に変換する手段と、同じ乱数がかかった秘密情報を復元する、または秘匿演算装置が復元できるようにする手段と、を有する演算支援装置。
【請求項１０】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける入力者装置のコンピュータを、秘密情報に０でない値を加算した値に０でない値の乱数を乗ずる手段、及びその乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させるプログラム。
【請求項１１】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、秘密情報に０でない値の第１の乱数を加算する手段、及びその値に０でない値の第２の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させるプログラム。
【請求項１２】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、秘密情報に０でない値の乱数を秘匿加算する手段、及びその秘匿加算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させるプログラム。
【請求項１３】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける装置のコンピュータを、１個以上の第１の乱数を生成する手段、及び第１の乱数の各々を秘密分散した分散値の各々にかける手段として機能させるプログラム。
【請求項１４】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、請求項４による異なる乱数がかかった分散値に請求項１〜請求項３の装置によって公開された秘匿化秘密情報を作用させる手段、及びその手段の出力である同一の秘密情報に対して異なる乱数を作用させた分散値を用いて演算する手段として機能させるプログラム。
【請求項１５】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける入力者装置のコンピュータを、用いる秘匿演算装置の数をｔ、入力数をｕとしたとき、ｎをｕｔ以上として秘密分散を行う手段、その分散値をｎ／ｔ個毎に分割して異なる乱数を乗算する手段、及びその異なる乱数が乗じられた分散値ｎ／ｔ個から少なくとも１つの分散値を秘匿演算装置に配布する手段として機能させるプログラム。
【請求項１６】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、分散値同士の乗算を行う手段と、乱数がかけられた分散値同士の積から乱数を削除する手段、及び乱数が削除された分散値に対して次数変換処理を１回以上繰り返す手段として機能させるプログラム。
【請求項１７】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、請求項１〜３による秘匿化秘密情報から請求項１〜３で加算された定数を秘匿減算する手段、及びその秘匿減算結果が０であるかを検証する手段と、０でないときに秘匿減算された値からその逆数を生成する手段として機能させるプログラム。
【請求項１８】
ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、異なる乱数がかかった分散値を他の分散値と同じ乱数に変換する手段、及び同じ乱数がかかった秘密情報を復元する、または秘匿演算装置が復元できるようにする手段として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力者装置、演算支援装置、装置、秘匿演算装置、及びプログラムに関する。
【背景技術】
【０００２】
入力者装置、演算支援装置、及び秘匿演算装置は情報を安全に分散管理する分散管理技術に関する。また、分散管理された情報を秘匿したまま演算を行う秘匿演算技術に関する。
【０００３】
近年、ＡＩなどの進歩に伴い、ニューラルネットワーク（以降、ＮＮ）の活用が期待されている。ただし、ＮＮの活用においては、解こうとする問題が漏洩すると個人のプライバシーや企業の機密情報に影響を与える可能性がある。そのため、ＮＮの利活用においては、その入力情報や解こうとする問題を秘匿できることが望まれる。
【０００４】
入力情報を秘匿しながら計算を実現する手法として秘匿計算技術が研究されている。秘匿計算技術を大きく分けると、主に鍵を用いてデータを秘匿する公開鍵暗号に基づく準同型暗号と、鍵を用いずにデータを秘匿する秘密分散法を用いた秘匿計算がある。ただし、準同型暗号は一般的に計算量が多く、演算の処理に多大な時間がかかるという問題がある。一方、秘密分散を用いる場合、最小２台の装置が必要であるが、秘匿計算を行おうとすれば、一般に３台以上の別々に管理された装置が必要であることが知られており、装置規模が大きくなるという問題がある。よって、高速な秘匿計算が可能で、できるだけ少ない台数、または小さな装置規模で秘匿計算が行える仕組みが必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明では、小さな装置規模で効率的に秘匿計算を行える入力者装置、演算支援装置、及び秘匿演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
請求項１に記載の発明の入力者装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値を加算した値に０でない値の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする。
【０００７】
請求項２に記載の発明の演算支援装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値の第１の乱数を加算する手段と、その値に０でない値の第２の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする。
【０００８】
請求項３に記載の発明の演算支援装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、秘密情報に０でない値の乱数を秘匿加算する手段と、その秘匿加算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段と、を有することを特徴とする。
【０００９】
請求項４に記載の発明の装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、１個以上の第１の乱数を生成する手段と、第１の乱数の各々を秘密分散した分散値の各々にかける手段と、を有することを特徴とする。
【００１０】
請求項５に記載の発明の秘匿演算装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、請求項４による異なる乱数がかかった分散値に請求項１〜請求項３の装置によって公開された秘匿化秘密情報を作用させる手段と、その手段の出力である同一の秘密情報に対して異なる乱数を作用させた分散値を用いて演算する手段を有することを特徴とする。
【００１１】
請求項６に記載の発明の入力者装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、用いる秘匿演算装置の数をｔ、入力数をｕとしたとき、ｎをｕｔ以上として秘密分散を行う手段と、その分散値をｎ／ｔ個毎に分割して異なる乱数を乗算する手段と、その異なる乱数が乗じられた分散値ｎ／ｔ個から少なくとも１つの分散値を秘匿演算装置に配布する手段と、を有することを特徴とする。
【００１２】
請求項７に記載の発明の秘匿演算装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、分散値同士の乗算を行う手段と、乱数がかけられた分散値同士の積から乱数を削除する手段と、乱数が削除された分散値に対して次数変換処理を１回以上繰り返す手段と、を有することを特徴とする。
【００１３】
請求項８に記載の発明の秘匿演算装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、請求項１〜３による秘匿化秘密情報から請求項１〜３で加算された定数を秘匿減算する手段と、その秘匿減算結果が０であるかを検証する手段と、０でないときに秘匿減算された値からその逆数を生成する手段と、を有する。
【００１４】
請求項９に記載の発明の演算支援装置は、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおいて、異なる乱数がかかった分散値を他の分散値と同じ乱数に変換する手段と、同じ乱数がかかった秘密情報を復元する、または秘匿演算装置が復元できるようにする手段と、を有する。
【００１５】
請求項１０に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける入力者装置のコンピュータを、秘密情報に０でない値を加算した値に０でない値の乱数を乗ずる手段、及びその乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させる。
【００１６】
請求項１１に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、秘密情報に０でない値の第１の乱数を加算する手段、及びその値に０でない値の第２の乱数を乗ずる手段と、その乗算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させる。
【００１７】
請求項１２に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、秘密情報に０でない値の乱数を秘匿加算する手段、及びその秘匿加算結果をそのまま秘匿演算に参加する全秘匿演算装置に送る手段として機能させる。
【００１８】
請求項１３に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける装置のコンピュータを、１個以上の第１の乱数を生成する手段、及び第１の乱数の各々を秘密分散した分散値の各々にかける手段として機能させる。
【００１９】
請求項１４に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、請求項４による異なる乱数がかかった分散値に請求項１〜請求項３の装置によって公開された秘匿化秘密情報を作用させる手段、及びその手段の出力である同一の秘密情報に対して異なる乱数を作用させた分散値を用いて演算する手段として機能させる。
【００２０】
請求項１５に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける入力者装置のコンピュータを、用いる秘匿演算装置の数をｔ、入力数をｕとしたとき、ｎをｕｔ以上として秘密分散を行う手段、その分散値をｎ／ｔ個毎に分割して異なる乱数を乗算する手段、及びその異なる乱数が乗じられた分散値ｎ／ｔ個から少なくとも１つの分散値を秘匿演算装置に配布する手段として機能させる。
【００２１】
請求項１６に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、分散値同士の乗算を行う手段と、乱数がかけられた分散値同士の積から乱数を削除する手段、及び乱数が削除された分散値に対して次数変換処理を１回以上繰り返す手段として機能させる。
【００２２】
請求項１７に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける秘匿演算装置のコンピュータを、請求項１〜３による秘匿化秘密情報から請求項１〜３で加算された定数を秘匿減算する手段、及びその秘匿減算結果が０であるかを検証する手段と、０でないときに秘匿減算された値からその逆数を生成する手段として機能させる。
【００２３】
請求項１８に記載の発明のプログラムは、ｎを２以上の整数、ｋを、最小値が２で最大値がｎの整数、Ｌを１以上ｋ以下の整数とし、秘密情報をｎ個に分散し、ｎ個のうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個以下では秘密情報を復元できない手段を用いて秘匿演算を行うシステムにおける演算支援装置のコンピュータを、異なる乱数がかかった分散値を他の分散値と同じ乱数に変換する手段、及び同じ乱数がかかった秘密情報を復元する、または秘匿演算装置が復元できるようにする手段として機能させる。
【発明の効果】
【００２４】
本発明は、効率的に計算を行える。
【図面の簡単な説明】
【００２５】
【図１】第１の実施の形態の秘密情報分散秘匿演算システムの構成図である。
【図２】第１の実施の形態の入力者装置１２のブロック図である。
【図３】入力者装置１２のＣＰＵ２２の機能ブロック図である。
【図４】マシン１４Ｎ０〜１４Ｎｎ−１のＣＰＵ２２の機能ブロック図である。
【図５】分散１のプログラムのフローチャートである。
【図６】秘匿積和演算１のプログラムのフローチャートである。
【図７】秘密分散１のプログラムのフローチャートである。
【図８】秘匿除算１のプログラムのフローチャートである。
【図９】分散１′のプログラムのフローチャートである。
【図１０】秘匿積和演算１′のプログラムのフローチャートである。
【図１１】秘匿積和演算１′のプログラムのフローチャートである。
【図１２】入力者装置１２のＣＰＵ２２の機能ブロック図である。
【図１３】分散２のプログラムのフローチャートである。
【図１４】積和のプログラムのフローチャートである。
【図１５】演算支援２のプログラムのフローチャートである。
【図１６】演算支援２′のプログラムのフローチャートである。
【図１７】秘匿除算２のプログラムのフローチャートである。
【図１８】第３の実施の形態の秘密情報分散秘匿演算システムの構成図である。
【図１９】入力者装置１２のＣＰＵ２２の機能ブロック図である。
【図２０】マシン１４Ｎ０〜１４Ｎｎ−１のＣＰＵ２２の機能ブロック図である。
【図２１】変換用乱数生成３のシーケンス図である。
【図２２】変換用乱数生成３’のシーケンス図である。
【図２３】分散３のプログラムのフローチャートである。
【図２４】秘匿積和演算３のプログラムのフローチャートである。
【図２５】第４の実施の形態の構成の秘密情報分散秘匿演算システムの構成図である。
【図２６】分散４のプログラムのフローチャートである。
【図２７】積和演算４のプログラムのフローチャートである。
【図２８】演算支援４のプログラムのフローチャートである。
【図２９Ａ】入力者装置１２Ａの分散５のプログラムのフローチャートである。
【図２９Ｂ】入力者装置１２Ｂの分散５のプログラムのフローチャートである。
【図２９Ｃ】入力者装置１２Ｃの分散５のプログラムのフローチャートである。
【図２９Ｄ】演算支援装置１６の分散５のプログラムのフローチャートである。
【図２９Ｅ】マシン１４ＮＮの分散５のプログラムのフローチャートである。
【図２９Ｆ】分散５のシーケンス図である。
【図３０】秘匿積和演算５のプログラムのフローチャートである。
【図３１】秘匿積和演算５のプログラムのフローチャートである。
【図３２】演算支援５のプログラムのフローチャートである。
【発明を実施するための形態】
【００２６】
以下、図面を参照して本発明の実施の形態の一例を詳細に説明する。
＜ 第１の実施の形態＞
まず、第１の実施の形態の構成を説明する。
図１に示すように、第１の実施の形態の秘密情報分散秘匿演算システムは、ネットワーク１０を介して相互に接続された、入力者装置１２、複数（Ｎ個）のマシン１４Ｎ０〜１４Ｎｎ−１を備えている。マシン１４Ｎ０〜１４Ｎｎ−１は、ニューラルネットワークマシン（ＮＮマシン）である。なお、以下では、マシン１４Ｎ０〜１４Ｎｎ−１の各々を、マシン１４Ｎｉで標記する場合もある。
【００２７】
入力者装置１２及びマシン１４Ｎ０〜１４Ｎｎ−１は、同様の構成になっているので、入力者装置１２の構成のみを、図２を参照して説明する。図２に示すように、入力者装置１２は、コンピュータを備え、ＣＰＵ２２、ＲＯＭ２４、ＲＡＭ２６、メモリ２８、入力装置３０、送受信装置３２、表示装置３４がバス３６を介して相互に接続されて、構成されている。入力者装置１２及びマシン１４Ｎ０〜１４Ｎｎ−１のメモリ２８には、後述するプログラムが記憶されている。
【００２８】
次に、図３を参照して、入力者装置１２のＣＰＵ２２がプログラムを実行することで実現される機能について説明する。プログラムは、分散機能を備えている。ＣＰＵ２２がこの機能を有するプログラムを実行することで、ＣＰＵ２２は、図３に示すように、分散部４２として機能する。なお、上記プログラムは、復元機能を備え、ＣＰＵ２２がこの機能を有するプログラムを実行することで、ＣＰＵ２２は、図示しない復元部として機能する。
【００２９】
次に、図４を参照して、マシン１４Ｎ０〜１４Ｎｎ−１の各々のＣＰＵ２２がプログラムを実行することで実現される機能について説明する。プログラムは、秘匿積和演算機能及び秘匿除算機能を備えている。ＣＰＵ２２がこの機能を有するプログラムを実行することで、ＣＰＵ２２は、図４に示すように、秘匿積和演算部４４及び秘匿除算部４６として機能する。
【００３０】
次に、本実施の形態の作用を説明する。
【００３１】
本実施の形態では、秘密分散法を用いる。最初に、秘密分散法を説明する。代表的な秘密分散法であるＳｈａｍｉｒの（ｋ、ｎ）閾値秘密分散法（以降、Ｓｈａｍｉｒ法）は、１つの秘密情報をｎ個の分散値に変換し、ｎ台のサーバに分散する。Ｓｈａｍｉｒ法の特徴は、分散したｎ個の分散値から、ｋ個の分散値を集めれば、元の秘密情報を復元することができるが、ｋ個未満の情報からは、秘密情報に関する情報を一切得ることができないということである。Ｓｈａｍｉｒ法のアルゴリズムを以下に示す。また、秘密分散法を用いた秘匿計算法として以下に示すＴＵＳ方式がある。
【００３２】
Ｓｈａｍｉｒの（ｋ、ｎ）閾値秘密分散法
（分散処理）
ユーザはｓ＜ｐかつｎ＜ｐの条件を満たす任意の素数ｐを選択する。
【００３３】
ユーザはＧＦ（ｐ）の元からｎ個のｘｉ（ｉ＝０、１、２、・・・、ｎ−１）を選び、サーバＩＤとする。
【００３４】
ユーザはＧＦ（ｐ）の元からｋ−１個の乱数ａｌ（ｌ＝１、２、・・・、ｋ−１）を選び、以下の分散式を生成する。
【００３５】
Ｗｉ＝ｓ＋ａ１ｘｉ＋ａ２ｘｉ２＋・・・＋ａｋ−１ｘｉｋ−１（ｍｏｄｐ）
【００３６】
ユーザは上式のｘｉに各サーバＩＤを代入し、分散値Ｗｉを計算し、各サーバＳｉに送信する。
【００３７】
（復元処理）
復元に用いる分散情報をＷｉ（ｉ＝０、１、２、・・・、ｋ−１）として、その分散情報に対応するサーバＩＤをｘｉとする。
【００３８】
分散式にｘｉとＷｉを代入し、ｋ個の連立方程式を解いて、元の秘密情報ｓを復元する。ただし、秘密情報ｓを復元する際に、ラグランジュの補間公式を使うと便利である。
【００３９】
また、秘密情報をＬ個に分割し、分散式の係数として含ませるランプ型秘密分散方式も知られている。これによって、分散値の小型化が実現できる。
【００４０】
ＴＵＳ方式
従来の秘匿乗算はＳｈａｍｉｒ法による分散値をそのまま用いて乗算するため多項式の次数が変化し、復元に必要な分散値の数が２ｋ−１個に増加する。しかし、以下の文献１で提案されたＴＵＳ方式は、秘密情報に乱数を乗じて秘匿化秘密情報を生成し、それを秘密分散する。秘匿乗算を行う際には、秘匿化秘密情報を一時的に復元してスカラー量として扱い、他の分散値と乗算を行う。これにより、乗算した際に多項式の次数は増加しないので、閾値を変化させない秘匿乗算を行うことができる。ただし、秘匿乗算においては秘密情報が漏洩する可能性があるため、秘密情報ａ、ｂは０を含まず、乱数も０を含まない（秘匿乗算以外では秘密情報に０を含んでもよい）。ＴＵＳ方式は秘密分散の処理も含めてすべての秘匿演算はｐを法として行われる。
【００４１】
文献１：神宮武志、岩村惠市：“除算を含む四則演算に適応可能な秘密分散法を用いた秘匿計算手法の提案”、信学技報１１５（１２２）、５１−５７、２０１５−０７−０２。
【００４２】
文献２：青井健、神宮武志、岩村惠市：“ｎ＜２ｋ−１における秘匿計算の安全性検討及び非対称秘密分散との応用”、信学技報１１６（１２９）、２３７−２４３、２０１６−０７−１４。
【００４３】
ＴＵＳ方式の問題点
ＴＵＳ方式は秘匿加減算と秘匿乗除算が別々に構成され、それら単独であれば安全であることが、上記文献２に示されている。しかし、秘匿乗算と秘匿加算を組み合わせて、ｆ（ｘ）＝ａｂ＋ｃのような積和演算を行う場合安全でない。以下に、手順１〜５でＴＵＳ方式の秘匿乗算ａｂを行い、手順６〜１０で秘匿加算ａｂ＋ｃを行う場合を示す。なお、秘密情報ａ、ｂ、ｃはａ、ｂ、ｃ∈Ｚ／ｐＺであり、分散処理および秘匿加算で生成する乱数αｊ、βｊ、λｊ、γｊもαｊ、βｊ、λｊ、γｊ∈Ｚ／ｐＺである（ただし、乗算において一旦復元されるａと乱数は０ではない）。以下において、
【００４４】
【数１】
2019144405.tif 000003
【００４５】
はａに対する分散値を表す。秘密分散の処理も含めてすべての秘匿演算はｐを法として行われる。
【００４６】
（ａｂ＋ｃの秘匿演算）
入力：
【数２】
2019144405.tif 000004
【００４７】
出力：
【数３】
2019144405.tif 000005
【００４８】
手順１：サーバＳ０はｋ台のサーバより
【数４】
2019144405.tif 000006
を収集し、一時的にαａのスカラー量を復元し、全サーバＳｉに送信する。
【００４９】
手順２：全サーバＳｉは以下の式を用いて、
【数５】
2019144405.tif 000007
を計算する。
【数６】
2019144405.tif 000008
【００５０】
手順３：ｋ台のサーバＳｊは
【数７】
2019144405.tif 000009
と
【数８】
2019144405.tif 000010
を収集し、αｊとβｊを復元し、αｊβｊを計算する。
【００５１】
手順４：ｋ台のサーバＳｊは乱数αｊβｊをＳｈａｍｉｒの（ｋ、ｎ）閾値秘密分散法で全サーバＳｉに分散する。
【００５２】
手順５：サーバＳｉ（ｉ＝０、１、２、・・・、ｎ−１）は秘密情報ａｂに関する分散情報として
【数９】
2019144405.tif 000011
を保持する。
【００５３】
手順６：ｋ台のサーバＳｊは
【数１０】
2019144405.tif 000012
と
【数１１】
2019144405.tif 000013
を収集し、αｊβｊとλｊを復元する。それから、ｋ台のサーバＳｊは乱数γｊを生成し、サーバＳ０にγｊ／αｊβｊ、γｊ／λｊを送信する。
【００５４】
手順７：サーバＳ０はγｊ／αｊβｊ、γｊ／λｊを用いて、以下の式よりγ／αβ、γ／λを計算し、全サーバＳｉに送信する。
【数１２】
2019144405.tif 000014
【００５５】
手順８：全サーバＳｉは以下の式を用いて、
【数１３】
2019144405.tif 000015
を計算する。
【数１４】
2019144405.tif 000016
【００５６】
手順９：ｋ台のサーバＳｊは乱数γｊをＳｈａｍｉｒの（ｋ、ｎ）閾値秘密分散法で全サーバＳｉに分散する。
【００５７】
手順１０：サーバＳｉ（ｉ＝０、１、２、・・・、ｎ−１）は秘密情報ａｂ＋ｃに関する分散情報として
【数１５】
2019144405.tif 000017
2019144405.tif 000018
を保持する。
【００５８】
（復号処理）
手順ａ：復元者はＫ台のサーバよりｋ個の分散情報［ａｂ＋ｃ］ｊを収集する。
【００５９】
手順ｂ：収集した分散情報の
【数１６】
2019144405.tif 000019
からγ（ａｂ＋ｃ）、γ０、・・・、γｋ−１を復元し、乱数
【数１７】
2019144405.tif 000020
を計算する。
【００６０】
手順ｃ：復元した秘匿した秘密情報γ（ａｂ＋ｃ）と乱数γを用いて、以下の式より秘密情報ａｂ＋ｃを復元する。
γ（ａｂ＋ｃ）×γ−１＝ａｂ＋ｃ
【００６１】
積和演算は３入力１出力の演算であるため、入力者は３人、出力者は１人想定される。ここで、攻撃者として復元者かつ１つの値の入力者である場合を考える。例えば、攻撃者が秘密情報ｂの入力者かつ復元者である場合、攻撃者は入力者が入力した秘密情報ｂ、乱数β、演算結果を復元するための乱数γ、演算結果ａｂ＋ｃおよびｋ−１台のサーバから漏洩するαａ、γ／αβ、γ／λの情報を持っている。攻撃者は乱数β、γ、γ／αβの情報を用いて、乱数αを求めることができる。攻撃者は求めた乱数αと演算途中に得られるαａより秘密情報ａを計算することができる。それから、攻撃者は秘密情報ａ、ｂと演算結果ａｂ＋ｃを用いて、秘密情報ｃを知ることができる。これによって、攻撃者は入力者Ｂの入力情報、復元者の持つ情報およびｋ−１台のサーバから漏洩する情報を持っていれば、残りの入力者の情報が漏洩してしまうという問題がある。
【００６２】
一般に、ビッグデータなどに対する秘匿計算においては、秘密情報の入力者は複数存在し、秘匿演算結果を復元する復元者も入力者と異なる、または入力者と一部同一であり、その利害は他者と対立すると想定する。それに対して、ＮＮでは入力者はある問題を解こうとする１名または同一組織（以降、入力者と呼ぶ）であることが多く、入力者は多くの学習データを準備して、すべての秘密情報と演算結果を知る。ここでは、入力者がＮＮマシン及びＮＮマシンを監視できる攻撃者に対して入力および解こうとする問題を秘匿したい場合を想定する。秘密分散を用いる場合、最小ｎ＝２であるが、以降ではｎ＝１をめざし、ｎ＝１、２の場合に対して有効な秘匿計算法を提案する。
【００６３】
まず、秘密分散を用いてＮＮマシンで問題を解こうとする場合、ＴＵＳ方式以外では最小閾値であるｎ＝ｋ＝２としたくても秘匿乗算が含まれれば、ｎに相当するＮＮマシンは３台以上必要とすることが知られている。また、ＴＵＳ方式では安全な積和演算が実現できない。
【００６４】
そこで、第１の実施の形態として、入力者及び復元者を同一の１名として、最小２台のＮＮマシンで秘匿計算を実現する場合を考える。この場合、入力者及び復元者が異なり利害が対立するとするＴＵＳ方式を上記状況に合わせて効率化することと、入力される情報に０が含まれないとは保証されないため、ＴＵＳ方式では対応できなかった秘密情報に０を含む積和演算を実現することが課題となる。
【００６５】
四則演算は積和演算ａｂ＋ｃの組み合わせで実現できる。ＴＵＳ方式では積和演算を安全に実行できなかったが、秘匿積和演算を安全に実現できれば、任意の四則演算はその組み合わせによって実現される。ただし、本実施の形態では一人の入力者が全秘密情報ａ、ｂ、ｃを入力するとする。また、以下ではｎ台のＮＮマシンを例に説明するが、最小にしたい場合ｎ＝ｋ＝２とできる。また、前記ＴＵＳ方式では秘密情報に直接乱数をかけて分散したため、秘匿乗算においてαａをスカラー量として復元したとき、秘密情報がａ＝０の場合、αａ＝０となるため秘密情報に０を含むことができなかった。また、秘匿加算ではαａを復元しないため、ａ＝０であってもよいが、そのためαａは必ず秘密分散しておく必要があり、αを構成する乱数α０、α１、・・・、αｋ−１を含む全情報は全て秘密分散しておく必要があった。よって、その全秘密情報の分散及び復元に大きな手間が生じた。以下では秘密情報に直接乱数をかけるだけで分散せず、秘密情報ａに１を加えることから、ａ＝０であってもα（ａ＋１）＝０とならない。そのためα（ａ＋１）を分散することなくそのまま配布することができる。また、入力者は全ての秘密を知るためαを直接使用できる。すなわち、α０、α１、・・・、αｋ−１などに分解する必要がなく、これによって秘密分散に関する手間を大きく効率化できる。
【００６６】
以下において、秘密情報ａ、ｂ、ｃは１を加えるためａ、ｂ、ｃ＜ｐ−１であり、生成する乱数α、β、γ、δはα、β、γ、δ∈Ｚ／ｐＺである（ただし、乱数として０は選択されない）。また、秘密分散の処理も含めてすべての演算はｐを法として行われる。また、以下の記号を定義する。また、値を公開するとは秘匿演算を行う全マシンにその値を送ることを意味する。
【００６７】
（記号定義）
［ａ］ｉは、マシン１４Ｎｉが保持する値ａに対する分散値を示す。
【００６８】
［分散１］
次に、図５を参照して、入力者装置１２のＣＰＵ２２における分散部４２が実行する分散１を説明する。
【００６９】
ステップ５２で、分散部４２は、乱数α、β、γを生成する。なお、乱数α、β、γは、真正乱数でも疑似乱数でもよい。以下の各乱数も同様である。
【００７０】
ステップ５４で、分散部４２は、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）を、次のように計算する。
【００７１】
α（ａ＋１）＝α×（ａ＋１）
β（ｂ＋１）＝β×（ｂ＋１）
γ（ｃ＋１）＝γ×（ｃ＋１）
【００７２】
ステップ５６で、分散部４２は、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）を、全マシン１４Ｎ０〜１４Ｎｎ−１に送信する。
【００７３】
ステップ５８で、分散部４２は、乱数δを生成し、ステップ６０で、分散部４２は、δ／αβ、δ／α、δ／β、δ／γ、δを計算し、ステップ６２で、分散部４２は、その秘密分散の分散値［δ／αβ］ｉ、［δ／α］ｉ、［δ／β］ｉ、［δ／γ］ｉ、［δ］ｉを計算する（ｉ＝０，・・・，ｋ−１）。
【００７４】
ステップ６４で、分散部４２は、分散値［δ／αβ］ｉ、［δ／α］ｉ、［δ／β］ｉ、［δ／γ］ｉ、［δ］ｉを、対応するマシン１４Ｎ０〜１４Ｎｎ−１中のマシン１４Ｎｉに送信する。
【００７５】
なお、入力者装置１２のＣＰＵ２２における分散部４２はδを入力者装置１２のメモリ２８に保存する。
【００７６】
［秘匿積和演算１］
次に、図６を参照して、マシン１４Ｎ０〜１４Ｎｎ−１の予め定められたｋ台以上のマシン（マシン１４Ｎｉ（ｉ＝０,・・・,ｋ−１）のＣＰＵ２２における秘匿積和演算部４４が実行する秘匿積和演算１を説明する。
ステップ７２で、秘匿積和演算部４４は、以下を計算する。
［δ（ａｂ＋ｃ＋１）］ｉ＝α（ａ＋１）×β（ｂ＋１）×［δ／αβ］ｉ−α（ａ＋１）×［δ／α］ｉ−β（ｂ＋１）×［δ／β］ｉ＋γ（ｃ＋１）×［δ／γ］ｉ＋［δ］ｉ
【００７７】
ステップ７４で、秘匿積和演算部４４は、予め定められたｋ台以上のマシンが協力してδ（ａｂ＋ｃ＋１）を復元する。
【００７８】
ステップ７６で、秘匿積和演算部４４は、δ（ａｂ＋ｃ＋１）を各マシン１４Ｎ０〜１４Ｎｎ−１のメモリ２８に保存する。
【００７９】
入力者が計算結果を得る場合、入力者装置１２は、δ（ａｂ＋ｃ＋１）をどれかのマシンから得て、保存しているδで割って１を引くことによって積和演算結果であるａｂ＋ｃを得る。もしくは、［δ］ｉを集めて復元し、δで割って１を引く。また、分散１では１を加えるが、加える値は１に限定されず、その他の値、例えば、２であれば下記を積和演算として計算すればよい。
【００８０】
［δ（ａｂ＋ｃ＋２）］ｉ＝α（ａ＋２）×β（ｂ＋２）×［δ／αβ］ｉ−２α（ａ＋２）×［δ／α］ｉ−２β（ｂ＋２）×［δ／β］ｉ＋γ（ｃ＋２）×［δ／γ］ｉ＋４［δ］ｉ
【００８１】
その他の値は、例えば、−１、−２に相当するＺ／ｐＺ上の値でもよい。入力者装置１２は、δ（ａｂ＋ｃ−１）を保存しているδで割って、１（または２等）を加えることによって積和演算結果であるａｂ＋ｃを得るようにしてもよい。
【００８２】
また、秘匿積和演算１においてｃ＝０とすれば秘匿乗算となり、ａ＝１とすれば秘匿加算となる。また、図６のステップ７２の＋γ(ｃ＋１)を−γ(ｃ＋１)とすれば秘匿減算となる。秘匿積和演算１では公開されたα（ａ＋１），β（ｂ＋１），γ(ｃ＋１)以外のステップ７２における秘匿積和演算に必要な情報は分散され、入力者装置１２以外知らないため、攻撃者は公開された情報以外知ることができず情報理論的に安全である。
【００８３】
［秘密分散１］
【００８４】
また、秘匿除算は以下のように行う。図７には、秘匿除算のための、入力者装置１２のＣＰＵ２２における分散部４２が実行する秘密分散１のフローチャートが示されている。
【００８５】
ステップ８２で、分散部４２は、乱数α′を生成し、ステップ８４で、分散部４２は、α′／αを計算する。
【００８６】
ステップ８６で、分散部４２は、α′／αの秘密分散の分散値とα′の秘密分散値とを計算する。
【００８７】
ステップ８８で、分散部４２は、α′／αの秘密分散の分散値とα′の秘密分散値とを、対応するマシン１４Ｎｉに送信する。
【００８８】
［秘匿除算１］
図８には、マシン１４Ｎ０〜１４Ｎｎ−１の各々のＣＰＵ２２における秘匿除算部４６が実行する秘匿除算１のフローチャートが示されている。
【００８９】
ステップ９２で、秘匿除算部４６は、以下を計算する。
［α’ａ］ｉ＝α（ａ＋１）×［α′／α］ｉ−［α′］ｉ
【００９０】
ステップ９４で、秘匿除算部４６は、他のマシンと協力して［α′ａ］ｉを復元する。
【００９１】
ステップ９６で、秘匿除算部４６は、α′ａ＝０であるか否かを判断する。α′ａ＝０であれば、秘匿除算１は終了する。
【００９２】
α′ａ＝０でなければ、ステップ９８で、秘匿除算部４６は、１／α′ａを計算する、
【００９３】
ステップ１００で、秘匿除算部４６は、１／α′ａをα（ａ＋１）として秘匿積和演算１のために秘匿積和演算部４４に送る。これにより、秘匿積和演算部４４により、乗算を除算に変えた結果が得られる。ただし、秘匿積和演算１のステップ７２における−β（ｂ＋１）×［δ／β］ｉの計算は１／α′ａに１が足されていないため省略される。
【００９４】
上記秘匿除算においてα′ａ＝０である場合、ａ＝０であることが漏洩するが、除数が０の場合演算できず、それを検知して演算を中止する必要があるので、除算において除数が０であることがわかるのは問題ない。よって、入力者があらかじめ［α′ａ］ｉを生成しておき、必要な時に入力してもよい。
【００９５】
演算を連続する場合、復元したδ（ａｂ＋ｃ＋１）を、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）の１つとし、同様の演算によって計算された他の秘匿演算結果をα（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）の残りとすればよい。また、新たにδを生成し、α、β、γとなった乱数に対してδ／αβ、δ／α、δ／β、δ／γ、δを計算すればよい。
【００９６】
また、以上によって入力を秘匿することができるが、四則演算は積和演算の組み合わせで表せることから、解きたい問題をダミーの積和演算（ａ＝ｂ＝ｃ＝０とすれば加算用のダミー積和演算処理となり、ａ＝ｂ＝０、ｃ＝１とすれば乗算用のダミー積和演算処理となる）を含めて定型の秘匿積和演算の繰り返しで表すことにより、解こうとする問題も秘匿することができる。
【００９７】
また、入力者装置１２のＣＰＵ２２における分散部４２は、演算を繰り返す場合、分散１（図５参照）において、新たにδを生成し新たにα、β、γとなった乱数に対してδ／αβ、δ／α、δ／β、δ／γ、δを計算するが、演算手順が予め分かっている場合、予め計算しておくこともできる。
【００９８】
ただし、この場合、分散部４２が演算手順に応じて予め計算しておく必要があり、分散部４２の負担が大きい可能性がある。よって、分散部４２の負担を減らしたい場合、以下によって分散部４２は乱数を生成して分散するだけでよく、以降の処理はマシン１４Ｎ０〜１４Ｎｎ−１だけで実行できる。以下では、ｎ＝ｋとしてｎ台のマシンの中から演算を行うマシン１４Ｎｉは定まっているとし、αを構成する乱数を直接マシンに送付する場合を説明する。分散１’と秘匿積和演算１’が連続して行われず、演算を行うマシン１４Ｎｉが定まっていない場合は、αｉ、βｉ、γｉ（ｉ＝０、・・・、ｋ−１）などをｎ台のマシンに秘密分散し、秘匿演算時に演算に参加するマシンがその中から対応する乱数のｋ個の分散値を集めて復元してもよい。
【００９９】
［分散１′］
次に、上記の場合において入力者装置１２のＣＰＵ２２における分散部４２が実行する分散１′を、図９を参照して説明する。
【０１００】
ステップ１０２で、分散部４２は、ｋ個の乱数の組α０、α１、・・・、αｋ−１及びβ０、β１、・・・、βｋ−１、γ０、γ１、・・・、γｋ−１を生成する。
【０１０１】
ステップ１０４で、分散部４２は、以下を計算する。
【０１０２】
まず、分散部４２は、α＝α０×α１×・・・×αｋ−１を計算し、α（ａ＋１）＝α×（ａ＋１）を計算する。
【０１０３】
分散部４２は、β＝β０×β１×・・・×βｋ−１を計算し、β（ｂ＋１）＝β×（ｂ＋１）を計算する。
【０１０４】
分散部４２は、γ＝γ０×γ１×・・・×γｋ−１を計算し、γ（ｃ＋１）＝γ×（ｃ＋１）を計算する。
【０１０５】
ステップ１０６で、分散部４２は、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）を、全マシン１４Ｎ０〜１４Ｎｎ−１に送信する。
【０１０６】
ステップ１１０で、分散部４２は、αｉ、βｉ、γｉ（ｉ＝０、・・・、ｋ−１）を、対応するマシン１４Ｎｉに送信する。
【０１０７】
ステップ１１２で、分散部４２は、ｋ個の乱数の組ε０、ε１、・・・、εｋ−１及びφ０、φ１、・・・、φｋ−１、λ０、λ１、・・・、λｋ−１、η０、η１、・・・、ηｋ−１、μ０、μ１、・・・、μｋ−１を生成する。
【０１０８】
ステップ１１４で、分散部４２は、以下を計算する。
【０１０９】
ε＝ε０×ε１×・・・×εｋ−１
φ＝φ０×φ１×・・・×φｋ−１
λ＝λ０×λ１×・・・×λｋ−１
η＝η０×η１×・・・×ηｋ−１
μ＝μ０×μ１×・・・×μｋ−１
ステップ１１６で、分散部４２は、ε、φ、λ、η、μの分散値［ε］ｉ、［φ］ｉ、［λ］ｉ、［η］ｉ、［μ］ｉを計算する。
【０１１０】
ステップ１１８で、分散部４２は、分散値［ε］ｉ、［φ］ｉ、［λ］ｉ、［η］ｉ、［μ］ｉとεｉ、φｉ、λｉ、ηｉ、μｉを、対応するマシンに送信する。
【０１１１】
［秘匿積和演算１’］
次に、マシン１４Ｎ０〜１４Ｎｎ−１の各々のＣＰＵ２２における秘匿積和演算部４４が実行する秘匿積和演算１’を、図１０を参照して、説明する。
【０１１２】
ステップ１２２で、秘匿積和演算部４４は、乱数δｉを生成する。
【０１１３】
ステップ１２４で、秘匿積和演算部４４は、δｉ／αｉβｉεｉ、δｉ／αｉφｉ、δｉ／βｉλｉ、δｉ／γｉηｉ、δｉμｉを計算する。
【０１１４】
ステップ１２６で、秘匿積和演算部４４は、δｉ／αｉβｉεｉ、δｉ／αｉφｉ、δｉ／βｉλｉ、δｉ／γｉηｉ、δｉμｉを、予め定められたマシン１４Ｎ０に送信する（ｎ＝ｋ＝２のとき、２台のマシン間で互いに交換してもよい）。
【０１１５】
図１１に示すように、予め定められたマシン１４Ｎ０のＣＰＵ２２における秘匿積和演算部４４は、ステップ１４２で、以下のδ／αβε、δ／αφ、δ／βλ、δ／γη、μを計算し、ステップ１４６で、ステップ１４２で当該計算された各値を、全マシンに送信する（ステップ１２６で互いに値を交換した場合、図１１の処理は不要で、全マシンがδ／αβε、δ／αφ、δ／βλ、δ／γη、μを計算する。すなわち、ステップ１２８は「δ／αβε、δ／αφ、δ／βλ、δ／γη、μを計算」に変更される）。
【０１１６】
【数１８】
2019144405.tif 000021
【０１１７】
【数１９】
2019144405.tif 000022
【０１１８】
なお、「φ」と
【数２０】
2019144405.tif 000023
とは同じである。
【０１１９】
ステップ１２８で、秘匿積和演算部４４は、予め定められたマシン１４Ｎ０から送信されたδ／αβε、δ／αφ、δ／βλ、δ／γη、μを受信する。
【０１２０】
ステップ１３０で、秘匿積和演算部４４は、以下を計算する。
［αβε（ａ＋１）（ｂ＋１）］ｉ＝α（ａ＋１）×β（ｂ＋１）×［ε］ｉ
［αφ（ａ＋１）］ｉ＝α（ａ＋１）×［φ］ｉ、［βλ（ｂ＋１）］ｉ＝β（ｂ＋１）×［λ］ｉ、［γη（ｃ＋１）］ｉ＝γ（ｃ＋１）×［η］ｉ
【０１２１】
ステップ１３２で、秘匿積和演算部４４は、以下を計算する。
［δ（ａｂ＋ｃ＋１）］ｉ＝δ／αβε×［αβε（ａ＋１）（ｂ＋１）］ｉ−δ／αφ×［αφ（ａ＋１）］ｉ−δ／βλ×［βλ（ｂ＋１）］ｉ＋δ／γη×［γη（ｃ＋１）］ｉ＋δ／μ×［μ］ｉ
【０１２２】
分散１’におけるステップ１１２〜１１８で生成され各マシンに送付される（[ε]i、εi）、（[φ]i、φi）、（[λ]i、λi）、（[η]i、ηi）、（[μ]i、μi）は後述するように変換用乱数と呼ぶが、入力者装置が必ず生成する必要はなく、第３の実施の形態に示されるようにマシン間または他のマシンによって生成されてもよい。また、（[ε]i、εi）、（[φ]i、φi）、（[λ]i、λi）、（[η]i、ηi）、（[μ]i、μi）は予め準備されているとしてもよい。秘匿積和演算１’では次のα，β，γに相当するδは演算中に分散され、新たなδも演算中にマシン１４Ｎ０〜１４Ｎｎ−１が生成するため、演算途中で分散部４２の処理がなくても演算継続できる。
【０１２３】
近年、ＮＮマシンを公開して自由に利用できるようにする動きが広がっている。このようなパブリックのＮＮマシンが２台あったとき、第１の実施の形態によって全ＮＮマシンの情報が漏洩しない限り安全であり、準備するＮＮマシンも２台で済むという従来法では実現できない利点を実現できる。また、ＴＵＳ方式では安全にできなかった積和演算の定型の組み合わせによって解いている問題も秘匿しながら、効率的に秘匿演算結果を得ることができる。また、入力者装置が復元者装置であり、すべての情報を知るため多くの処理を効率化できる。これによって、個人または同一組織が自分の秘密情報及び解こうとする問題をＮＮマシンまたは攻撃者に漏らすことなく、公開されたＮＮマシンを利用して望む秘匿演算を実行できるようになる。
【０１２４】
＜第２の実施の形態＞
第２の実施の形態の秘密情報分散秘匿演算システムは、第１の実施の形態と同様の構成であるので、同様の構成部分には同一の符号を付して、その説明を省略する。ただし、入力者装置１２は、演算支援装置でもある。
【０１２５】
また、第２の実施の形態では、マシン１４Ｎ０〜１４Ｎｎ−１の内の予め定められた１台のマシン１４ＮＮが秘匿演算を行う。
【０１２６】
秘密分散法においては、秘密情報の分散数と演算を行うマシン数は同じである。本実施の形態においては、演算を行うマシン数と秘密分散における分散数が異なるため、演算を行うマシン数をＮ（本実施の形態では１）台とし、秘密分散に関する分散数と閾値はｎ及びｋで表現する（ｎ，ｋは任意の数を選択できるが、以下では説明を簡単にするため最小値のｎ＝ｋ＝２とする）。
【０１２７】
秘密分散を用いた秘匿演算を１台のマシン１４ＮＮでいかに安全に実行させるか、または演算を行うマシン数と秘密情報の分散数が異なる場合どのように秘匿演算を行うかは大きな課題であり、今までそれを実現した例はない。
【０１２８】
第２の実施の形態では、１台のＮＮマシンで秘密分散を安全に実行するために、詳細には後述するが、２つの乱数δ０、δ１を導入し、分散値毎に異なる乱数をかけて演算を行うことが特徴である。
【０１２９】
次に、第２の実施の形態における入力者装置１２のＣＰＵ２２がプログラムを実行することで実現される機能について説明する。プログラムは、分散機能及び演算支援機能を備えている。ＣＰＵ２２がこれらの機能を有するプログラムを実行することで、ＣＰＵ２２は、図１２に示すように、分散部４２及び演算支援部１５０として機能する。
【０１３０】
［分散２］
まず、図１３を参照して、入力者装置１２のＣＰＵ２２における分散部４２が実行する分散２を説明する。
【０１３１】
ステップ１５２で、分散部４２は、乱数α、β、γを生成する。
【０１３２】
ステップ１５４で、分散部４２は、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）を、以下のように計算する。
α（ａ＋１）＝α×（ａ＋１）
β（ｂ＋１）＝β×（ｂ＋１）
γ（ｃ＋１）＝γ×（ｃ＋１）
【０１３３】
ステップ１５６で、分散部４２は、α（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）を１台のマシン１４ＮＮに送信する。
【０１３４】
ステップ１５８で、分散部４２は、乱数δ０、δ１を生成する。
【０１３５】
ステップ１６０で、分散部４２は、δ０／αβ、δ０／α、δ０／β、δ０／γの秘密分散の分散値を計算し、［δ０／αβ］０、［δ０／α］０、［δ０／β］０、［δ０／γ］０とδ０／αβ］１、［δ０／α］１、［δ０／β］１、［δ０／γ］１を得る。
【０１３６】
ステップ１６２で、分散部４２は、以下を計算する（δ＝δ０δ１）。
［δ／αβ］１＝δ１×［δ０／αβ］１
［δ／α］１＝δ１×［δ０／α］１
［δ／β］１＝δ１×［δ０／β］１
［δ／γ］１＝δ１×［δ０／γ］１
ステップ１６４で、分散部４２は、［δ０／αβ］０、［δ０／α］０、［δ０／β］０、［δ０／γ］０と［δ／αβ］１、［δ／α］１、［δ／β］１、［δ／γ］１をマシン１４ＮＮに送信する。
【０１３７】
［積和演算２］
【０１３８】
次に、マシン１４ＮＮのＣＰＵ２２における秘匿積和演算部４４が実行する積和演算２を、図１４を参照して説明する。
【０１３９】
ステップ１７２で、秘匿積和演算部４４は、以下を計算する。
［δ０（ａｂ＋ｃ）］０＝α（ａ＋１）×β（ｂ＋１）×［δ０／αβ］０−α（ａ＋１）×［δ０／α］０−β（ｂ＋１）×［δ０／β］０＋γ（ｃ＋１）×［δ０／γ］０
［δ（ａｂ＋ｃ）］１＝α（ａ＋１）×β（ｂ＋１）×［δ／αβ］１−α（ａ＋１）×［δ／α］１−β（ｂ＋１）×［δ／β］１＋γ（ｃ＋１）×［δ／γ］１
【０１４０】
［演算支援２］
【０１４１】
次に、演算を継続または終了する場合、入力者装置１２のＣＰＵ２２における演算支援部１５０が実行する演算支援２を、図１５を参照して説明する。
【０１４２】
ステップ１８２で、演算支援部１５０は、［δ０（ａｂ＋ｃ）］０と［δ（ａｂ＋ｃ）］１を収集する。
【０１４３】
ステップ１８４で、演算支援部１５０は、［δ（ａｂ＋ｃ）］０＝δ１［δ０（ａｂ＋ｃ）］０を計算する。
【０１４４】
ステップ１８６で、演算支援部１５０は、δ（ａｂ＋ｃ）を復元する。
【０１４５】
ステップ１８７で、演算支援部１５０は、演算を継続するか否かを判断する。これは実行している演算処理がそこで終わるか、継続する処理があるかによって判断される、すなわち入力者が設定したプログラムによる。演算を継続する場合には、ステップ１８８で、演算支援部１５０は、δ（ａｂ＋ｃ＋１）＝δ（ａｂ＋ｃ）＋δを計算する。
【０１４６】
その後、ステップ１９０で、演算支援部１５０は、δ（ａｂ＋ｃ＋１）をマシン１４ＮＮに送信する。
【０１４７】
演算を継続せず演算結果を得る場合は、ステップ１９２で、演算支援部１５０は、δ（ａｂ＋ｃ）をδで割って、ａｂ＋ｃを計算する。
【０１４８】
ただし、加減算を継続する演算を行う場合、演算支援２を行わずに他の［δ０（ａｂ＋ｃ）］０，［δ（ａｂ＋ｃ）］１と係数を合わせて加減算を継続してもよい。また、乗除残においてもα（ａ＋１）×β（ｂ＋１）のように直接繰り返すことができる。すなわち、加減算または乗除算の繰返しにおいては演算支援処理を行わなくてもよく、積和演算のような加減算と乗除算を組み合わせる場合に１度行えば良い。積和演算２において計算される［δ０（ａｂ＋ｃ）］０，［δ（ａｂ＋ｃ）］１は独立に定められた異なる乱数δ０，δがかかっているため、ｋ＝２であっても正しく復元できず、情報理論的安全性が達成できる。
【０１４９】
［演算支援２′］
【０１５０】
次に、入力者装置１２のＣＰＵ２２における演算支援部１５０が実行する演算支援２′を、図１６を参照して説明する。
【０１５１】
ステップ２０２で、演算支援部１５０は、［δ０（ａｂ＋ｃ）］０と［δ（ａｂ＋ｃ）］１を収集する。
【０１５２】
ステップ２０３で、演算支援部１５０は、以下を計算する。
［δ０（ａｂ＋ｃ＋１）］０＝［δ０（ａｂ＋ｃ＋１）］０＋［０］０＋δ０
［δ（ａｂ＋ｃ＋１）］１＝［δ（ａｂ＋ｃ＋１）］１＋［０］１＋δ
ここで、［０］０、［０］１は定数項０の分散値であり、事前に準備できる。
【０１５３】
ステップ２０４で、演算支援部１５０は、演算を継続するか否かを判断する。
【０１５４】
演算を継続する場合には、ステップ２０５で計算結果をマシン１４ＮＮに送信する。
【０１５５】
演算を継続しない場合（ステップ２０４：Ｎ）、ステップ２０６で、演算支援部１５０は、［δ０（ａｂ＋ｃ＋１）］０にδ１を掛けて［δ（ａｂ＋ｃ＋１）］0を生成する。その後、ステップ２０７で、［δ（ａｂ＋ｃ＋１）］０と［δ（ａｂ＋ｃ＋１）］１からδ（ａｂ＋ｃ＋１）を復元してδで割って１を引きａｂ＋ｃを得る。
【０１５６】
このようにすれば、演算支援２′により最終の演算結果を得る場合以外、入力者装置１２の復元の手間はなくなる。
【０１５７】
演算を継続する場合、マシン１４ＮＮはδ（ａｂ＋ｃ＋１）を復元し、それをα（ａ＋１）、β（ｂ＋１）、γ（ｃ＋１）の１つとすれば、演算が連続できることは明らかである。
【０１５８】
また、秘匿積和演算においてｃ＝０とすれば秘匿乗算となり、ａ＝１とすれば秘匿加算となる。また、図１４のステップ１７２で、ａｂ＋ｃの＋を−とし、ａｂ−ｃとする、すなわち＋γ（ｃ＋１）を−γ（ｃ＋１）とすれば秘匿減算となる。
【０１５９】
［秘匿除算２］
【０１６０】
次に、入力者装置１２のＣＰＵ２２における演算支援部１５０（分散部４２でもよい）が実行する秘匿除算２を、図１７を参照して説明する。なお、秘匿除算のための、入力者装置１２のＣＰＵ２２における分散部４２は、図７のステップ８２〜８６を実行する。
【０１６１】
ステップ２２０で、演算支援部１５０は、乱数α″を生成する。
【０１６２】
ステップ２２２で、演算支援部１５０は、以下を計算する。
［α″／α］１＝（α″／α′）［α′／α］１
［α″］１＝（α″／α′）［α′］１
【０１６３】
ステップ２２６で、秘匿除算部４６は、［α′／α］０、［α′］０、［α″／α］１、［α″］１をマシン１４ＮＮに送信する。
【０１６４】
マシン１４ＮＮは、以下を計算して、入力者装置１２に送る。
【０１６５】
［α′ａ］０＝α（ａ＋１）×［α′／α］０−［α′］０
［α″ａ］１＝α（ａ＋１）×［α″／α］１−［α″］１
【０１６６】
そこで、ステップ２２８で、演算支援部１５０は、［α′ａ］０、［α″ａ］１を受信する。
【０１６７】
ステップ２３０で、演算支援部１５０は、［α″ａ］０＝（α″／α′）［α′ａ］０と［α″ａ］１からα″ａを復元する。
【０１６８】
ステップ２３２で、演算支援部１５０は、α″ａ＝０であるか否かを判断する。α″ａ＝０であれば、秘匿除算２を終了する。
【０１６９】
α″ａ＝０でなければ、ステップ２３４で、演算支援部１５０は、１／α″ａを計算する。
【０１７０】
ステップ２３６で、演算支援部１５０は、１／α″ａをα（ａ＋１）として秘匿積和演算２のために秘匿積和演算部４４に送る。これにより、秘匿積和演算部４４により、乗算を除算に変えた結果が得られる。ただし、１／α″ａには１が加えられていないため、秘匿積和演算２のステップ１７２においてβ（ｂ＋１）を減算する計算は省略される。
【０１７１】
秘匿除算２において、図１７のステップ２２２〜２２８は事前に実行でき、ステップ２３０〜２３６が秘匿除算における演算支援となる。また、ステップ２２８〜２３６の処理を演算支援部が行わず、そのままマシン１４ＮＮが行ってもよい。
【０１７２】
また、分散２の図１３のステップ１５６の後に、α、β、γを秘密分散する処理を加え、ステップ１６４の後に、α、β、γを復元する処理を加えれば、分散２のステップ１５２〜１５６と、ステップ１５８〜１６４との間の実行開始時間が大きく異なっても、入力者装置１２のＣＰＵ２２における分散部４２は、秘密情報の秘匿に用いたα、β、γを記憶しておくことなく実行でき、ステップ１５８〜１６４を事前に計算しておかなくても、演算支援として演算中に処理できる。
【０１７３】
第２の実施の形態によってマシン１４ＮＮが１台しかなくても、入力者装置１２の秘密情報及び解こうとする問題が漏洩しないようにすることができる。従来、１台のＮＮマシンしかないとき、秘密分散法は適用できず膨大な計算量を必要とする準同型暗号を用いるしかなかったが、第２の実施の形態によってこの問題を解決できる。
【０１７４】
＜第３の実施の形態＞
次に、第３の実施の形態を説明する。第３の実施の形態の構成は、第１の実施の形態の構成と同様の部分を有するので、同様の部分には、同様の符号を付してその詳細な説明を省略する。
【０１７５】
図１８に示すように、第３の実施の形態の秘密情報分散秘匿演算システムは、ネットワーク１０を介して相互に接続された、複数、例えば、３台の入力者装置１２Ａ〜１２Ｃ、複数（Ｎ個）のマシン１４Ｎ０〜１４Ｎｎ−１、及び復元者装置１８を備えている。第３の実施の形態では、秘密情報ａ、ｂ、ｃをそれぞれ有する３台の入力者装置１２Ａ〜１２Ｃを備え、下記復元者装置１８を備えている点で、第１の実施の形態と異なる。
【０１７６】
次に、第３の実施の形態における復元者装置１８のＣＰＵ２２がプログラムを実行することで実現される機能について説明する。プログラムは、分散値を集めて秘密情報の復元を行う復元機能を備えている。ＣＰＵ２２がこれらの機能を有するプログラムを実行することで、復元者装置１８のＣＰＵ２２は、図１９に示すように、復元部２４２として機能する。
【０１７７】
次に、第３の実施の形態におけるマシン１４Ｎ０〜１４Ｎｎ−１の各々のＣＰＵ２２がプログラムを実行することで実現される機能について説明する。プログラムは、変換用乱数生成機能、秘匿積和演算機能及び秘匿除算機能を備えている。ＣＰＵ２２がこの機能を有するプログラムを実行することで、ＣＰＵ２２は、図２０に示すように、変換用乱数生成部２４４、秘匿積和演算部４４及び秘匿除算部４６として機能する。
【０１７８】
マシン１４Ｎ０〜１４Ｎｎ−１は更に、変換用乱数生成部として機能する。
【０１７９】
第３の実施の形態では、複数（例えば、３台）の入力者装置１２Ａ〜１２Ｃと、結果を知る復元者装置１８とが異なり、複数（最小はｎ＝ｋ＝２）のマシン１４Ｎ０〜１４Ｎｎ−１で秘匿計算する場合を考える。
【０１８０】
ＴＵＳ方式では秘匿加算と秘匿乗算は単独では安全であるが、積和演算のように乗算と加算を組み合わせると、入力者の秘密情報が漏洩するなど安全性に問題があることが知られている。そこで、そのような場合においても安全に秘匿計算が実現できるように変換用乱数の生成が課題となる。なお、第１、２の実施の形態では同一の入出力者装置を仮定するため、ＴＵＳ方式で積和演算を行っても利害が対立する複数の入出力者が存在しないので、上記問題が発生しなかった。
【０１８１】
ここでは、秘密情報ａ，ｂ，ｃをもつ入力者装置（以下、第３の実施の形態では、「入力者」ともいう）が異なり、復元者装置（以下、第３の実施の形態では、「復元者」ともいう）も異なり、利害が対立する場合を考える。また、マシンは複数（最小はＮ＝ｎ＝ｋ＝２）あるとする。また、他の入力者や復元者から自らの秘密情報を守るために以下の変換用乱数を生成する。この変換用乱数は複数の信頼できない入力者によって秘密に生成する方法は知られていなかった。例えば、第１の実施の形態の分散１’の図９のステップ１１２〜１１８のように一台の入力者が生成する方法は知られているが、この入力者は変換用乱数の値を知る。よって、入力者装置が攻撃者であれば、それを用いた秘匿計算は安全ではなく、第１の実施の形態のように入力者装置は信頼できなければならない。それに対して信頼できる入力者がいない場合でも、変換用乱数が特定されない生成方法を以下に示す。
【０１８２】
下記文献３、文献４において、２ｋ次の多項式を用いて生成された分散値をｋ次の多項式に対する分散値に変換する方法が示されている。例えば文献３の手法では、ある規則によって生成された定数を要素とする下記行列Ａを用いて、２ｋ次の多項式に対する分散値ベクトルＷ＝（Ｗ０，Ｗ１，・・・，Ｗ２ｋ−１）に対してＲ＝Ｗ・Ａを計算し、ｋ次の多項式に対する分散値ベクトルＲ＝（Ｒ０，Ｒ１，・・・，Ｒ２ｋ−１）に変換することができる（文献４の手法もほぼ同様の処理で実現できる）。ただし、文献３、４の手法はマシン台数ＮがＮ≧２ｋ−１の場合に有効であるが、本実施例ではＮ＜２ｋ−１、すなわち実際のマシン台数ＮがＮ≧２ｋ−１を満たさない場合を扱う。
【０１８３】
【数２１】
2019144405.tif 000024
【０１８４】
文献３：M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” STOC ’88, 1988, pp. 1−10, ACM Press.
【０１８５】
文献４：Rosario Gennaro, Michael O. Rabin, and Tal Rabin, “Simplified VSS and fast-track multiparty computations with applications to threshold cryptography,” In Brian A. Coen and Yehuda Afek, editors, PODC, 1998, pp. 101−111, ACM.
【０１８６】
以下に、ｕ人の入力者による変換用乱数生成部がＮ＝ｔ＝ｋ台のマシンの変換用乱数生成部２４４を用いて変換用乱数を生成する場合を、図２１を参照して説明する。以下において、入力者は入力者装置を意味し、Ｓｉはマシン１４Ｎｉとすることができる。ただし、この入力者及びＳｉなどは後述の秘匿積和演算を行う各装置と同じである必要はなく、他の秘匿演算システムによって生成されてもよいし、そのシステム自体を変換用乱数生成システムとして専用化してもよい。
【０１８７】
［変換用乱数生成３］
【０１８８】
（処理３（１））
入力者ｉ（ｉ＝０，・・・，ｕ−１）は乱数λｉ，０，・・・，λｉ，ｔ−１，αｉ，０，・・・，αｉ，ｔ−１，βｉ，０，・・・，βｉ，ｔ−１，・・・，γｉ，０，・・・，γｉ，ｔ−１を生成し、以下を計算する。
λｉ＝λ，０×・・・×λｉ，ｔ−１，αｉ＝αｉ，０×・・・×αｉ，ｔ−１，βｉ＝βｉ，０×・・・×βｉ，ｔ−１，・・・，γｉ＝γｉ，０×・・・×γｉ，ｔ−１
【０１８９】
（処理３（２））
入力者ｉはｋ＝ｔ、ｎ＝ｕｔ（厳密にはｎ＝ｕ（ｋ−１）＋１以上）として、λｉをＳｈａｍｉｒ法を用いて秘密分散し、［λｉ］０，・・・，［λｉ］ｕｔ−１を得る。
【０１９０】
（処理３（３））
【０１９１】
入力者ｉは生成した分散値をｔ毎に分割して以下のように乱数を乗じる。
［αｉλｉ］ｔ＝αｉ×［λｉ］ｔ，・・・，［αｉλｉ］２ｔ−１＝αｉ×［λｉ］２ｔ−１，
［βｉλｉ］２ｔ＝βｉ×［λｉ］２ｔ，・・・，［βｉλｉ］３ｔ−１＝βｉ×［λｉ］３ｔ−１，
：
［γｉλｉ］（ｕ−１）ｔ＝γｉ×［λｉ］（ｕ−１）ｔ，・・・，［γｉλｉ］ｕｔ−１＝γｉ×［λｉ］ｕｔ−１
【０１９２】
（処理３（４））
入力者ｉは［λｉ］ｊ，［αｉλｉ］ｊ＋ｔ，［βｉλｉ］ｊ＋２ｔ，・・・，［γｉλｉ］ｊ＋（ｕ−１）ｔ，λｉ，ｊ，αｉ，ｊ，βｉ，ｊ，・・・，γｉ，ｊをマシン１４ＮｊであるマシンＳｊ（ｊ＝０，・・・，ｔ−１）に送る。
【０１９３】
（処理３（５））
Ｓｉ（ｉ＝０，・・・，ｔ−１）は以下を計算する。ただし、下記乗算は分散値同士の乗算であるので、乗算結果はｋ＝ｕ（ｔ−１）＋１、ｎ＝ｕｔとしたＳｈａｍｉｒ法による分散値と等価である。
［λ０λ１・・・λ３］ｉ＝［λ０］ｉ×［λ１］ｉ×・・・×［λｕ−１］ｉ，
【０１９４】
［α０α１・・・α３λ０λ１・・・λ３］ｉ＋ｔ＝［α０λ０］ｉ＋ｔ×［α１λ１］ｉ＋ｔ×・・・×［αｕ−１λｕ−１］ｉ＋ｔ
［β０β１・・・β３λ０λ１・・・λ３］ｉ＋２ｔ＝［β０λ０］ｉ＋２ｔ×［β１λ１］ｉ＋２ｔ×・・・×［βｕ−１λｕ−１］ｉ＋２ｔ
：
［γ０γ１・・・γ３λ０λ１・・・λ３］ｉ＋（ｕ−１）ｔ＝［γ０λ０］ｉ＋（ｕ−１）ｔ×［γ１λ１］ｉ＋（ｕ−１）ｔ×・・・×［γｕ−１λｕ−１］ｉ＋（ｕ−１）ｔ
【０１９５】
（処理３（６））
Ｓｉ（ｉ＝０，・・・，ｔ−１）はα０，ｉ×α１，ｉ・・・×αｕ−１，ｉ，β０，ｉ×β１，ｉ・・・×βｕ−１，ｉ，・・・，γ０，ｉ×γ１，ｉ・・・×γｕ−１，ｉを計算し、Ｓ０に送る。また、λ′ｉ＝λ０，ｉ×λ１，ｉ×λ２，ｉ×・・・×λｕ−１，ｉを計算する。
【０１９６】
（処理３（７））
【０１９７】
Ｓ０は送られてきた全てのα０，ｉ×α１，ｉ・・・×αｕ−１，ｉをかけあわせα０α１・・・αｕ−１を、β０，ｉ×β１，ｉ・・・×βｕ−１をかけあわせβ０β１・・・βｕ−１を、・・・、γ０，ｉ×γ１，ｉ・・・×γｕ−１，ｉをかけあわせγ０γ１・・・γｕ−１を計算し、全マシンに送る。
【０１９８】
（処理３（８））
【０１９９】
Ｓｉ（ｉ＝０，・・・，ｔ−１）は以下を計算する。ただし、λ＝λ０λ１・・・λｕ−１とする。
［λ］ｉ＋ｔ＝［α０α１・・・α３λ０λ１・・・λ３］ｉ＋ｔ／（α０α１・・・α３）
［λ］ｉ＋２ｔ＝［β０β１・・・β３λ０λ１・・・λ３］ｉ＋２ｔ／（β０β１・・・β３）
：
［λ］ｉ＋（ｕ−１）ｔ＝［γ０γ１・・・γ３λ０λ１・・・λ３］ｉ＋（ｕ−１）ｔ／（γ０γ１・・・γ３）
【０２００】
（処理３（９））
Ｓｉ（ｉ＝０，・・・，ｔ−１）は０をｋ＝ｕ（ｔ−１）／２＋１，ｎ＝ｕｔ／２としてＳｈａｍｉｒ法を用いて秘密分散した［０ｉ］ｊを計算し、以下を計算してＲｉ，ｊ，Ｒｉ，ｊ＋ｔ，・・・，Ｒｉ，ｊ＋ｕ‘ｔをＳｊに送る。ただし、ｈ＝０，・・・，２ｔ−１，ｕ’＝ｕ／４であり、ａｉ，ｈは行列Ａの各要素である。
Ｒｉ，ｈ＝ａｉ，ｈ×［λ］ｉ＋ａｉ＋ｔ，ｈ×［λ］ｉ＋ｔ＋ａｉ＋２ｔ，ｈ×［λ］ｉ＋２ｔ＋・・・＋ａｉ＋（ｕ−１）ｔ，h×［λ］ｉ＋（ｕ−１）ｔ＋［０ｉ］ｈ，
【０２０１】
（処理３（１０））
【０２０２】
Ｓｉ（ｉ＝０，・・・，ｔ−１）は以下を計算して得られた［λ］ｉ，・・・，［λ］ｉ＋ｕ”−１を次数が半減された（ｕ”＋１，ｕｔ／２）における分散値とする。ただし、ｕ”＝ｕ（ｔ−１）／２
［λ］ｉ＝Ｒ０，ｉ＋・・・＋Ｒｔ−１，ｉ，［λ］ｉ＋ｕ′＝Ｒ０，ｉ＋ｕ′＋・・・＋Ｒｔ−１，ｉ＋ｕ′，，・・・，
【０２０３】
（処理３（１１））
【０２０４】
Ｓｉ（ｉ＝０，・・・，ｔ−１）は必要な次数になるまで（９）（１０）の次数変換処理を繰り返し、変換用乱数｛λ｝ｉ＝（［λ］ｉ，λ′ｉ）を生成する。
【０２０５】
上記は記述が複雑であるので、ｕ＝４，Ｎ＝ｔ＝ｋ＝２の場合を以下に具体的に記す（図２２も参照）。
【０２０６】
［変換用乱数生成３’］
（処理３′（１））
入力者０は乱数λ０，０，λ０，１，α０，０，α０，１，β０，０，β０，１，γ０，０，γ０，１を生成し、以下を計算する。
λ０＝λ０，０×λ０，１，α０＝α０，０×α０，１，β０＝β０，０×β０，１，γ０＝γ０，０×γ０，１
【０２０７】
（処理３′（２））
入力者０はλ０を（２，８）Ｓｈａｍｉｒ法で秘密分散し、［λ０］０，・・・，［λ０］７を得る。
【０２０８】
（処理３′（３））
入力者０は以下を計算する。
［α０λ０］２＝α０×［λ０］２，［α０λ０］３＝α０×［λ０］３
［β０λ０］４＝β０×［λ０］４，［β０λ０］５＝β０×［λ０］５
［γ０λ０］６＝γ０×［λ０］６，［γ０λ０］７＝γ０×［λ０］７
【０２０９】
（処理３′（４））
入力者０は［λ０］０，［α０λ０］２，［β０λ０］４，［γ０λ０］６，λ０，０，α０，０，β０，０，γ０，０をマシンＳ０に送る。
【０２１０】
（処理３′（５））
入力者０は［λ０］１，［α０λ０］３，［β０λ０］５，［γ０λ０］７，λ０，１，α０，１，β０，１，γ０，１をマシンＳ１に送る。
【０２１１】
（処理３′（６））
入力者１は乱数λ１，０，λ１，１，α１，０，α１，１，β１，０，β１，１，γ１，０，γ１，１を生成し、以下を計算する。
λ１＝λ１，０×λ１，１，α１＝α１，０×α１，１，β１＝β１，０×β１，１，γ１＝γ１，０×γ１，１
【０２１２】
（処理３′（７））
入力者１はλ１を（２，８）Ｓｈａｍｉｒ法で秘密分散し、［λ１］０，・・・，［λ１］７を得る。
【０２１３】
（処理３′（８））
入力者１は以下を計算する。
［α１λ１］２＝α１×［λ１］２，［α１λ１］３＝α１×［λ１］３
［β１λ１］４＝β１×［λ１］４，［β１λ１］５＝β１×［λ１］５
［γ１λ１］６＝γ１×［λ１］６，［γ１λ１］７＝γ１×［λ１］７
【０２１４】
（処理３′（９））
入力者１は［λ１］０，［α１λ１］２，［β１λ１］４，［γ１λ１］６，λ１，０，α１，０，β１，０，γ１，０をマシンＳ０に送る。
【０２１５】
（処理３′（１０））
入力者１は［λ１］１，［α１λ１］３，［β１λ１］５，［γ１λ１］７，λ１，１，α１，１，β１，１，γ１，１をマシンＳ０に送る。
【０２１６】
（処理３′（１２））
入力者２，３も同様の処理を行う。よって、Ｓ０は以下を保持する。
【０２１７】
［λ０］０，［λ１］０，［λ２］０，［λ３］０，［α０λ０］２，［α１λ１］２，［α２λ２］２，［α３λ３］２，［β０λ０］４，［β１λ１］４，［β２λ２］４，［β３λ３］４，［γ０λ０］６，［γ１λ１］６，［γ２λ２］６，［γ３λ３］６，
λ０，０，λ１，０λ２，０λ３，０，α０，０，α１，０，α２，０，α３，０，β０，０，β１，０，β２，０，β３，０，γ０，０，γ１，０，γ２，０，γ３，０
【０２１８】
（処理３′（１３））
Ｓ１は以下を保持する。
【０２１９】
［λ０］１，［λ１］１，［λ２］１，［λ３］１，［α０λ０］３，［α１λ１］３，［α２λ２］３，［α３λ３］３，［β０λ０］５，［β１λ１］５，［β２λ２］５，［β３λ３］５，［γ０λ０］７，［γ１λ１］７，［γ２λ２］７，［γ３λ３］７，
λ０，１，λ１，１λ２，１λ３，１，α０，１，α１，１，α２，１，α３，１，β０，１，β１，１，β２，１，β３，１，γ０，１，γ１，１，γ２，１，γ３，１
【０２２０】
（処理３′（１４））
Ｓ０は以下を計算する。乗算結果は（５，８）Ｓｈａｍｉｒ法による分散値と等価である。
［λ０λ１λ２λ３］０＝［λ０］０×［λ１］０×［λ２］０×［λ３］０，
［α０α１α２α３λ０λ１λ２λ３］２＝［α０λ０］２×［α１λ１］２×［α２λ２］２×［α３λ３］２
［β０β１β２β３λ０λ１λ２λ３］４＝［β０λ０］４×［β１λ１］４×［β２λ２］４×［β３λ３］４
［γ０γ１γ２γ３λ０λ１λ２λ３］６＝［γ０λ０］６×［γ１λ１］６×［γ２λ２］６×［γ３λ３］６
【０２２１】
（処理３′（１５））
【０２２２】
Ｓ１は以下を計算する。乗算結果は（５，８）Ｓｈａｍｉｒ法による分散値と等価である。
［λ０λ１λ２λ３］１＝［λ０］１×［λ１］１×［λ２］１×［λ３］１，
［α０α１α２α３λ０λ１λ２λ３］３＝［α０λ０］３×［α１λ１］３×［α２λ２］３×［α３λ３］３
［β０β１β２β３λ０λ１λ２λ３］５＝［β０λ０］５×［β１λ１］５×［β２λ２］５×［β３λ３］５
［γ０γ１γ２γ３λ０λ１λ２λ３］７＝［γ０λ０］７×［γ１λ１］７×［γ２λ２］７×［γ３λ３］７
【０２２３】
（処理３′（１６））
【０２２４】
Ｓ０はα０，０×α１，０×α２，０×α３，０，β０，０×β１，０×β２，０×β３，０，γ０，０×γ１，０×γ２，０×γ３，０を計算する。また、λ′０＝λ０，０×λ１，０×λ２，０×λ３，０を計算する。
【０２２５】
（処理３′（１７））
【０２２６】
Ｓ１はα０，１×α１，１×α２，１×α３，１，β０，１×β１，１×β２，１×β３，１，γ０，１×γ１，１×γ２，１×γ３，１を計算してＳ０に送る。また、λ′１＝λ０，１×λ１，１×λ２，１×λ３，１を計算する。
【０２２７】
（処理３′（１８））
Ｓ０は以下を計算し、Ｓ１に送る。
【０２２８】
α０α１α２α３＝α０，０α１，０α２，０α３，０×α０，１α１，１α２，１α３，１，
β０β１β２β３＝β０，０β１，０β２，０β３，０×β０，１β１，１β２，１β３，１，
γ０γ１γ２γ３＝γ０，０γ１，０γ２，０γ３，０×γ０，１γ１，１γ２，１γ３，１
（処理３′（１９））
Ｓ０は以下を計算する。ただし、λ＝λ０λ１λ２λ３とする。
【数２２】
2019144405.tif 000025
【０２２９】
（処理３′（２０））
Ｓ１は以下を計算する。
【数２３】
2019144405.tif 000026
【０２３０】
（処理３′（２１））
【０２３１】
Ｓ０は０を（３，４）Ｓｈａｍｉｒ法で秘密分散した［００］ｊを計算し、以下を計算してＲ０，１とＲ０，３をＳ１に送る。ただし、ａｉ，ｊは４次式を２次式に変換する行列Ａにおける位置ｉ，ｊにおける要素である。
Ｒ０，０＝ａ０，０×［λ］０＋ａ２，０×［λ］２＋ａ４，０×［λ］４＋ａ６，０×［λ］６＋［００］０，
Ｒ０，１＝ａ０，１×［λ］０＋ａ２，１×［λ］２＋ａ４，１×［λ］４＋ａ６，１×［λ］６＋［００］１，
Ｒ０，２＝ａ０，２×［λ］０＋ａ２，２×［λ］２＋ａ４，２×［λ］４＋ａ６，２×［λ］６＋［００］２，
Ｒ０，３＝ａ０，３×［λ］０＋ａ２，３×［λ］２＋ａ４，３×［λ］４＋ａ６，３×［λ］６＋［００］３，
【０２３２】
（処理３′（２２））
【０２３３】
Ｓ１は０を（３，４）Ｓｈａｍｉｒ法で秘密分散した［０１］ｊを計算し、以下を計算してＲ１，０とＲ１，２をＳ０に送る。
【０２３４】
Ｒ１，０＝ａ１，０×［λ］１＋ａ３，０×［λ］３＋ａ５，０×［λ］５＋ａ７，０×［λ］７＋［０１］０，
Ｒ１，１＝ａ１，１×［λ］１＋ａ３，１×［λ］３＋ａ５，１×［λ］５＋ａ７，１×［λ］７＋［０１］１，
Ｒ１，２＝ａ１，２×［λ］１＋ａ３，２×［λ］３＋ａ５，２×［λ］５＋ａ７，２×［λ］７＋［０１］２，
Ｒ１，３＝ａ１，３×［λ］１＋ａ３，３×［λ］３＋ａ５，３×［λ］５＋ａ７，３×［λ］７＋［０１］３，
【０２３５】
（処理３′（２３））
Ｓ０は［λ］０＝Ｒ０，０＋Ｒ１，０，［λ］２＝Ｒ０，２＋Ｒ１，２を（３，４）Ｓｈａｍｉｒ法における分散値とし、（２，２）Ｓｈａｍｉｒ法で秘密分散した［００］ｊを計算して以下を計算する。Ｓ０はＲ′０，１をＳ１に送る。ただし、ａ′ｉ，ｊは２次式を１次式に変換する行列Ａ’における位置ｉ，ｊにおける要素である。
Ｒ′０，０＝ａ′０，０×［λ］０＋ａ′２，０×［λ］２＋［００］０，
Ｒ′０，１＝ａ′０，１×［λ］０＋ａ′２，１×［λ］２＋［００］１，
【０２３６】
（処理３′（２４））
【０２３７】
Ｓ１は［λ］１＝Ｒ０，１＋Ｒ１，１，［λ］３＝Ｒ０，３＋Ｒ１，３を（３，４）Ｓｈａｍｉｒ法における分散値とし、（２，２）Ｓｈａｍｉｒ法で秘密分散した［００］ｊを計算して以下を計算する。Ｓ１はＲ′１，０をＳ０に送る。
Ｒ′１，０＝ａ′１，０×［λ］１＋ａ′３，０×［λ］３＋［０１］０，
Ｒ′１，１＝ａ′１，１×［λ］１＋ａ′３，１×［λ］３＋［０１］１，
【０２３８】
（処理３′（２５））
Ｓ０は［λ］０＝Ｒ′０，０＋Ｒ′１，０を（２，２）Ｓｈａｍｉｒ法における分散値とし、｛λ｝０＝（［λ］０，λ′０）を変換用乱数とする。
【０２３９】
（処理３′（２６））
Ｓ１は［λ］１＝Ｒ′０，１＋Ｒ′１，１を（２，２）Ｓｈａｍｉｒ法における分散値とし、｛λ｝１＝（［λ］１，λ′１）を変換用乱数とする。
【０２４０】
変換用乱数生成３においてｕ＝２，ｋ＝２であれば、（７）においてα０α１が復元されるが、入力者が１台のマシンを観察できれば、それから自らが入力した例えばα０でα０α１を割った結果がもう一人の入力者のα１であることがわかる。よって、もう一人の入力者の秘密情報はα１で秘匿されているが、それが解除され２つの分散値が判るため秘密情報λ１が復元され漏洩する。入力者が３人以上であればα０α１α２が復元されるが、残りの乱数を分解できないため各入力者の秘密情報は漏洩しない。ただし、ｕ＝２としたい場合、一人の入力者が入力者０，１となり、もう一人の入力者が入力者２，３となって４つの秘密情報及び乱数を用いれば、例えば入力者０，１は入力者２，３のα２α３を分解できないので、個別の秘密情報は漏洩しない。よって、マシンＳ０，Ｓ１が各々入力者０，１及び入力者２，３となれば変換用乱数をマシン間で自動的に生成できる。逆に、ｕ＞４であっても、（１）〜（４）の処理を各入力者が行うことにより実現できることは明らかである。また例えば、ｕ＝３，ｔ＝４，ｋ＝３として入力者ｉ（ｉ＝０，１，２）は秘密情報λｉを（３，１２）Ｓｈａｍｉｒ法で秘密分散し、３つの分散値を乗算して（７，１２）Ｓｈａｍｉｒ法に対応する乗算結果を得るが、１回次数変換処理を行えば（４，６）Ｓｈａｍｉｒ法に対応する変換用乱数を得ることができる。この（４，６）Ｓｈａｍｉｒ法に対応する変換用乱数を各マシンが１つずつ持つことにより（４，４）Ｓｈａｍｉｒ法に対応する変換用乱数とできる。よって、演算を行うマシン数ｔとｋは同じとする必要はなく、最終的に設定されるｋも当初のｋと変えることができる。また、（９）〜（１０）の次数変換を行う回数もｕ，ｔ，ｋの設定及び最終的に必要な分散式の次数により異なる。変換用乱数生成３’においてｕ＝４とする理由は上記よりｕ＞２である必要があり、ｕ＝３，ｔ＝ｋ＝２であれば乗算結果はｕ（ｋ−１）より３次式となり、半減できないためである。
【０２４１】
また、変換用乱数生成の安全性としては以下が言える。変換用乱数生成３’において、例えばＳ０は一つの秘密情報λ３について［λ３］０，［α３λ３］２，［β３λ３］４，［γ３λ３］６と４個の分散値を持つが、これらは異なる乱数がかけられているため、ｋ＝２であっても解くことができない。また、処理３′（１９）、（２０）において乱数が外され、例えばＳ０は［λ］０，［λ］２，［λ］４，［λ］６の４個の分散値を持つが、この分散値は分散値同士の乗算結果であるので、５個集めなければ解けない。また、（２３）において次数が半減され３個集めればよくなるが、Ｓ０は［λ］０，［λ］２の２個しか持たない。最後に、もう１度次数削減され、２個集めればよくなるが、Ｓ０は［λ］０しか持たないので解けない。よって、この手法によって生成された変換用乱数の値は二人以上の入力者が結託しないならば、誰も知らない値となる。よって、この手法は情報理論的安全性をもつといえる。ただし上記において、行列ＡとＡ’の積をＡ”としてその各要素をかけて２回の次数変換を１回にしてもよい。
【０２４２】
以下では上記変換用乱数生成処理によって、変換用乱数
【数２４】
2019144405.tif 000027
が事前に準備されているとする。
【０２４３】
［分散３］
【０２４４】
次に、入力者装置１２ＡのＣＰＵ２２における分散部４２が実行する分散３を、図２３を参照して説明する。
【０２４５】
ステップ４０２で、分散部４２は、ｋ個の乱数α０、α１、・・・、αｋ−１を生成する。
【０２４６】
ステップ４０４で、分散部４２は、以下を計算する。
【０２４７】
α（ａ＋１）＝α×（ａ＋１）（α＝α０α１・・・αｋ−１）
【０２４８】
ステップ４０６で、分散部４２は、α＝α０α１・・・αｋ−１を構成する乱数αｉを対応するマシン１４Ｎｉに送信する。
【０２４９】
入力者装置１２Ｂ、１２Ｃも、図２３と同様の処理を実行する。例えば、ステップ４０４では、入力者装置１２Ｂ、１２Ｃの分散部４２はそれぞれ、β０、β１、・・・、βｋ−１、γ０、γ１、・・・、γｋ−１を生成し、以下を計算する。
【０２５０】
β（ｂ＋１）＝β×ｂ（β＝β０β１・・・βｋ−１）
【０２５１】
γ（ｃ＋１）＝γ×ｃ（γ＝γ０γ１・・・γｋ−１）
【０２５２】
αｉ、βｉ、γｉ（ｉ＝０、・・・、ｋ−１）を秘密分散して、必要時にマシンＳｉがαｉ、βｉ、γｉを復元してもよい。
【０２５３】
［秘匿積和演算３］
【０２５４】
次に、マシン１４Ｎ０〜１４Ｎｎ−１のＣＰＵ２２における秘匿積和演算部４４が実行する秘匿積和演算３を、図２４を参照して説明する。
【０２５５】
ステップ４１２で、秘匿積和演算部４４は、以下を計算する。
［φωαβ（ａ＋１）（ｂ＋１）］ｉ＝α（ａ＋１）×β（ｂ＋１）×［φ］ｉ
［εηα（ａ＋１）］ｉ＝α（ａ＋１）×［ε］ｉ
［λμβ（ｂ＋１）］ｉ＝β（ｂ＋１）×［μ］ｉ
［τργ（ｃ＋１）］ｉ＝γ（ｃ＋１）×［ρ］ｉ
【０２５６】
ステップ４１４で、秘匿積和演算部４４は、乱数δｊ∈Ｚ／ｐＺを生成する。
【０２５７】
ステップ４１６で、秘匿積和演算部４４は、以下を計算し、ステップ４１８で、秘匿積和演算部４４は、以下の計算値を、予め定めたマシン１４Ｎ０に送信する。
【数２５】
2019144405.tif 000028
【０２５８】
予め定めたマシン１４Ｎ０は、以下を計算し、他のマシンに送信するので、ステップ４２０で、秘匿積和演算部４４は、以下の計算値を受信する。
【数２６】
2019144405.tif 000029
【０２５９】
ステップ４２２で、秘匿積和演算部４４は、以下を計算する。
【０２６０】
【数２７】
2019144405.tif 000030
【０２６１】
ステップ４２４で、秘匿積和演算部４４は、δｊを保存する。
【０２６２】
δｊをＳｊが秘密分散して、権限をもつ復元者が必要時に復元してもよい。
【０２６３】
演算結果を得るには復元者装置１８の復元部２４２は［δ（ａｂ＋ｃ）］ｉをｋ個集めて復元し、保存しているδｉを集めて、復元したδで割れば積和演算結果であるａｂ＋ｃが得られる。
【０２６４】
また、秘匿積和演算においてｃ＝０とすれば秘匿乗算となり、ａ＝１とすれば秘匿加算となる。また、ステップ４２２のγ（ｃ＋１）の前の＋を−とすれば秘匿減算となる。
【０２６５】
（秘匿除算３）
【０２６６】
また、秘匿除算は以下のように行う。ただし、分散３においてマシン１４Ｎｉは徐算用の分散値［α′ａ］ｉとα′を構成するα′ｉをもつとする。
【０２６７】
予め定められたマシン１４Ｎ０は、ｋ台のサーバより［α′ａ］ｉを収集し、一時的にα′ａを復元する。このとき、α′ａ＝０となった場合、除数が０であるので演算を中止する。α′ａ＝０でない場合、マシン１４Ｎ０は、１／α′ａを計算し、他のマシンに送信する。その後、積和演算３において１／α′ａをα（ａ＋１）として扱うことによって、秘匿除算が実行される。ただし、１／α′ａは１が加えられていないので、ステップ４２２でμβ（ｂ＋１）を削減する処理は省略される。
【０２６８】
演算の連続及び演算の秘匿も第１の実施の形態と同様に実現できることは明らかである。また、変換用乱数は誰も知らないので、攻撃者となる１入力の入力者と復元者が結託した場合でも秘密情報にかけられた乱数を知ることができず、ＴＵＳ方式の問題点で説明した解析ができなくなり、利害関係が対立する入出力者間であっても情報理論的に安全な秘匿積和演算が実現される。
【０２６９】
第３の実施の形態によって多くの人または組織が協力してＮＮマシンの学習などを実現することができる。これによって、各入力者装置の入力情報は他の入力者装置及び復元者装置に漏えいせず、その学習結果などを公開できるようになる。また、第３の実施の形態は最小ｎ＝ｋ＝２台のＮＮマシンによって実現でき、少なくとも１つのＮＮマシンの情報が漏えいしなければ安全であり、一般のビッグデータへの応用が可能である。よって、第３の実施の形態によって、ＴＵＳ方式で実現できなかった積和演算を含むどのような場合にも適用できる安全な秘匿演算を実現する。
【０２７０】
＜第４の実施の形態＞
【０２７１】
第４の実施の形態の構成は、図２５に示すように、第３の実施の形態の構成（図１８）と同様の構成があるので、同一部分には同一の符号を付して、その説明を省略し、異なる部分を説明する。第４の実施の形態では、演算支援装置１６を備えている。第４の実施の形態における入力者装置１２Ａ０〜１２Ｃ０は、演算支援部を備えていない。演算支援装置１６が、演算支援部を備えている。第４の実施の形態では、マシン１４Ｎ０〜１４Ｎｎ−１の内の予め定められた１台のマシン１４ＮＮ（マシン数Ｎ＝１、ｎ＝ｋ＝２）が秘匿演算を行う。ただし、演算支援装置１６は後述するように復元処理も行えるので、復元者装置１８はなくてもよい。第２の実施の形態と同様に秘密分散に関するｎ及びｋは最小値である２（任意の数を選択できる）として説明する。
【０２７２】
入力者装置１２Ａ〜１２Ｃの各々のＣＰＵ２２の機能部は、図３に示すように、分散部４２を備える。マシン１４ＮＮのＣＰＵ２２の機能部は、図４に示すように、秘匿積和演算部４４及び秘匿除算部４６を備える。演算支援装置１６のＣＰＵ２２の機能部は、図１２に示すように、分散部４２と演算支援部１５０を備える。
【０２７３】
第４の実施の形態では、複数の秘密情報の入力者装置１２Ａ〜１２Ｃと、結果を知る復元者装置１８とが異なり、かつ１台の演算支援装置と１台のマシン１４ＮＮで秘匿演算を実行する。
【０２７４】
第４の実施の形態では、利害が対立する入力者装置１２Ａ〜１２Ｃの間で１台のマシン１４ＮＮによって秘匿計算を実現するために、信頼できる演算支援装置が1台あるとする。また、各入力者装置１２Ａ〜１２Ｃはその演算支援装置と暗号などを用いた安全な通信路を確保しているとする。
【０２７５】
演算支援装置はマシン１４Ｎ０〜１４Ｎｎ−１に比べて非常に小さな処理でよく、マシン１４ＮＮの処理は攻撃者が知ることができるが、演算支援装置の処理は漏えいしないとする。
【０２７６】
詳細は後述するが、１台のＮＮマシンで秘匿計算を行う第２の実施の形態との大きな違いは入力者からの攻撃を想定する点である。第２の実施の形態における入力者は全ての情報を知るため攻撃する必要はなく、ＮＮマシン及びそれを観察できる者だけが攻撃者であった。それに対して、本実施の形態における入力者は部分的な情報しか知らず、他の入力者及び演算結果を知るための攻撃を行う可能性がある、よって、積和演算自体を入力者から秘匿するため、１のような定数ではなく、第１の乱数ａ１を秘密情報に加算して第２の乱数αを乗じたα（ａ＋ａ１）を公開する。これによって、入力者による攻撃を防ぐ。
【０２７７】
［分散４］
【０２７８】
各入力者装置１２Ａ〜１２Ｃから安全な通信路を介して得た秘密情報a,ｂ,ｃに対する演算支援装置のＣＰＵ２２における分散部４２が実行する分散４を、図２６を参照して説明する。
【０２７９】
ステップ４３２で、分散部４２は、乱数α、β、γと乱数ａ１、ｂ１、ｃ１を生成する。
【０２８０】
ステップ４３４で、分散部４２は、以下を計算する。
α（ａ＋ａ１）＝α×（ａ＋ａ１）
β（ｂ＋ｂ１）＝β×（ｂ＋ｂ１）
γ（ｃ＋ｃ１）＝γ×（ｃ＋ｃ１）
【０２８１】
ステップ４３６で、分散部４２は、α（ａ＋ａ１）、β（ｂ＋ｂ１）、及びγ（ｃ＋ｃ１）を、１台のマシン１４ＮＮに送信する。
【０２８２】
ステップ４３８で、分散部４２は、乱数δ０、δ１を生成する。
【０２８３】
ステップ４４０で、分散部４２は、δ０／αβ、δ０ｂ１／α、δ０ａ１／β、δ０／γを計算する。
【０２８４】
ステップ４４２で、分散部４２は、δ０／αβ、δ０ｂ１／α、δ０ａ１／β、δ０／γの秘密分散における以下の分散値［δ０／αβ］０、［δ０ｂ１／α］０、［δ０ａ１／β］０、［δ０／γ］０と［δ０／αβ］１、［δ０ｂ１／α］１、［δ０ａ１／β］１、［δ０／γ］１を計算する。
【０２８５】
ステップ４４４で、分散部４２は、以下の計算（δ＝δ０δ１）をする。
［δ／αβ］１＝δ１［δ０／αβ］１
［δｂ１／α］１＝δ１［δ０ｂ１／α］１
［δａ１／β］１＝δ１［δ０ａ１／β］１
［δ／γ］１＝δ１［δ０／γ］１
【０２８６】
ステップ４４６で、分散部４２は、［δ０／αβ］０、［δ０ｂ１／α］０、［δ０ａ１／β］０、［δ０／γ］０と［δ／αβ］１、［δｂ１／α］１、［δａ１／β］１、［δ／γ］１を１台のマシン１４ＮＮに送信する。
【０２８７】
［積和演算４］
次に、マシン１４ＮＮのＣＰＵ２２における秘匿積和演算部４４が実行する積和演算４を、図２７を参照して説明する。
【０２８８】
ステップ４５２で、秘匿積和演算部４４は、以下の計算をする。
［δ０｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］０＝α（ａ＋ａ１）×β（ｂ＋ｂ１）×［δ０／αβ］０−α（ａ＋ａ１）×［δ０ｂ１／α］０−β（ｂ＋ｂ１）×［δ０ａ１／β］０＋γ（ｃ＋ｃ１）×［δ０／γ］０
［δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］１＝α（ａ＋１）×β（ｂ＋１）×［δ／αβ］１−α（ａ＋１）×［δｂ１／α］１−β（ｂ＋１）×［δａ１／β］１＋γ（ｃ＋１）×［δ／γ］１
【０２８９】
［演算支援４］
次に、演算支援装置１６のＣＰＵ２２における演算支援部が実行する演算支援４を、図２８を参照して説明する。
【０２９０】
ステップ４６２で、演算支援部は、［δ０｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］０と［δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］１を収集する。
【０２９１】
ステップ４６４で、演算支援部は、以下を計算する。
［δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）］０＝δ１［δ０｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］０
【０２９２】
ステップ４６６で、演算支援部は、［δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］０と［δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝］１からδ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）を復元する。
【０２９３】
ステップ４６８で、演算支援部は、δ（ａｂ＋ｃ＋ｄ１）を計算する。ここで、ｄ１＝（ｃ１−ａ１ｂ１）としてもよいが、δ｛（ａｂ＋ｃ）−（ａ１ｂ１−ｃ１）｝にδ（ａ１ｂ１−ｃ１）を足して、新たに生成した乱数δｄ１を足してもよい。
【０２９４】
ステップ４７０で、演算支援部は、演算を継続するか否かを判断し、演算を継続しない場合には、ステップ４７２で、演算支援部は、上記においてδｄ１を足さずにδで割ることによりａｂ＋ｃを計算する。
【０２９５】
演算を継続する場合、分散４の図２６のステップ４３８〜４４４の処理は演算手順が判っていれば事前に実行できる。よって、演算中に行われる必須の演算支援処理は演算支援処理４のみとなる。また、演算支援処理は積和演算毎に実行しなくても必要に応じて実行すればよい。例えば、Σδ０（ａｉ＋１）（ｂｉ＋１）などの処理では演算後に１度演算支援処理をするだけでよい。
【０２９６】
［秘匿除算４］
次に、演算支援装置１６のＣＰＵ２２における演算支援部２５４が実行する秘匿除算４を説明する。本実施の形態における秘匿除算４は、前述した秘匿除算２（図１７）において、入力者装置１２のＣＰＵ２２における演算支援部１５０が実行した処理を、演算支援装置１６のＣＰＵ２２における演算支援部２５４が実行する点のみが異なるので、その説明を省略する。
【０２９７】
第４の実施の形態によって１台のマシン１４ＮＮと１台の演算支援装置の組み合わせによって、入力者装置及び復元者装置などの利害関係が対立しても安全な秘匿計算が実現できるようになる。一般に、マシン１４ＮＮはその制御を担当するＩＣチップまたは専用の制御装置などとセットで動作する場合が多い。よって、そのＩＣチップまたは専用の制御装置に耐タンパ性を持たせ、第４の実施の形態による演算支援機能を追加すれば、大きなシステム変更を伴わず本実施の形態が実現できる。すなわち、マシン１４ＮＮは高速演算器として動作し、その動作を観察されてもＩＣチップまたは制御装置が安全であれば、入力情報や解こうとする問題が漏えいしないシステムが構成できる。ただし、演算支援装置１６は第２の実施の形態における１個の入力者装置と同様に全ての情報を知るので、演算支援装置１６が解析されると秘密情報及び秘匿演算結果が漏洩する。
【０２９８】
＜第５の実施の形態＞
次に、第５の実施の形態を説明する。
第５の実施の形態の構成は、第４の実施の形態の構成（図２５参照）と同様であるので、その説明を省略する。
【０２９９】
第５の実施の形態において、第４の実施の形態のように演算支援装置を絶対としなくても第３の実施の形態のような安全性が実現できる手法を考える。第４の実施の形態においては演算支援装置が解析できれば、全ての秘密情報が漏洩する。これは、演算支援装置が第２の実施の形態における入力者のように全ての情報を１元的に管理するためである。これに第３の実施の形態の要素を加え、秘密分散における処理量がＮＮマシンは大きく演算支援装置は小さいという特徴を生かしながら、１台のマシン１４ＮＮと演算支援装置の両方を解析しなければ秘密情報が漏洩しないようにすることが課題である。第５の実施の形態においてもＮ＝１，ｎ＝ｋ＝２として説明する。
【０３００】
第４の実施の形態では演算支援装置は全ての秘密情報を知るため、演算支援装置だけ攻撃できれば全秘密情報が漏えいする。そこで、第４の実施の形態のように利害が対立する入力者装置間でも１台のマシンで演算可能で、かつ第３の実施の形態のように１台のマシンと演算支援装置の２つが解析されない限り安全な実施の形態を示す。また、第３の実施の形態と同様に変換用乱数を生成するが、演算支援装置は信頼できるとするので、第１の実施の形態の（１−２）と同等に変換用乱数は演算支援装置が生成する。よって、分散５において変換用乱数｛μ′｝ｉ、｛ν′｝ｉ、｛ε′｝ｉ、｛ρ′｝ｉ、｛ω′｝ｉは準備されているとする。
【０３０１】
[分散５]
分散５を、入力者装置１２Ａの分散５のプログラムのフローチャート（図２９Ａ）、入力者装置１２Ｂの分散５のプログラムのフローチャート（図２９Ｂ）、入力者装置１２Ｃの分散５のプログラムのフローチャート（図２９Ｃ）、演算支援装置１６の分散５のプログラムのフローチャート（図２９Ｄ）、マシン１４ＮＮの分散５のプログラムのフローチャート（図２９Ｅ）、及び分散５のシーケンス図（図２９Ｆ）を参照して説明する。
【０３０２】
（分散５（１））
入力者装置１２Ａは乱数α′０、α′１を生成して以下を計算してα′（ａ＋１）をマシン１４ＮＮと演算支援装置１６に送信し、マシン１４ＮＮにα′０を送信し、演算支援装置１６にα′１を送信する（図２９Ａのステップ５０２Ａ〜５０８Ａ、図２９Ｄのステップ５１２、図２９Ｅのステップ５５２も参照）。
α′＝α′０×α′１、    α′（ａ＋１）＝α′×（ａ＋１）
【０３０３】
入力者装置１２Ｂは乱数β′０、β′１を生成して以下を計算してβ′（ｂ＋１）をマシン１４ＮＮと演算支援装置１６に送信し、マシン１４ＮＮにβ′０を送信し、演算支援装置１６にβ′１を送信する（図２９Ｂのステップ５０２Ｂ〜５０８Ｂ、図２９Ｄのステップ５１４、図２９Ｅのステップ５５４も参照）。
β′＝β′０×β′１、    β′（ｂ＋１）＝β′×（ｂ＋１）
【０３０４】
入力者装置１２Ｃは乱数γ′０、γ′１を生成して以下を計算してγ′（ｃ＋１）をマシン１４ＮＮと演算支援装置１６に送信し、マシン１４ＮＮにγ′０を送信し、演算支援装置１６にγ′１を送信する（図２９Ｃのステップ５０２Ｃ〜５０８Ｃ、図２９Ｄのステップ５１６、図２９Ｅのステップ５５６も参照）。
γ′＝γ′０×γ′１、    γ′（ｃ＋１）＝γ′×（ｃ＋１）
【０３０５】
α′ｉ、β′ｉ、γ′ｉ（ｉ＝０、・・・、ｋ−１）を秘密分散して、必要時にマシン１４ＮＮ及び演算支援装置１６がα′ｉ、β′ｉ、γ′ｉを復元してもよい。
【０３０６】
（分散５（２））
【０３０７】
マシン１４ＮＮは、２以上の乱数ａ００、ａ０１を生成し、ａ０＝ａ００×ａ０１を計算して、ａ０からａ０′＝ａ０−１を計算し、乱数ξａ０、０、ξａ０．１とξ′ａ０、０、ξ′ａ０．１を生成して、ξａ０＝ξａ０、０×ξａ０．１、ξ′ａ０＝ξａ０×ａ０を計算し、ξ′ａ０×ａ０′と、ξａ０．１、ξ′ａ０、１、ａ０１を演算支援装置１６に送信する（図２９Ｅのステップ５５８〜５６８、図２９Ｄのステップ５１８参照）。
【０３０８】
（分散５（３））
【０３０９】
演算支援装置１６は、０でない乱数ａ１０、ａ１１、ξａ１、０、ξａ１．１を生成してａ１＝ａ１０×ａ１１、ξａ１＝ξａ１、０×ξａ１．１を計算してξａ１×ａ１とξａ１、０をマシン１４ＮＮに送信する（図２９Ｄのステップ５２０〜５２４、図２９Ｅのステップ５７０参照）。
【０３１０】
マシン１４ＮＮは乱数α０、α′０を生成し（図２９Ｅのステップ５７２参照）、演算支援装置１６は乱数α１、α′１を生成し（図２９Ｄのステップ５２６）、マシン１４ＮＮは、以下を計算し（図２９Ｅのステップ５７４）、演算支援装置１６は以下を計算し、マシン１４ＮＮに送る（図２９Ｄステップ５２８、図２９Ｅのステップ５７６参照）（以降、マシン１４ＮＮはｉ=０、演算支援装置１６はｉ＝１に対応する計算を行う）。
【０３１１】
【数２８】
2019144405.tif 000031
【０３１２】
（分散５（４））
【０３１３】
マシン１４ＮＮは、
【０３１４】
【数２９】
2019144405.tif 000032
【０３１５】
をｉ＝０，１について掛け合わせ、（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）、（Ｅ）、即ち、それぞれ
【０３１６】
【数３０】
2019144405.tif 000033
【０３１７】
を計算して、演算支援装置１６に送る（図２９Ｅのステップ５７８、５８０、図２９Ｄのステップ５３０参照）。
【０３１８】
（分散５（５））
【０３１９】
マシン１４ＮＮはｉ＝０に対応する下記式を計算し（図２９Ｅのステップ５８２）、演算支援装置１６はｉ＝１に対応する下記式を計算する（図２９Ｄのステップ５３２）。ただし、ａ０＋ａ１＝ａ２とする。
【０３２０】
【数３１】
2019144405.tif 000034
【０３２１】
2019144405.tif 000035
【０３２２】
（分散５（６））
【０３２３】
演算支援装置１６はｉ＝１に対応する［α″ａ２］１、［α（ａ＋ａ２）］１をマシン１４ＮＮに送信し（図２９Ｄのステップ５３４、図２９Ｅのステップ５８４参照）、マシン１４ＮＮはα″ａ２、α（ａ＋ａ２）を復元する（図２９Ｅのステップ５８６参照）。
【０３２４】
（分散５（７））
【０３２５】
マシン１４ＮＮと演算支援装置１６は分散５（１）〜（６）をｂ、ｃに対しても実行し、β（ｂ＋ｂ２）、β″ｂ２、γ（ｃ＋ｃ２）、γ″ｃ２を得る（図２９Ｄのステップ５３６、図２９Ｅのステップ５８８、図２９Ａ〜２９Ｃも参照）。
【０３２６】
（分散５（８））
【０３２７】
演算支援装置１６は乱数χと乱数ε、τ、ω、λ、κ、ζを生成して、ε、τ、ω、λ、κ、ζを秘密分散して以下を計算し、変換用乱数｛ε｝、｛τ｝、｛ω｝、｛λ｝、｛κ｝、｛ζ｝をマシン１４Ｎ０に送る（図２９Ｄのステップ５４０、５４２参照）。
［χε］１＝χ×［ε］１
［χτ］１＝χ×［τ］１
［χφω］１＝χ×［φ］１
［χλ］１＝χ×［λ］１
［χκ］１＝χ×［κ］１
［χζ］１＝χ×［ζ］１
｛ε｝＝（［ε］０、［χε］１、ε０）
｛ρ｝＝（［ρ］０、［χρ］１、ρ０）
｛ω｝＝（［ω］０、［χω］１、ω０）
｛μ｝＝（［μ］０、［χμ］１、μ０）
｛ν｝＝（［ν］０、［χν］１、ν０）
｛ζ｝＝（［ζ］０、［χζ］１、ζ０）
【０３２８】
第３の実施の形態で説明した複数の入力者による変換用乱数生成３’を用いて変換用乱数が生成されている場合、Ｓ１に相当する演算支援装置１６が最終結果である例えば［ε］１とε１を得、Ｓ０に相当するマシン１４Ｎ０が［ε］０とε０を既に得ている。この場合、演算支援装置１６はステップ５３８の乱数生成を省略でき、ステップ５４０の処理を行った後、ステップ５４２において例えば［χε］１のみをマシン１４Ｎ０に送ればよい（他のτ、ω、λ、κ、ζも同様）。
［秘匿積和演算５］
【０３２９】
次に、マシン１４ＮＮのＣＰＵ２２における秘匿積和演算部４４が実行する秘匿積和演算５と、演算支援装置１６のＣＰＵ２２における演算支援部１５０が実行する演算支援５とをそれぞれ、図３０、図３１を参照して説明する。
【０３３０】
図３０のステップ６０２で、マシン１４ＮＮの秘匿積和演算部４４は、乱数δ０∈Z/pZを生成する。
【０３３１】
図３１のステップ６１２で、演算支援装置１６の演算支援部１５０は、乱数δ１∈Z/pZを生成する。
【０３３２】
図３０のステップ６０４で、マシン１４ＮＮの秘匿積和演算部４４は、ｉ＝０として以下を計算する。
【０３３３】
【数３２】
2019144405.tif 000036
【０３３４】
を送信する。
【０３３５】
図３１のステップ６１４で、演算支援装置１６の演算支援部１５０は、ｉ＝１として以下を計算して、ステップ６１６でマシン１４ＮＮに送る。
【０３３６】
【数３３】
2019144405.tif 000037
【０３３７】
図３０のステップ６０６で、マシン１４ＮＮのＣＰＵ２２における秘匿積和演算部４４は、上記２つの式（ｉ＝０，１）を掛け合わせ、以下を計算する。
【０３３８】
【数３４】
2019144405.tif 000038
【０３３９】
図３０のステップ６０８で、マシン１４ＮＮのＣＰＵ２２における秘匿積和演算部４４は、以下を計算する。
【０３４０】
【数３５】
2019144405.tif 000039
【０３４１】
【数３６】
2019144405.tif 000040
【０３４２】
［演算支援処理５］
次に、演算支援装置１６のＣＰＵ２２における演算支援部１５０が実行する演算支援処理５を、図３２を参照して、説明する。
【０３４３】
ステップ６２２で、演算支援部１５０は、［δ０（ａｂ＋ｃ）］０と［δ（ａｂ＋ｃ）］１を収集する。
【０３４４】
ステップ６２４で、演算支援部１５０は、以下を計算する。
［δ｛（ａｂ＋ｃ）］０＝δ１［δ０（ａｂ＋ｃ）］０
【０３４５】
ステップ６２６で、演算支援部１５０は、［δ（ａｂ＋ｃ）］０と［δ（ａｂ＋ｃ）］１からδ（ａｂ＋ｃ）を復元する。
【０３４６】
演算を継続する場合、マシン１４Ｎ０と演算支援装置１６は新たにａ０、ａ１に相当する乱数を生成し、それらを秘匿加算したものを新たなα″ａ２、さらに復元したδ（ａｂ＋ｃ）とα″ａ２を秘匿加算したものを新たなα（ａ＋ａ２）とすればよい。
【０３４７】
秘匿徐算はａ２を秘匿徐算４におけるａ１とすれば、同様に実現可能である。
【０３４８】
本実施の形態において演算支援装置１６は秘密情報ａ，ｂ，ｃを知らず、それらを復元することなく、演算支援装置１６はとマシン１４ＮＮによって生成された乱数の秘匿加算を行い、入力者が知らない第１の乱数の加算と第２の乱数の乗算を行う。よって、攻撃者が演算支援装置１６を攻撃しただけでは秘密情報は漏洩せず、マシン１４ＮＮも一緒に解析しなければ秘密情報は漏洩しない。よって、第５の実施の形態によって演算支援装置のみが解析されても安全なシステムが構築できる。
【０３４９】
また、第２、第４の実施の形態において演算を継続する場合、入力者装置１２は新たなα，β，γに対して新たなδ０を生成し、δ０／αβ、δ０／α、δ０／β、δ０／γを計算する必要があるが、本実施の形態と同様に、例えば｛ε｝＝（［ε］０、［χε］１、ε０）となる変換用乱数をマシン１４ＮＮに送り（他の変換用乱数も同様）、秘匿積和演算２及び４において秘匿積和演算５と同様の演算を行えば、演算を継続するためにδ０／αβ、δ０／α、δ０／β、δ０／γを演算中に計算する必要がなくなる（ただし、図３０でａ０＝ｂ０＝０、α″＝β″＝γ″＝０であり、第２の実施の形態のみａ１＝ｂ１＝ｃ２＝１とする。それに伴いａ０、ｂ０等に関する図３０、３１の演算は省略される）。すなわち、｛ε｝＝（［ε］０、［χε］１、ε０）の形式の変換用乱数が事前に準備されていればよい。
【０３５０】
第１の実施の形態〜第５の実施の形態では、秘匿演算するマシンが１台または２台を例として説明されたが、１台または２台のマシンを用いて秘匿計算を行う場合に汎用的に用いることができる。
【０３５１】
以上より、秘匿演算するマシンが１台の場合、入力者装置が１台であれば第２の実施の形態が最も高速であり、複数台であり演算支援装置が耐タンパ性を有していれば第４の実施の形態が、複数名であり演算装置も解析される可能性がある場合、第５の実施の形態が推奨される。
【０３５２】
また、秘匿演算するマシンを２台利用できる場合、入力者装置が１台であれば第１の実施の形態が最も高速であり、複数台であれば第３の実施の形態が推奨される。
【符号の説明】
【０３５３】
１２  入力者装置
１４Ｎ０〜１４Ｎｎ−１  マシン
【図１】
2019144405.tif 000041
【図２】
2019144405.tif 000042
【図３】
2019144405.tif 000043
【図４】
2019144405.tif 000044
【図５】
2019144405.tif 000045
【図６】
2019144405.tif 000046
【図７】
2019144405.tif 000047
【図８】
2019144405.tif 000048
【図９】
2019144405.tif 000049
【図１０】
2019144405.tif 000050
【図１１】
2019144405.tif 000051
【図１２】
2019144405.tif 000052
【図１３】
2019144405.tif 000053
【図１４】
2019144405.tif 000054
【図１５】
2019144405.tif 000055
【図１６】
2019144405.tif 000056
【図１７】
2019144405.tif 000057
【図１８】
2019144405.tif 000058
【図１９】
2019144405.tif 000059
【図２０】
2019144405.tif 000060
【図２１】
2019144405.tif 000061
【図２２】
2019144405.tif 000062
【図２３】
2019144405.tif 000063
【図２４】
2019144405.tif 000064
【図２５】
2019144405.tif 000065
【図２６】
2019144405.tif 000066
【図２７】
2019144405.tif 000067
【図２８】
2019144405.tif 000068
【図２９Ａ】
2019144405.tif 000069
【図２９Ｂ】
2019144405.tif 000070
【図２９Ｃ】
2019144405.tif 000071
【図２９Ｄ】
2019144405.tif 000072
【図２９Ｅ】
2019144405.tif 000073
【図２９Ｆ】
2019144405.tif 000074
【図３０】
2019144405.tif 000075
【図３１】
2019144405.tif 000076
【図３２】
2019144405.tif 000077