秘密計算システム、秘密計算方法、計算装置

【課題】計算効率と通信効率が従来方法よりも優れた秘密計算方法を提供する。
【解決手段】本発明の秘密計算システムは、３つの計算装置から構成され、数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、ａ_１＝ａ_２２＋ａ_２３,ａ_２＝（ａ_２１，ａ_２２）,ａ_３＝（ａ_２１，ａ_２３）、（ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ）の関係を有し、計算装置Ｘが第１断片を、計算装置Ｙが第２断片を、計算装置Ｚが第３断片を記録する。そして、単純な協調計算によって、算術計算、論理回路演算、それらの演算の組合せも実現できる。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関し、ある演算に対して分散された入力データを復元することなく演算結果を得るための秘密計算システム、秘密計算方法、計算装置に関する。
【背景技術】
【０００２】
ある演算に対して暗号化された入力データを復元することなく演算結果を得る方法（以降、当該方法を秘密計算方法と呼ぶ）として、例えば非特許文献１に記載された方法がある。当該方法は、暗号化手段として秘密分散法を用いる。すなわち、複数の装置がそれぞれ異なる分散データ（断片）を所持し、当該断片を一定数以上用いることでデータの復元を可能とし、さらにデータを復元することなく当該データを入力とした演算結果の断片を複数の装置が得ることも可能とする。当該方法を用いて実現可能な演算種別は算術演算（加減乗算）や論理（回路）演算である。また、当該方法は、ｎ台の装置がそれぞれ異なる断片を所持するとき、ｎ≧２ｔ−１を満たすｔ以上の数の断片を用いることでデータの復元を可能とする。
【０００３】
一方、当該方法は、整数値の断片から当該整数値を復元することなく論理演算を行い、演算結果の断片を得る方法が自明でなかったが、非特許文献２ではその解決法が提案されている。また、秘密計算方法を論理演算に用いて実行する方法として、例えば非特許文献３の方法が知られている。非特許文献３の方法は、論理回路の入出力ビットを乱数に置き換える操作により、置き換え後の演算の実行者は入出力の値を知ることなく演算結果に対応する乱数を得ることを可能とする。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)”, Proc. of STOC 1988, pp.1-10.
【非特許文献２】Takashi Nishide and Kazuo Ohta, “Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol”, Proc. of Public Key Cryptography 2007, pp.343-360.
【非特許文献３】Andrew Chi-Chih Yao, “How to Generate and Exchange Secrets (Extended Abstract)”, Proc. of FOCS 1986, pp.162-167.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、秘密計算方法を用いた演算は、通常の演算よりも効率が悪く、複雑な演算になると実用的ではない処理時間になることがある。そこで、本発明は、計算効率と通信効率が従来方法よりも優れた秘密計算方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の秘密計算システムは、３つの計算装置から構成され、数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、計算装置Ｘとして機能する計算装置が第１断片を記録し、計算装置Ｙとして機能する計算装置が第２断片を記録し、計算装置Ｚとして機能する計算装置が第３断片を記録する。
【０００７】
本発明の秘密計算システムの秘密加算手段は、計算装置Ｘが、Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算部を有し、計算装置Ｙが、Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算部を有し、計算装置Ｚが、Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算部を有す。
【０００８】
本発明の秘密計算システムの秘密減算手段は、計算装置Ｘが、Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１−ｂ_１
のように求める第１減算部を有し、計算装置Ｙが、Ａ−Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１−ｂ_２１，ａ_２２−ｂ_２２）
のように求める第２減算部を有し、計算装置Ｚが、Ａ−Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１−ｂ_２１，ａ_２３−ｂ_２３）
のように求める第３減算部を有す。
【０００９】
本発明の秘密計算システムの秘密定数倍手段は、計算装置Ｘが、Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝Ｂａ_１
のように求める第１定数倍計算部を有し、計算装置Ｙが、Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（Ｂａ_２１，Ｂａ_２２）
のように求める第２定数倍計算部を有し、計算装置Ｚが、Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（Ｂａ_２１，Ｂａ_２３）
のように求める第３定数倍計算部を有す。
【００１０】
本発明の秘密計算システムの秘密乗算手段は、計算装置Ｘが、乗算乱数生成部と第１乗算部と第１乗算送信部を有し、計算装置Ｙが、第２乗算乱数受信部と第２乗算中間値計算部と第２乗算送信部と第２乗算中間値受信部と第２乗算部を有し、計算装置Ｚが、第３乗算乱数受信部と第３乗算中間値計算部と第３乗算送信部と第３乗算中間値受信部と第３乗算部を有す。乗算乱数生成部は、乱数ｒ_１，ｒ_２，ｒ_３，ｒ_４，ｒ_５を生成する。第１乗算部は、Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１、第２要素ｃ_２２、第３要素ｃ_２３を
ｃ_１＝ａ_１ｂ_１−ｒ_３−r_４
ｃ_２２＝ｒ_５
ｃ_２３＝ｃ_１−ｃ_２２
のように求める。第１乗算送信部は、計算装置Ｙに（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を、計算装置Ｚに（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する。第２乗算乱数受信部は、計算装置Ｘから（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を受信する。第２乗算中間値計算部は、数値ｙを
ｙ＝ａ_２１ｂ_２１＋ａ_２１ｒ_２＋ｒ_１ｂ_２１＋ｒ_３
のように求める。第２乗算送信部は、計算装置Ｚに数値ｙを送信する。第２乗算中間値受信部は、計算装置Ｚから数値ｚを受信する。第２乗算部は、Ａ×Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ｙ＋ｚ，ｃ_２２）
のように求める。第３乗算乱数受信部は、計算装置Ｘから（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を受信する。第３乗算中間値計算部は、数値ｚを
ｚ＝ａ_２１（ｂ_１−ｒ_２）＋（ａ_１−ｒ_１）ｂ_２１＋ｒ_４
のように求める。第３乗算送信部は、計算装置Ｙに数値ｚを送信する。第３乗算中間値受信部は、計算装置Ｙから数値ｙを受信する。第３乗算部は、Ａ×Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ｙ＋ｚ，ｃ_２３）
のように求める。
【００１１】
本発明の秘密計算システムの秘密否定手段では、計算装置Ｘが、１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝−ａ_１
のように求める第１否定部を有し、計算装置Ｙが、１−Ａの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（１−ａ_２１，−ａ_２２）
のように求める第２否定部を有し、計算装置Ｚが、１−Ａの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（１−ａ_２１，−ａ_２３）
のように求める第３否定部を有す。
【００１２】
本発明の秘密計算システムの秘匿処理手段は、自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配部とを備える。
【００１３】
本発明の秘密計算システムの復元手段は、計算装置Ｘが、第１断片送信部と第１断片受信部と第１復元部を有し、計算装置Ｙが、第２断片送信部と第２断片受信部と第２復元部
を有し、計算装置Ｚが、第３断片送信部と第３断片受信部と第３復元部を有す。第１断片送信部は、計算装置Ｙまたは計算装置Ｚに第１断片を送信する。第１断片受信部は、計算装置Ｙまたは計算装置Ｚから第１要素を受信する。第１復元部は、第１断片受信部が受信した第１要素と当該第１要素に対応する第１断片とを加算することで数値を復元する。第２断片送信部は、計算装置Ｘに第１要素を送信する、または計算装置Ｚに第２要素を送信する。第２断片受信部は、計算装置Ｘから第１断片を受信する、または計算装置Ｚから第３要素を受信する。第２復元部は、第２断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または第２断片受信部が受信した第３要素と当該第３要素に対応する第１要素と第２要素とを加算することで数値を復元する。第３断片送信部は、計算装置Ｘに第１要素を送信する、または計算装置Ｙに第３要素を送信する。第３断片受信部は、計算装置Ｘから第１断片を受信する、または計算装置Ｙから第２要素を受信する。第３復元部は、第３断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または第３断片受信部が受信した第２要素と当該第２要素に対応する第１要素と第３要素とを加算することで数値を復元する。
【発明の効果】
【００１４】
本発明の秘密計算システムでは、断片を分散して記録した状態からの加減算や定数倍演算は、非特許文献１と同様に、各計算装置が単独で計算できる。乗算や論理回路演算については、非特許文献２と同様に各計算装置の協調計算が必要となる。更に本発明の秘密計算システムは、２進数変換や整数変換についても他の計算の単純な拡張として実現できる。これにより、算術演算および論理回路演算の組合せ計算が可能となる。
【図面の簡単な説明】
【００１５】
【図１】実施例１の秘密計算システムの機能構成例を示す図。
【図２】実施例１の秘密加算過程の処理フローを示す図。
【図３】実施例１の秘密減算過程の処理フローを示す図。
【図４】実施例１の秘密定数倍過程の処理フローを示す図。
【図５】実施例１の秘密乗算過程の処理フローを示す図。
【図６】実施例１の秘密否定過程の処理フローを示す図。
【図７】実施例１の秘密加算手段の構成を示す図。
【図８】実施例１の秘密減算手段の構成を示す図。
【図９】実施例１の秘密定数倍手段の構成を示す図。
【図１０】実施例１の秘密乗算手段の構成を示す図。
【図１１】実施例１の秘密否定手段の構成を示す図。
【図１２】実施例１の秘匿処理手段の構成例を示す図。
【図１３】実施例１の秘匿処理のフローを示す図。
【図１４】図１の秘密計算システムに秘匿手段を付加した秘密計算システムの機能構成例を示す図。
【図１５】図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第１の例を示す図。
【図１６】図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第２の例を示す図。
【図１７】実施例１の復元手段を計算装置に配置した構成例を示す図。
【図１８】実施例１の復元手段の処理フローを示す図。
【図１９】図１と図１２と図１７に示した計算装置１００_Ｘ，１００_Ｙ，１００_Ｚのいずれの計算装置としても機能できる計算装置１００_１（１００_２，１００_３）の機能構成例を示す図。
【図２０】入力と出力の不正を検出するための計算装置の機能構成例を示す図。
【図２１】実施例１の入力の不正を検出する処理フローを示す図。
【図２２】第１要素の不正を検出する処理フローを示す図。
【図２３】第１断片の不正を検出する処理フローを示す図。
【図２４】第２要素の不正を検出する処理フローを示す図。
【図２５】第３要素の不正を検出する処理フローを示す図。
【図２６】実施例１の出力の不正を検出する処理フローを示す図。
【図２７】実施例２の秘密計算システムの機能構成例を示す図。
【図２８】実施例２の秘密計算システムの処理フロー例を示す図。
【図２９】実施例３の秘密計算システムの機能構成例を示す図。
【図３０】実施例３の秘密計算システムの処理フロー例を示す図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１７】
図１に実施例１の秘密計算システムの機能構成例を示す。図２は秘密加算過程の処理フローを、図３は秘密減算過程の処理フローを、図４は秘密定数倍過程の処理フローを、図５は秘密乗算過程の処理フローを、図６は秘密否定過程の処理フローを示す図である。また、図１に示した機能構成の中で、図２〜図６に示した各処理フローを実行するために必要な構成のみを表示した図を、図７〜１１に示す。図７は秘密加算手段の構成を、図８は秘密減算手段の構成を、図９は秘密定数倍手段の構成を、図１０は秘密乗算手段の構成を、図１１は秘密否定手段の構成を示す図である。
【００１８】
＜基本的な算術演算のためのシステム構成＞
実施例１の秘密計算システムは、ネットワーク１０００で接続された３つの計算装置１００_Ｘ、１００_Ｙ、１００_Ｚで構成される。計算装置Ｘとして機能する計算装置１００_Ｘは、第１加算部１１０_１、第１減算部１２０_１、第１定数倍計算部１３０_１、乗算乱数生成部１４１_１、第１乗算部１４２_１、第１乗算送信部１４３_１、第１否定部１５０_１、第１記録部１９０_１を備える。計算装置Ｙとして機能する計算装置１００_Ｙは、第２加算部１１０_２、第２減算部１２０_２、第２定数倍計算部１３０_２、第２乗算乱数受信部１４４_２、第２乗算中間値計算部１４５_２、第２乗算送信部１４６_２、第２乗算中間値受信部１４７_２、第２乗算部１４８_２、第２否定部１５０_２、第２記録部１９０_２を備える。計算装置Ｚとして機能する計算装置１００_Ｚは、第３加算部１１０_３、第３減算部１２０_３、第３定数倍計算部１３０_３、第３乗算乱数受信部１４４_３、第３乗算中間値計算部１４５_３、第３乗算送信部１４６_３、第３乗算中間値受信部１４７_３、第３乗算部１４８_３、第３否定部１５０_３、第３記録部１９０_３を備える。なお、実際の秘密計算システムでは、そのシステムで実行する計算に対応した構成を、これらの中から選んで備えればよい。例えば、秘密加算のみを行うのであれば、計算装置１００_Ｘは、第１加算部１１０_１と第１記録部１９０_１を備え、計算装置１００_Ｙは、第２加算部１１０_２と第２記録部１９０_２を備え、計算装置１００_Ｚは、第３加算部１１０_３と第３記録部１９０_３を備えればよい。
【００１９】
各演算の入力である数値Ａと数値Ｂは、３つの断片に分けられ、３つの計算装置に分配された状態となっている。具体的には、数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を持つ。そして、計算装置１００_Ｘの第１記録部１９０_１が第１断片を記録し、計算装置１００_Ｙの第２記録部１９０_２が第２断片を記録し、計算装置１００_Ｚの第３記録部１９０_３が第３断片を記録する。
【００２０】
＜秘密加算手段（図２，７参照）＞
実施例１の秘密計算システムの秘密加算手段１０は、計算装置１００_Ｘが第１加算部１１０_１を有し、計算装置１００_Ｙが第２加算部１１０_２を有し、計算装置１００_Ｚが第３加算部１１０_３を有す。そして、秘密加算過程Ｓ１０は以下の処理で構成されている。第１加算部１１０_１が、Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める（Ｓ１１０_１）。第２加算部１１０_２が、Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める（Ｓ１１０_２）。第３加算部１１０_３が、Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める（Ｓ１１０_３）。
【００２１】
このような処理を行えば、加算の結果Ｃの第１断片ｃ_１を第１記録部１９０_１が記録し、第２断片ｃ_２を第２記録部１９０_２が記録し、第３断片ｃ_３を第３記録部１９０_３が記録した状態となる。また、互いのデータの授受がないため、いずれの計算装置も入力の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００２２】
＜秘密減算手段（図３，８参照）＞
実施例１の秘密計算システムの秘密減算手段２０は、計算装置１００_Ｘが第１減算部１２０_１を有し、計算装置１００_Ｙが第２減算部１２０_２を有し、計算装置１００_Ｚが第３減算部１２０_３を有す。そして、秘密減算過程Ｓ２０は以下の処理で構成されている。第１減算部１２０_１が、Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１−ｂ_１
のように求める（Ｓ１２０_１）。第２減算部１２０_２が、Ａ−Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１−ｂ_２１，ａ_２２−ｂ_２２）
のように求める（Ｓ１２０_２）。第３減算部１２０_３が、Ａ−Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１−ｂ_２１，ａ_２３−ｂ_２３）
のように求める（Ｓ１２０_３）。
【００２３】
このような処理を行えば、減算の結果Ｃの第１断片ｃ_１を第１記録部１９０_１が記録し、第２断片ｃ_２を第２記録部１９０_２が記録し、第３断片ｃ_３を第３記録部１９０_３が記録した状態となる。また、互いのデータの授受がないため、いずれの計算装置も入力の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００２４】
＜秘密定数倍手段（図４，９参照）＞
実施例１の秘密計算システムの秘密定数倍手段３０は、計算装置１００_Ｘが第１定数倍計算部１３０_１を有し、計算装置１００_Ｙが第２定数倍計算部１３０_２を有し、計算装置１００_Ｚが第３定数倍計算部１３０_３を有す。そして、秘密定数倍過程Ｓ３０は以下の処理で構成されている。第１定数倍計算部１３０_１が、Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝Ｂａ_１
のように求める（Ｓ１３０_１）。第２定数倍計算部１３０_２が、Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（Ｂａ_２１，Ｂａ_２２）
のように求める（Ｓ１３０_２）。第３定数倍計算部１３０_３が、Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（Ｂａ_２１，Ｂａ_２３）
のように求める（Ｓ１３０_３）。
【００２５】
このような処理を行えば、定数倍計算の結果Ｃの第１断片ｃ_１を第１記録部１９０_１が記録し、第２断片ｃ_２を第２記録部１９０_２が記録し、第３断片ｃ_３を第３記録部１９０_３が記録した状態となる。また、互いのデータの授受がないため、いずれの計算装置も入力の数値Ａも計算結果である数値Ｃも、単独では知ることができない。
【００２６】
＜秘密乗算手段（図５，１０参照）＞
実施例１の秘密計算システムの秘密乗算手段４０は、計算装置１００_Ｘが、乗算乱数生成部１４１_１、第１乗算部１４２_１、第１乗算送信部１４３_１を有し、計算装置１００_Ｙが、第２乗算乱数受信部１４４_２、第２乗算中間値計算部１４５_２、第２乗算送信部１４６_２、第２乗算中間値受信部１４７_２、第２乗算部１４８_２を有し、計算装置１００_Ｚが、第３乗算乱数受信部１４４_３、第３乗算中間値計算部１４５_３、第３乗算送信部１４６_３、第３乗算中間値受信部１４７_３、第３乗算部１４８_３を有す。そして、秘密乗算過程Ｓ４０は以下の処理で構成されている。
【００２７】
乗算乱数生成部１４１_１は、乱数ｒ_１，ｒ_２，ｒ_３，ｒ_４，ｒ_５を生成する（Ｓ１４１_１）。第１乗算部１４２_１は、Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１、第２要素ｃ_２２、第３要素ｃ_２３を
ｃ_１＝ａ_１ｂ_１−ｒ_３−r_４
ｃ_２２＝ｒ_５
ｃ_２３＝ｃ_１−ｃ_２２
のように求める（Ｓ１４２_１）。第１乗算送信部１４３_１は、計算装置１００_Ｙに（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を、計算装置１００_Ｚに（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する（Ｓ１４３_１）。
【００２８】
第２乗算乱数受信部１４４_２は、計算装置１００_Ｘから（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を受信する（Ｓ１４４_２）。第３乗算乱数受信部１４４_３は、計算装置１００_Ｘから（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を受信する（Ｓ１４４_３）。第２乗算中間値計算部１４５_２は、数値ｙを
ｙ＝ａ_２１ｂ_２１＋ａ_２１ｒ_２＋ｒ_１ｂ_２１＋ｒ_３
のように求める（Ｓ１４５_２）。第３乗算中間値計算部１４５_３は、数値ｚを
ｚ＝ａ_２１（ｂ_１−ｒ_２）＋（ａ_１−ｒ_１）ｂ_２１＋ｒ_４
のように求める（Ｓ１４５_３）。第２乗算送信部１４６_２は、計算装置１００_Ｚに数値ｙを送信する（Ｓ１４６_２）。第３乗算送信部１４６_３は、計算装置１００_Ｙに数値ｚを送信する（Ｓ１４６_３）。第２乗算中間値受信部１４７_２は、計算装置１００_Ｚから数値ｚを受信する（Ｓ１４７_２）。第３乗算中間値受信部１４７_３は、計算装置１００_Ｙから数値ｙを受信する（Ｓ１４７_３）。第２乗算部１４８_２は、Ａ×Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ｙ＋ｚ，ｃ_２２）
のように求める（Ｓ１４８_２）。第３乗算部１４８_３は、Ａ×Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ｙ＋ｚ，ｃ_２３）
のように求める（Ｓ１４８_３）。
【００２９】
このような処理を行えば、乗算の結果Ｃの第１断片ｃ_１を第１記録部１９０_１が記録し、第２断片ｃ_２を第２記録部１９０_２が記録し、第３断片ｃ_３を第３記録部１９０_３が記録した状態となる。また、計算装置１００_Ｘは、他の計算装置からデータを受け取らないので、入力の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。計算装置１００_Ｙは、ｒ_１，ｒ_２，ｒ_３，ｃ_２２，ｚを受信するが、これらの数値は数値Ａ，Ｂとは独立の乱数とみなせるため、数値Ａ，Ｂ，Ｃを単独で復元することはできない。計算装置１００_Ｚは、ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３，ｙを受信するが、これらの数値は数値Ａ，Ｂとは独立の乱数とみなせるため、数値Ａ，Ｂ，Ｃを単独で復元することはできない。
【００３０】
＜秘密否定手段（図６，１１参照）＞
これまでの説明は、算術演算についてであったが、論理演算も可能である。まず、否定を行う手段について説明する。実施例１の秘密計算システムの秘密否定手段５０は、計算装置１００_Ｘが第１否定部１５０_１を有し、計算装置１００_Ｙが第２否定部１５０_２を有し、計算装置１００_Ｚが第３否定部１５０_３を有す。そして、秘密否定過程Ｓ５０は以下の処理で構成されている。第１否定部１５０_１が、１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝−ａ_１
のように求める（Ｓ１５０_１）。第２否定部１５０_２が、１−Ａの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（１−ａ_２１，−ａ_２２）
のように求める（Ｓ１５０_２）。第３否定部１５０_３が、１−Ａの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（１−ａ_２１，−ａ_２３）
のように求める（Ｓ１５０_３）。
【００３１】
このような処理を行えば、否定の結果Ｃの第１断片ｃ_１を第１記録部１９０_１が記録し、第２断片ｃ_２を第２記録部１９０_２が記録し、第３断片ｃ_３を第３記録部１９０_３が記録した状態となる。また、互いのデータの授受がないため、いずれの計算装置も数値Ａも計算結果である数値Ｃも、単独では知ることができない。
【００３２】
＜秘密論理積手段＞
次に、論理積を行う方法について説明する。ＡとＢとの論理積（Ｃ＝Ａ∧Ｂ）は、乗算と同じなので、秘密乗算過程Ｓ４０を実行すればよい。
【００３３】
＜秘密論理和手段＞
ＡとＢの論理和（Ｃ＝Ａ∨Ｂ）は、
Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ
の演算を行えばよい。したがって、例えば、以下の処理を行えばよい。
（１）秘密加算過程Ｓ１０によってＤ_１＝Ａ＋Ｂを求める。
（２）秘密乗算過程Ｓ４０によってＤ_２＝ＡＢを求める。
（３）秘密減算過程Ｓ２０によってＣ＝Ｄ_１−Ｄ_２を求める。
【００３４】
このような処理を行えば、論理和の結果Ｃの第１断片ｃ_１を計算装置１００_Ｘの第１記録部１９０_１が記録し、第２断片ｃ_２を計算装置１００_Ｙの第２記録部１９０_２が記録し、第３断片ｃ_３を計算装置１００_Ｚの第３記録部１９０_３が記録した状態となる。また、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００３５】
＜秘密排他的論理和手段＞
ＡとＢの排他的論理和は、
【００３６】
【数１】

【００３７】
の演算を行えばよい。したがって、例えば、以下の処理を行えばよい。
（１）秘密加算過程Ｓ１０によってＤ_１＝Ａ＋Ｂを求める。
（２）秘密乗算過程Ｓ４０によってＤ_２＝ＡＢを求める。
（３）秘密定数倍過程Ｓ３０によって、Ｄ_３＝２Ｄ_２
（４）秘密減算過程Ｓ２０によってＣ＝Ｄ_１−Ｄ_３を求める。
【００３８】
このような処理を行えば、排他的論理和の結果Ｃの第１断片ｃ_１を計算装置１００_Ｘの第１記録部１９０_１が記録し、第２断片ｃ_２を計算装置１００_Ｙの第２記録部１９０_２が記録し、第３断片ｃ_３を計算装置１００_Ｚの第３記録部１９０_３が記録した状態となる。また、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００３９】
＜秘匿処理手段＞
次に、いずれかの計算装置が保有している数値の３つの断片を生成し、断片を３つの計算装置で共有する処理について説明する。図１２は実施例１の秘匿処理手段の構成例を示す図、図１３は秘匿処理のフローを示す図である。図１３（Ａ）は計算装置１００_Ｘとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｘ過程）を示す図であり、図１３（Ｂ）は計算装置１００_Ｙとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｙ過程）を示す図であり、図１３（Ｃ）は計算装置１００_Ｚとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｚ過程）を示す図である。
【００４０】
計算装置１００_Ｘとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００_Ｘは、断片生成部１６１_１と断片分配部１６２_１を備える。計算装置１００_Ｙとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００_Ｙは、断片生成部１６１_２と断片分配部１６２_２を備える。計算装置１００_Ｚとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００_Ｚは、断片生成部１６１_３と断片分配部１６２_３を備える。
【００４１】
数値Ｓをいずれかの計算装置が保有しているとする。断片生成部１６１_１、１６１_２、１６１_３は、自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める（Ｓ１６１_１、Ｓ１６１_２、Ｓ１６１_３）。断片分配部１６２_１、１６２_２、１６２_３は、計算装置Ｘとして機能する計算装置１００_Ｘが第１断片ｓ_１を、計算装置Ｙとして機能する計算装置１００_Ｙが第２断片ｓ_２を、計算装置Ｚとして機能する計算装置１００_Ｚが第３断片ｓ_３を記録した状態にする（Ｓ１６２_１、Ｓ１６２_２、Ｓ１６２_３）。なお、秘匿処理手段は、秘匿処理したい数値を保有する計算装置に備えればよく、秘匿処理したい数値を保有しない計算装置には具備しなくてもよい。
【００４２】
このような処理を行えば、演算の対象となる数値の第１断片ｓ_１を第１記録部１９０_１が記録し、第２断片ｓ_２を第２記録部１９０_２が記録し、第３断片ｓ_３を第３記録部１９０_３が記録した状態となる。
【００４３】
＜秘密２進変換手段＞
第１の秘密２進変換手段
図１４は、図１の秘密計算システムに秘匿手段を付加した秘密計算システムの機能構成例である。図１５は、図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第１の例を示す図である。なお、図１５のフローでは、計算装置１００_Ｘが保有する数値（第１断片ａ_１）と計算装置１００_Ｙが保有する数値（第１要素ａ_２１）を秘匿処理することで、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を秘匿処理する例を示している。この例の場合、断片生成部１６１_３と断片分配部１６２_３は不要である。なお、数値Ａと断片ａ_１と第１要素ａ_２１は高々Ｎビットであるとし、Ａ［ｎ］は数値Ａの下位ｎ番目のビットを、ａ_１［ｎ］は第１断片ａ_１の下位ｎ番目のビットを、ａ_２１［ｎ］は第１要素ａ_２１の下位ｎ番目のビットをあらわす。
【００４４】
次に、数値Ａを２進表現した時の各ビットＡ［１］，…，Ａ［Ｎ］の断片を３つの計算装置で分散して記録するフローを説明する。
（１−１）計算装置１００_Ｘの秘匿処理Ｘ手段６０_１によって、第１断片ａ_１［１］，…，ａ_１［Ｎ］を秘匿処理する（Ｓ３１１）。
（１−２）計算装置１００_Ｙの秘匿処理Ｙ手段６０_２によって、第１要素ａ_２１［１］，…，ａ_２１［Ｎ］を秘匿処理する（Ｓ３１２）。
（２−１）秘密計算システムは、ｃ_１＝０、ｎ＝１のように初期設定を行う（Ｓ３２１）。具体的には、いずれかの計算装置１００でＳ３２１を行えばよい。
（２−２）秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
ｄ_ｎ＝ａ_１［ｎ］＋ａ_２１［ｎ］−２ａ_１［ｎ］ａ_２１［ｎ］
を行う（Ｓ３３０）。これは、第１断片ａ_１の下位ｎ番目ａ_１［ｎ］と第１要素ａ_２１の下位ｎ番目ａ_２１［ｎ］の排他的論理和に相当する計算である。排他的論理和の処理の詳細は、上述の秘密排他的論理和手段に示されている。
（２−３）秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
Ａ［ｎ］＝ｄ_ｎ＋ｃ_ｎ−２ｄ_ｎｃ_ｎ
を行う（Ｓ３４０）。これは、ｄ_ｎとｃ_ｎの排他的論理和に相当する計算である。ステップＳ３３０とＳ３４０の処理によって、
【００４５】
【数２】

【００４６】
の計算結果の断片が３つの計算装置で分散されて記録された状態となる。
（２−４）次に、ステップＳ３２１を行った計算装置１００が、ｎ＝Ｎかを確認する（Ｓ３２２）。ステップＳ３２２がＹｅｓの場合には処理を終了し、Ｎｏの場合には次の処理に進む。
（２−５）ステップＳ３２２がＮｏの場合には、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密減算過程Ｓ２０によって、
ｃ_ｎ＋１＝ａ_１［ｎ］ａ_２１［ｎ］＋ｄ_ｎｃ_ｎ−ａ_１［ｎ］ａ_２１［ｎ］ｄ_ｎｃ_ｎ
を行う（Ｓ３５０）。これは、ａ_１［ｎ］ａ_２１［ｎ］とｄ_ｎｃ_ｎとの論理和に相当する計算である。
（２−６）ステップＳ３２１を行った計算装置１００が、ｎにｎ＋１を代入し（Ｓ３２３）、ステップＳ３３０に戻る。
【００４７】
このような処理を行えば、数値Ａの下位ｎ番目のビットＡ［ｎ］の第１断片ａ_１［ｎ］を計算装置１００_Ｘの第１記録部１９０_１が記録し、第２断片ａ_２［ｎ］を計算装置１００_Ｙの第２記録部１９０_２が記録し、第３断片ａ_３［ｎ］を計算装置１００_Ｚの第３記録部１９０_３が記録した状態となる。また、秘匿処理Ｘ過程Ｓ６０_１と秘匿処理Ｙ過程Ｓ６０_２は、第１断片ａ_１［１］，…，ａ_１［Ｎ］と第１要素ａ_２１［１］，…，ａ_１［Ｎ］を秘匿処理している。この処理では、いずれの計算装置も、数値Ａを単独では知ることができない。秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａも、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、単独では知ることができない。
【００４８】
第２の秘密２進変換手段
図１６は、図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第２の例を示す図である。なお、図１６のフローでも、計算装置１００_Ｘが保有する数値（第１断片ａ_１）と計算装置１００_Ｙが保有する数値（第１要素ａ_２１）を秘匿処理することで、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を秘匿処理する例を示している。この例の場合、断片生成部１６１_３と断片分配部１６２_３は不要である。なお、数値Ａと断片ａ_１と第１要素ａ_２１は高々Ｎビットであるとし、Ａ［ｎ］は数値Ａの下位ｎ番目のビットを、ａ_１［ｎ］は第１断片ａ_１の下位ｎ番目のビットを、ａ_２１［ｎ］は第１要素ａ_２１の下位ｎ番目のビットをあらわす。
【００４９】
次に、数値Ａを２進表現した時の各ビットＡ［１］，…，Ａ［Ｎ］の断片を３つの計算装置で分散して記録するフローを説明する。
（１−１）計算装置１００_Ｘの秘匿処理Ｘ手段６０_１によって、第１断片ａ_１［１］，…，ａ_１［Ｎ］を秘匿処理する（Ｓ３１１）。
（１−２）計算装置１００_Ｙの秘匿処理Ｙ手段６０_２によって、第１要素ａ_２１［１］，…，ａ_２１［Ｎ］を秘匿処理する（Ｓ３１２）。
（２−１）秘密計算システムは、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
【００５０】
【数３】

【００５１】
を行う（Ｓ３２４）。この処理によって、各計算装置１００は、Ａ［１］の断片を分散して記録した状態となる。
（３−１）秘密計算システムは、ｎ＝２のように初期設定を行う（Ｓ３２５）。具体的には、いずれかの計算装置１００でＳ３２５を行えばよい。
（３−２）秘密計算システムは、秘密定数倍過程Ｓ３０、秘密加算過程Ｓ１０、秘密減算過程Ｓ２０によって、
【００５２】
【数４】

【００５３】
を行う（Ｓ３３１）。この処理によって、各計算装置１００は、Ｂ^（ｎ）の断片ｂ_１^（ｎ），ｂ_２^（ｎ），ｂ_３^（ｎ）を分散して記録した状態となる。
（３−３）計算装置１００_Ｘの秘匿処理Ｘ手段６０_１によって、Ｂ^（ｎ）の第１断片ｂ_１^（ｎ）を秘匿処理する。また、計算装置１００_Ｙの秘匿処理Ｙ手段６０_２によって、Ｂ^（ｎ）の第１要素ｂ_２１^（ｎ）を秘匿処理する（Ｓ３３２）。
（３−４）秘密計算システムは、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
【００５４】
【数５】

【００５５】
を行い、Ｄ^（ｎ）の断片ｄ_１^（ｎ），ｄ_２^（ｎ），ｄ_３^（ｎ）を分散して記録した状態にする（Ｓ３３３）。
（４−１）各計算装置１００は、それぞれｃ_１^（ｎ）＝０、ｉ＝１のように初期設定を行う（Ｓ３４１）。
（４−２）計算装置Ｘとして機能する計算装置１００_Ｘは、
【００５６】
【数６】

【００５７】
を計算する。計算装置Ｙとして機能する計算装置１００_Ｙと、計算装置Ｚとして機能する計算装置１００_Ｚは、
【００５８】
【数７】

【００５９】
を計算する（Ｓ３４２）。
（４−３）各計算装置１００は、それぞれ
ｃ_ｉ＋１^（ｎ）＝ｃ_ｉ^（ｎ）ｂ_１^（ｎ）［ｉ］∨ｃ_ｉ^（ｎ）ｂ_２１^（ｎ）［ｉ］∨ｂ_１^（ｎ）［ｉ］ｂ_２１^（ｎ）［ｉ］
を計算する（Ｓ３４３）。
（４−４）各計算装置１００は、それぞれｉ＝ｎ−１かを確認する（Ｓ３４４）。各計算装置１００は、ステップＳ３４４がＮｏの場合には、ｉにｉ＋１を代入し（Ｓ３４５）、ステップＳ３４２に戻る。ステップＳ３４４がＹｅｓの場合には、ステップＳ３５１に進む。
（５−１）秘密計算システムは、ｃ_ｎ^（ｎ）＝０ならば各計算装置が分散して記録しているＤ^（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とする。また、ｃ_ｎ^（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ^（ｎ）の否定を秘密否定過程Ｓ５０で計算し、Ｄ^（ｎ）の否定の断片を、自己が記録するＡ［ｎ］の断片とする（Ｓ３５１）。
（５−２）秘密計算システムは、ｎ＝Ｎかを確認する（Ｓ３２６）。秘密計算システムは、ステップＳ３２６がＮｏの場合には、ｎにｎ＋１を代入し（Ｓ３２７）、ステップＳ３３１に戻る。ステップＳ３２６がＹｅｓの場合には、処理を終了する。
【００６０】
なお、ステップＳ３４３で計算されるｃ_ｉ＋１^（ｎ）は、Ｂ^（ｎ）＝ｂ_１^（ｎ）＋ｂ_２１^（ｎ）の加算回路における下位ｉ番目のビットの桁上げ（ｃａｒｒｙ）である。Ｂ^（ｎ）は、その取り方から、
【００６１】
【数８】

【００６２】
となり、Ｂ^（ｎ）の最下位ビットから下位ｎ−１ビットまでは０となる。したがって、１≦ｉ≦ｎ−１では
【００６３】
【数９】

【００６４】
となるので、ステップＳ３４２の式が成り立つことが分かる。また、ステップＳ３５１の計算結果は明らかにＢ^（ｎ）［ｎ］の断片となっているため、Ａ［ｎ］＝Ｂ^（ｎ）［ｎ］なので、Ａ［ｎ］の断片でもある。
【００６５】
このような処理を行えば、数値Ａの下位ｎ番目のビットＡ［ｎ］の第１断片ａ_１［ｎ］を計算装置１００_Ｘの第１記録部１９０_１が記録し、第２断片ａ_２［ｎ］を計算装置１００_Ｙの第２記録部１９０_２が記録し、第３断片ａ_３［ｎ］を計算装置１００_Ｚの第３記録部１９０_３が記録した状態となる。また、秘匿処理Ｘ過程Ｓ６０_１と秘匿処理Ｙ過程Ｓ６０_２は、第１断片ａ_１［１］，…，ａ_１［Ｎ］と第１要素ａ_２１［１］，…，ａ_１［Ｎ］を秘匿処理している。この処理では、いずれの計算装置も、数値Ａを単独では知ることができない。秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａも、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、単独では知ることができない。
【００６６】
さらに、第１の秘密２進変換手段では、秘密乗算過程Ｓ４０をａ_１［ｎ］ａ_２１［ｎ］、ｄ_ｎｃ_ｎ、ａ_１［ｎ］ａ_２１［ｎ］ｄ_ｎｃ_ｎの３回実行し、これをｎ＝１からＮまでＮ回繰り返す必要がある。ただし、ｃ_１＝０であり、ｎ＝Ｎのときはａ_１［ｎ］ａ_２１［ｎ］ｄ_ｎｃ_ｎの計算は不要なため、合計で３Ｎ−３回の秘密乗算過程Ｓ４０を実行する。一方、第２の秘密２進変換手段では、ａ_１［ｎ］ａ_２１［ｎ］および、ｎ＝２からＮまでのｂ_１^（ｎ）［ｎ］ｂ_２１^（ｎ）［ｎ］の合計Ｎ回の秘密乗算過程Ｓ４０の実行で済む。したがって、計算効率が高くなると共に、計算装置間の通信量も低減できる。
【００６７】
＜秘密整数変換手段＞
ここでは、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］の断片が３つの計算装置で分散して記録された状態から、整数表現の数値Ａの断片Ａ_１，Ａ_２，Ａ_３が３つの計算装置に分散して記録された状態にするための手段について説明する。整数表現された数値Ａは、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を用いて
【００６８】
【数１０】

【００６９】
のように求めることができる。したがって、秘密定数倍過程Ｓ３０の処理と秘密加算過程Ｓ１０の処理を繰り返すことで、数値Ａの第１断片Ａ［ｎ］を計算装置１００_Ｘの第１記録部１９０_１が記録し、第２断片Ａ_２を計算装置１００_Ｙの第２記録部１９０_２が記録し、第３断片Ａ_３を計算装置１００_Ｚの第３記録部１９０_３が記録した状態となる。
【００７０】
また、秘密定数倍過程Ｓ３０、秘密加算過程Ｓ１０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、整数表現ざれた数値Ａも、単独では知ることができない。
【００７１】
実施例１の秘密計算装置によれば、上述の秘密２進変換手段によって２進表現された数値に対して、上述の論理演算（秘密否定手段、秘密論理積手段、秘密論理和手段、秘密排他的論理和手段の処理）を行い、その結果を整数表現された数値に戻すことも可能である。しかも、これらの処理の途中の数値も、処理の結果の数値も、いずれの計算装置も単独では知ることができない。
【００７２】
＜復元手段＞
分散して記録された状態の断片から数値を復元する手段について説明する。図１７に実施例１の復元手段を計算装置に配置した構成例を示す。また、図１８に実施例１の復元手段の処理フローを示す。図１８（Ａ）の実線は、計算装置Ｘとして機能する計算装置１００_Ｘが、計算装置Ｙとして機能する計算装置１００_Ｙに第１断片を送り、計算装置１００_Ｙが数値を復元する処理フロー（復元ＸＹ過程Ｓ７０_１２）を示している。図１８（Ａ）の点線は、計算装置１００_Ｘが、計算装置Ｚとして機能する計算装置１００_Ｚに第１断片を送り、計算装置１００_Ｚが数値を復元する処理フロー（復元ＸＺ過程Ｓ７０_１３）を示している。図１８（Ｂ）の実線は、計算装置１００_Ｙが計算装置１００_Ｘに第２断片を送り、計算装置１００_Ｘが数値を復元する処理フロー（復元ＹＸ過程Ｓ７０_２１）を示している。図１８（Ｂ）の点線は、計算装置１００_Ｙが計算装置１００_Ｚに第２断片を送り、計算装置１００_Ｚが数値を復元する処理フロー（復元ＹＺ過程Ｓ７０_２３）を示している。図１８（Ｃ）の実線は、計算装置１００_Ｚが計算装置１００_Ｘに第３断片を送り、計算装置１００_Ｘが数値を復元する処理フロー（復元ＺＸ過程Ｓ７０_３１）を示している。図１８（Ｃ）の点線は、計算装置１００_Ｚが計算装置１００_Ｙに第３断片を送り、計算装置１００_Ｙが数値を復元する処理フロー（復元ＺＹ過程Ｓ７０_３２）を示している。秘密計算システムが、上記の復元処理のすべてを実行できるようにするためには、計算装置１００_Ｘが、第１断片送信部１７１_１、第１断片受信部１７２_１、第１復元部１７３_１を有し、計算装置１００_Ｙが、第２断片送信部１７１_２、第２断片受信部１７２_２、第２復元部１７３_２を有し、計算装置１００_Ｚが、第３断片送信部１７１_３、第３断片受信部１７２_３、第３復元部１７３_３を有する必要がある。なお、システムの設計上必要のない構成部は適宜省略してもよい。
【００７３】
次に、数値Ａの第１断片，第２断片，第３断片をａ_１，ａ_２，ａ_３とし、第１要素，第２要素，第３要素をａ_２１，ａ_２２，ａ_２３として、復元の処理フローについて説明する。なお、これまでの説明で何度も説明しているが、実施例１の秘密計算システムでは、分散して記録された断片は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
Ａ＝ａ_２１＋ａ_２２＋ａ_２３
の関係を有していることに注意されたい。
【００７４】
復元ＸＹ過程Ｓ７０_１２（図１８（Ａ）実線）
第１断片送信部１７１_１は、計算装置１００_Ｙに第１断片ａ_１を送信する（Ｓ１７１_１２）。第２断片受信部１７２_２は、計算装置１００_Ｘから第１断片ａ_１を受信する（Ｓ１７２_１２）。第２復元部１７３_２は、次式のように第２断片受信部１７２_２が受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値Ａを復元する（Ｓ１７２_１３）。
ａ_１＋ａ_２１＝ａ_２２＋ａ_２３＋ａ_２１＝Ａ
【００７５】
復元ＸＺ過程Ｓ７０_１３（図１８（Ａ）点線）
第１断片送信部１７１_１は、計算装置１００_Ｚに第１断片ａ_１を送信する（Ｓ１７１_１２）。第３断片受信部１７２_３は、計算装置１００_Ｘから第１断片ａ_１を受信する（Ｓ１７２_１２）。第３復元部１７３_３は、次式のように第３断片受信部１７２_３が受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値を復元する（Ｓ１７３_１２）。
ａ_１＋ａ_２１＝ａ_２２＋ａ_２３＋ａ_２１＝Ａ
【００７６】
復元ＹＸ過程Ｓ７０_２１（図１８（Ｂ）実線）
第２断片送信部１７１_２は、計算装置１００_Ｘに第１要素ａ_２１を送信する（Ｓ１７１_２１）。第１断片受信部１７２_１は、計算装置１００_Ｙから第１要素ａ_２１を受信する（Ｓ１７２_２１）。第１復元部１７３_１は、次式のように第１断片受信部１７２_１が受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する（Ｓ１７３_２１）。
ａ_２１＋ａ_１＝ａ_２１＋ａ_２２＋ａ_２３＝Ａ
【００７７】
復元ＹＺ過程Ｓ７０_２３（図１８（Ｂ）点線）
第２断片送信部１７１_２は、計算装置１００_Ｚに第２要素ａ_２２を送信する（Ｓ１７１_２３）。第３断片受信部１７２_３は、計算装置１００_Ｙから第２要素ａ_２１を受信する（Ｓ１７２_２３）。第３復元部１７３_３は、次式のように第３断片受信部１７２_３が受信した第２要素ａ_２２と当該第２要素ａ_２２に対応する第１要素ａ_２１と第３要素ａ_２３とを加算することで数値を復元する（Ｓ１７３_２３）。
ａ_２２＋ａ_２１＋ａ_２３＝Ａ
【００７８】
復元ＺＸ過程Ｓ７０_３１（図１８（Ｃ）実線）
第３断片送信部１７１_３は、計算装置１００_Ｘに第１要素ａ_２１を送信する（Ｓ１７１_３１）。第１断片受信部１７２_１は、計算装置１００_Ｚから第１要素ａ_２１を受信する（Ｓ１７２_３１）。第１復元部１７３_１は、次式のように第１断片受信部１７２_１が受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する（Ｓ１７３_３１）。
ａ_２１＋ａ_１＝ａ_２１＋ａ_２２＋ａ_２３＝Ａ
【００７９】
復元ＺＹ過程Ｓ７０_３２（図１８（Ｃ）点線）
第３断片送信部１７１_３は、計算装置１００_Ｙに第３要素ａ_２３を送信する（Ｓ１７１_３２）。第２断片受信部１７２_２は、計算装置１００_Ｚから第３要素ａ_２３を受信する（Ｓ１７２_３２）。第２復元部１７３_２は、次式のように第２断片受信部１７２_２が受信した第３要素ａ_２３と当該第３要素ａ_２３に対応する第１要素ａ_２１と第２要素ａ_２２とを加算することで数値Ａを復元する（Ｓ１７３_３２）。
ａ_２３＋ａ_２１＋ａ_２２＝Ａ
【００８０】
上述のように、実施例１の数値を分散して記録する方法では、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３の３つを加算できれば、元の数値Ａを復元できる。そして、いずれか２つの断片の情報が分かれば、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３の和を求めることができる。したがって、上述の秘密加算手段、秘密減算手段、秘密定数倍手段、秘密乗算手段、もしくは秘密否定手段の計算結果である数値Ｃの断片は、いずれか２つの断片が分かれば、数値Ｃを復元できることが分かる。
【００８１】
＜基本処理部＞
図１９に、図１と図１２と図１７に示した計算装置１００_Ｘ，１００_Ｙ，１００_Ｚのいずれの計算装置としても機能できる計算装置１００_１（１００_２，１００_３）の機能構成例を示す。基本処理部１０１_１（１０１_２，１０１_３）は、図１と図１２と図１７に示した構成部をすべで備えている。このように１つの計算装置が、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置としても機能できるようにしてもよい。この場合は、記録しているデータが第１断片から第３断片のいずれの断片かによって、その計算装置が、計算装置Ｘとして機能するか、計算装置Ｙとして機能するか、計算装置Ｚとして機能するかが決まる。もしくは、どの計算装置として機能させるかによって、秘匿処理などで渡す断片を決めればよい。このように、データごとに計算装置が発揮する機能が異なるようにすることで、より自由度の高い秘密計算システムを構築できる。
【００８２】
＜不正検出＞
次に、１つの計算装置が、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置としても機能できるようにしたときの例として、入力された断片のデータが正しいかを確認する方法と、計算結果である断片のデータ（出力）が正しいかを確認する方法を示す。図２０は、入力と出力の不正を検出するための計算装置の機能構成例を示す図である。
【００８３】
計算装置２００_１は、基本処理部１０１_１の他に、入力の不正を検出するために、第１乱数ｒ_ｘｙ共有部２４１_１、第１Ｚ送信部２４２_１、第１乱数ｒ_ｘｚ共有部２３１_１、第１Ｙ送信部２３２_１、第１受信部２２３_１、第１断片確認部２２４_１、第１確認乱数生成部２５１_１、Ｙ要素送信部２１１_２、Ｙ要素受信部２１２_２、Ｙ要素確認部２１３_２、第２乱数ｒ_ｘｙ共有部２４１_２、第２Ｚ送信部２４２_２、第２乱数ｒ_ｙｚ共有部２２１_２、第２Ｘ送信部２２２_２、第２受信部２３３_２、第２断片確認部２３４_２、第２確認乱数生成部２５１_２、Ｚ要素送信部２１１_３、Ｚ要素受信部２１２_３、Ｚ要素確認部２１３_３、第３乱数ｒ_ｘｚ共有部２３１_３、第３Ｙ送信部２３２_３、第３乱数ｒ_ｙｚ共有部２２１_３、第３Ｘ送信部２２２_３、第３受信部２４３_３、第３断片確認部２４４_３、第３確認乱数生成部２５１_３、復元入力確認部２５４を備える。また、計算装置２００_１は、基本処理部１０１_１の他に、出力の不正を検出するために、第１確認乱数生成部２５１_１、第２確認乱数生成部２５１_２、第３確認乱数生成部２５１_３、復元出力確認部２５５を備える。したがって、入力の不正のみを検出すればよいのであれば、復元出力確認部２５５は不要であり、基本処理部１０１_１中では秘匿手段と復元手段を具備していればよい。また、出力の不正のみを検出すればよいのであれば、第１確認乱数生成部２５１_１、第２確認乱数生成部２５１_２、第３確認乱数生成部２５１_３、復元出力確認部２５５と、基本処理部１０１_１中の秘匿手段と復元手段と計算に必要な手段のみを備えればよい。なお、各構成部の詳細な処理については後述する。
【００８４】
このときの秘密計算システムは、図２０に示された計算装置２００_１，２００_２，２００_３の３つの計算装置で構成される。そして、同一の入力（数値Ａ）に対して３種類の断片を用意し、各計算装置が計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置として機能するかを変更して断片を分散して記録する。また、元の数値は同じだが断片は異なる３つの入力から、各計算装置が計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置として機能するかを変更して同一の計算を３回行い、計算結果である断片を分散して記録する。この説明では、ｊ（１以上３以下の整数）を計算が何回目かを示す値とし、ａ_１^（ｊ），ａ_２^（ｊ），ａ_３^（ｊ）を入力である数値Ａに対するｊ番目の第１断片，第２断片，第３断片、ａ_２１^（ｊ）をｊ番目の第１要素、ｃ_１^（ｊ），ｃ_２^（ｊ），ｃ_３^（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ_２１^（ｊ），ｃ_２２^（ｊ），ｃ_２３^（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置２００_Ｘ^（ｊ），計算装置２００_Ｙ^（ｊ），計算装置２００_Ｚ^（ｊ）をｊ番目の計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能する計算装置とする。なお、それぞれの回で数値の断片や計算装置の役割が異なるので、
（ａ_１^（１），ａ_２^（１），ａ_３^（１））、（ａ_１^（２），ａ_２^（２），ａ_３^（２））、（ａ_１^（３），ａ_２^（３），ａ_３^（３））は互いに異なり、
（ｃ_１^（１），ｃ_２^（１），ｃ_３^（１））、（ｃ_１^（２），ｃ_２^（２），ｃ_３^（２））、（ｃ_１^（３），ｃ_２^（３），ｃ_３^（３））は互いに異なり、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））は互いに異なる。
【００８５】
入力された断片のデータが正しいかを確認する方法
図２１に入力の不正を検出する処理フローを示す。また、図２２は第１要素の不正を検出する処理フローを、図２３は第１断片の不正を検出する処理フローを、図２４は第２要素の不正を検出する処理フローを、図２５は第３要素の不正を検出する処理フローを示す図である。いずれかの計算装置２００_１が、ｊ＝１とする（Ｓ２０１）。そして、第１要素不正検出過程Ｓ２１、第１断片不正検出過程Ｓ２２、第２要素不正検出過程Ｓ２３、第３要素不正検出過程Ｓ２４を実行する。
【００８６】
第１要素不正検出過程Ｓ２１（図２２参照）では、計算装置２００_Ｙ^（ｊ）が保有する第１要素ａ_２１ｙ^（ｊ）と計算装置２００_Ｚ^（ｊ）が保有する第１要素ａ_２１ｚ^（ｊ）とが等しいことを確認する。具体的には、計算装置２００_Ｙ^（ｊ）のＹ要素送信部２１１_２は、計算装置２００_Ｚ^（ｊ）に自己が保有する第１要素ａ_２１ｙ^（ｊ）を送信する（Ｓ２１１_２）。計算装置２００_Ｚ^（ｊ）のＺ要素受信部２１２_３は、計算装置２００_Ｙ^（ｊ）から第１要素ａ_２１ｙ^（ｊ）を受信する（Ｓ２１２_３）。計算装置２００_Ｚ^（ｊ）のＺ要素確認部２１３_３は、自己が保有する第１要素ａ_２１ｚ^（ｊ）と計算装置２００_Ｙ^（ｊ）から受信した第１要素ａ_２１ｙ^（ｊ）とが等しいことを確認する（Ｓ２１３_３）。計算装置２００_Ｚ^（ｊ）のＺ要素送信部２１１_３は、計算装置２００_Ｙ^（ｊ）に自己が保有する第１要素ａ_２１ｚ^（ｊ）を送信する（Ｓ２１１_３）。計算装置２００_Ｙ^（ｊ）のＹ要素受信部２１２_２は、計算装置２００_Ｚ^（ｊ）から第１要素ａ_２１ｚ^（ｊ）を受信する（Ｓ２１２_２）。計算装置２００_Ｙ^（ｊ）のＹ要素確認部２１３_２は、自己が保有する第１要素ａ_２１ｙ^（ｊ）と計算装置２００_Ｚ^（ｊ）から受信した第１要素ａ_２１ｚ^（ｊ）とが等しいことを確認する（Ｓ２１３_２）。ステップＳ２１２_３とＳ２１３_２とで等しいと確認できた場合には、計算装置２００_Ｙ^（ｊ）が保有する第１要素ａ_２１ｙ^（ｊ）と計算装置２００_Ｚ^（ｊ）が保有する第１要素ａ_２１ｚ^（ｊ）とが等しいと確認できる。一方、ステップＳ２１２_３とＳ２１３_２のいずれかで等しくないと判断された場合には、入力に不正があったと判断される。
【００８７】
第１断片不正検出過程Ｓ２２（図２３参照）では、第１断片ａ_１^（ｊ）が第２要素ａ_２２^（ｊ）と第３要素ａ_２３^（ｊ）の和であることを確認する。具体的には、計算装置２００_Ｙ^（ｊ）の第２乱数ｒ_ｙｚ共有部２２１_２と計算装置２００_Ｚ^（ｊ）の第３乱数ｒ_ｙｚ共有部２２１_３との間で乱数ｒ_ｙｚを共有する（２２１_２，２２１_３）。なお、乱数ｒ_ｙｚはどちらの計算装置が生成してもよい。計算装置２００_Ｙ^（ｊ）の第２Ｘ送信部２２２_２は、計算装置２００_Ｘ^（ｊ）にｕ_ｙ（＝ａ_２２^（ｊ）＋ｒ_ｙｚ）を送信する（Ｓ２２２_２）。計算装置２００_Ｚ^（ｊ）の第３Ｘ送信部２２２_３は、計算装置２００_Ｘ^（ｊ）にｕ_ｚ（＝ａ_２３^（ｊ）−ｒ_ｙｚ）を送信する（Ｓ２２２_３）。計算装置２００_Ｘ^（ｊ）の第１受信部２２３_１は、計算装置２００_Ｙ^（ｊ）からｕ_ｙを、計算装置２００_Ｚ^（ｊ）からｕ_ｚを受信する（Ｓ２２３_１）。計算装置２００_Ｘ^（ｊ）の第１断片確認部２２４_１は、ａ_１^（ｊ）＝ｕ_ｙ＋ｕ_ｚであることを確認する（Ｓ２２４_１）。ステップＳ２２４_１で等しいと確認できた場合には、第１断片ａ_１^（ｊ）が第２要素ａ_２２^（ｊ）と第３要素ａ_２３^（ｊ）の和であることが確認できる。一方、ステップＳ２２４_１で等しくないと判断された場合には、入力に不正があったと判断される。
【００８８】
第２要素不正検出過程Ｓ２３（図２４参照）では、第２要素ａ_２２^（ｊ）が第１断片ａ_１^（ｊ）と第３要素ａ_２３^（ｊ）の差であることを確認する。具体的には、計算装置２００_Ｘ^（ｊ）の第１乱数ｒ_ｘｚ共有部２３１_１と計算装置２００_Ｚ^（ｊ）の第３乱数ｒ_ｘｚ共有部２３１_３との間で、乱数ｒ_ｘｚを共有する（Ｓ２３１_１、Ｓ２３１_３）。なお、乱数ｒ_ｘｚはどちらの計算装置が生成してもよい。計算装置２００_Ｘ^（ｊ）の第１Ｙ送信部２３２_１は、計算装置２００_Ｙ^（ｊ）にｕ_ｘ（＝ａ_１^（ｊ）＋ｒ_ｘｚ）を送信する（Ｓ２３２_１）。計算装置２００_Ｚ^（ｊ）の第３Ｙ送信部２３２_３は、計算装置２００_Ｙ^（ｊ）にｕ_ｚ（＝ａ_２３^（ｊ）＋ｒ_ｘｚ）を送信する（Ｓ２３２_３）。計算装置２００_Ｙ^（ｊ）の第２受信部２３３_２は、計算装置２００_Ｘ^（ｊ）からｕ_ｘを、計算装置２００_Ｚ^（ｊ）からｕ_ｚを受信する（Ｓ２３３_２）。計算装置２００_Ｙ^（ｊ）の第２断片確認部２３４_２は、ａ_２２^（ｊ）＝ｕ_ｘ−ｕ_ｚであることを確認する（Ｓ２３４_２）。ステップＳ２３４_２で等しいと確認できた場合には、第２要素ａ_２２^（ｊ）が第１断片ａ_１^（ｊ）と第３要素ａ_２３^（ｊ）の差であることが確認できる。一方、ステップＳ２３４_２で等しくないと判断された場合には、入力に不正があったと判断される。
【００８９】
第３要素不正検出過程Ｓ２４（図２５参照）では、第３要素ａ_２３^（ｊ）が第１断片ａ_１^（ｊ）と第２要素ａ_２２^（ｊ）の差であることを確認する。具体的には、計算装置２００_Ｘ^（ｊ）の第１乱数ｒ_ｘｙ共有部２４１_１と計算装置２００_Ｙ^（ｊ）の第２乱数ｒ_ｘｙ共有部２４１_２との間で乱数ｒ_ｘｙを共有する（Ｓ２４１_１，Ｓ２４１_２）。なお、乱数ｒ_ｘｙはどちらの計算装置が生成してもよい。計算装置２００_Ｘ^（ｊ）の第１Ｚ送信部２４２_１は、計算装置２００_Ｚ^（ｊ）にｕ_ｘ（＝ａ_１^（ｊ）＋ｒ_ｘｙ）を送信する（Ｓ２４２_１）。計算装置２００_Ｙ^（ｊ）の第２Ｚ送信部２４２_２は、計算装置２００_Ｚ^（ｊ）にｕ_ｙ（＝ａ_２２^（ｊ）＋ｒ_ｘｙ）を送信する（Ｓ２４２_２）。計算装置２００_Ｚ^（ｊ）の第３受信部２４３_３は、計算装置２００_Ｘ^（ｊ）からｕ_ｘを、計算装置２００_Ｙ^（ｊ）からｕ_ｙを受信する（Ｓ２４３_３）。計算装置２００_Ｚ^（ｊ）の第３断片確認部２４４_３は、ａ_２３^（ｊ）＝ｕ_ｘ−ｕ_ｙであることを確認する（Ｓ２４４_３）。ステップＳ２４４_３で等しいと確認できた場合には、第３要素ａ_２３^（ｊ）が第１断片ａ_１^（ｊ）と第２要素ａ_２２^（ｊ）の差であることが確認できる。一方、ステップＳ２４４_３で等しくないと判断された場合には、入力に不正があったと判断される。
【００９０】
計算装置２００_Ｘ^（ｊ）の第１確認乱数生成部２５１_１は、乱数ｒ_ｘを生成する（Ｓ２５１_１）。計算装置２００_Ｘ^（ｊ）の秘匿処理手段６０_１は、第１断片ａ_１^（ｊ），乱数ｒ_ｘの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０_１）。
【００９１】
計算装置２００_Ｙ^（ｊ）の第２確認乱数生成部２５１_２は、乱数ｒ_ｙを生成する（Ｓ２５１_２）。計算装置２００_Ｙ^（ｊ）の秘匿処理手段６０_２は、第１要素ａ_２１^（ｊ），乱数ｒ_ｙの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０_２）。
【００９２】
計算装置２００_Ｚ^（ｊ）の第３確認乱数生成部２５１_３は、乱数ｒ_ｚを生成する（Ｓ２５１_３）。計算装置２００_Ｚ^（ｊ）の秘匿処理手段６０_３は、乱数ｒ_ｚの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０_３）。
【００９３】
秘密加算手段１０は、
ａ_１^（ｊ）＋ａ_２１^（ｊ）＋ｒ
ただし、ｒ＝ｒ_ｘ＋ｒ_ｙ＋ｒ_ｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする（Ｓ２１０）。いずれかの計算装置２００_１の復元手段７０は、他の計算装置２００_２または計算装置２００_３から必要な情報を受け取り、
ａ_１^（ｊ）＋ａ_２１^（ｊ）＋ｒ
を復元して記録しておく（Ｓ２７０）。この処理は、ｊの値を変更しながら３回繰り替えされるが、計算装置Ｘ，Ｙ，Ｚのどの計算装置として機能しているかに関わらず、同じ計算装置がおこなえばよい。なお、この復元を行う計算装置は、ステップＳ２０１を行った計算装置（ｊの値を管理している計算装置）とすればよい。そして、その計算装置が、計算装置Ｘ，Ｙ，Ｚのどの計算装置として機能しているかによって、適宜復元手段を選択すればよい。ステップＳ２０１を行った計算装置（ｊの値を管理している計算装置）は、ｊ＝３かを確認し（Ｓ２０２）、Ｎｏの場合にはｊにｊ＋１を代入し（Ｓ２０３）ステップＳ２１〜Ｓ２４に戻る。ステップＳ２０２がＹｅｓの場合には、３つの復元結果ａ_１^（１）＋ａ_２１^（１）＋ｒ，ａ_１^（２）＋ａ_２１^（２）＋ｒ，ａ_１^（３）＋ａ_２１^（３）＋ｒを取得できるいずれかの計算装置（つまり、Ｓ２７０を３回行った計算装置）が、復元入力確認部２５４で、３つの結果が等しいことを確認する（Ｓ２５４）。
【００９４】
計算結果である断片のデータが正しいかを確認する方法
図２６に出力の不正を検出する処理フローを示す。いずれかの計算装置２００_１が、ｊ＝１とする（Ｓ２８１）。次に、所定の計算を行う（Ｓ２８５）。所定の計算とは、この秘密計算システムを用いて行う計算と同じにすればよく、加算、乗算、論理演算などのいずれかでも、いくつかの組合せでもかまわない。
【００９５】
計算装置２００_Ｘ^（ｊ）の第１確認乱数生成部２５１_１は、乱数ｒ_ｘを生成する（Ｓ２５１_１）。計算装置２００_Ｘ^（ｊ）の秘匿処理手段６０_１は、第１断片ｃ_１^（ｊ），乱数ｒ_ｘの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６５_１）。
【００９６】
計算装置２００_Ｙ^（ｊ）の第２確認乱数生成部２５１_２は、乱数ｒ_ｙを生成する（Ｓ２５１_２）。計算装置２００_Ｙ^（ｊ）の秘匿処理手段６０_２は、第１要素ｃ_２１^（ｊ），乱数ｒ_ｙの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６５_２）。
【００９７】
計算装置２００_Ｚ^（ｊ）の第３確認乱数生成部２５１_３は、乱数ｒ_ｚを生成する（Ｓ２５１_３）。計算装置２００_Ｚ^（ｊ）の秘匿処理手段６０_３は、乱数ｒ_ｚの断片を３つの計算装置で分散して記録した状態にする（Ｓ２６５_３）。
【００９８】
秘密加算手段は
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
ただし、ｒ＝ｒ_ｘ＋ｒ_ｙ＋ｒ_ｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする（Ｓ２１５）。計算装置２００_Ｘ^（ｊ）と計算装置２００_Ｙ^（ｊ）の一方は、他方から必要な情報を受け取り、ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＹ^（ｊ）を復元して記録しておく（Ｓ２７１）。計算装置２００_Ｙ^（ｊ）と計算装置２００_Ｚ^（ｊ）の一方は、他方から必要な情報を受け取り、ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＹＺ^（ｊ）を復元して記録しておく（Ｓ２７２）。計算装置２００_Ｘ^（ｊ）と計算装置２００_Ｚ^（ｊ）の一方は、他方から必要な情報を受け取り、ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＺ^（ｊ）を復元して記録しておく（Ｓ２７３）。ステップＳ２８１を行った計算装置（ｊの値を管理している計算装置）は、ｊ＝３かを確認し（Ｓ２８２）、Ｎｏの場合にはｊにｊ＋１を代入し（Ｓ２８３）ステップＳ２８５に戻る。ステップＳ２８２がＹｅｓの場合には、９つの復元結果Ｃ_ＸＹ^（１），Ｃ_ＹＺ^（１），Ｃ_ＸＺ^（１），Ｃ_ＸＹ^（２），Ｃ_ＹＺ^（２），Ｃ_ＸＺ^（２），Ｃ_ＸＹ^（３），Ｃ_ＹＺ^（３），Ｃ_ＸＺ^（３）を取得できるいずれかの計算装置（１つの計算装置では不可能なので、他の計算装置から復元結果を受信できる計算装置）が、復元結果Ｃ_ＸＹ^（１），Ｃ_ＹＺ^（１），Ｃ_ＸＺ^（１），Ｃ_ＸＹ^（２），Ｃ_ＹＺ^（２），Ｃ_ＸＺ^（２），Ｃ_ＸＹ^（３），Ｃ_ＹＺ^（３），Ｃ_ＸＺ^（３）がすべて等しいことを確認する（Ｓ２５５）。なお、すべての計算装置が復元結果を出力し、外部の計算装置で確認してもよい。
【００９９】
出力の不正が確認できる理由
計算結果を改ざんする不正は、
Ａ．入力の分散データを不正値とする、
Ｂ．乗算または２進変換処理の秘匿処理の手続きで他の計算装置に不正値を送信する、
Ｃ．復元処理で不正値を開示する
の何れかに帰着されることに着目する。なお、図２１の処理において何れかの計算装置が手続きを偽った場合は、不正Ａの検出ができなくなるが、その場合は不正ＢまたはＣの問題に帰着される。
【０１００】
次に、不正Ｂは１／２^λ以下の確率を除き図２６の処理で不正検出されることを示す。ただし、λは適当な整数である。不正Ａは各計算装置が図２１の処理を正しく行えば防ぐことができる。不正Ｃは図２６の処理によって防ぐことができる。したがって以下では不正Ｂについて考える。２進変換処理の秘匿処理で他の計算装置に不正値を送信する場合は、各計算装置が図２１の処理を正しく行えば図２１の処理で検出され、そうでない場合は、次段以降の乗算または２進変換処理の秘匿処理で他の計算装置に不正値を送信することに帰着される。次段以降に乗算および２進変換処理の秘匿処理が無い場合は不正Ｃの問題に帰着される。
【０１０１】
次に、乗算の処理で他の計算装置に不正値を送信する場合を考える。各計算装置は乗算ｃ＝ａｂにおいて計算装置Ｘの処理を行う際、計算装置Ｙ，Ｚにそれぞれ（ｒ_１，ｒ_２，ｒ_３，ｃ_２２），（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する。ｒ_１，ｒ_２，ｒ_３，ｃ_２２は乱数だから、ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３をそれぞれａ^〜、ｂ^〜、ｃ_２３^〜に置き換えたとき、計算装置Ｚが得る乗算結果の分散データはｃ_３^〜＝（ｃ_２１^〜，ｃ_２３^〜）＝（ｙ＋ａ_２１ｂ^〜＋ａ^〜ｂ_２１＋ｒ_４，ｃ_２３^〜）となる。すなわち、（ｃ_２１−ｃ_２１^〜，ｃ_２３−ｃ_２３^〜）＝（ａ_２１（ｂ_１−ｒ_２−ｂ^〜）＋（ａ_１−ｒ_１−ａ^〜）ｂ_２１，ｃ_２３−ｃ_２３^〜）の差分が生じる。しかし計算装置Ｘはａ_２１，ｂ_２１，ｃ_２３を知らないため、この差分をもう２回の乗算ｃ＝ａｂの実行時の計算装置Ｚの分散データに付加することができず、図２６の処理で不正検出されない確率は高々１／２^λとなる。
【０１０２】
最後に、実施例１の基本処理部と不正検出について、情報理論的安全性に基づく既存方式との比較を行う。非特許文献１では算術演算および論理回路演算を独立に実行することができ、非特許文献２の２進変換処理によってそれらを組み合わせた計算が可能となる。算術演算および論理回路演算は既存方式も本発明の提案方式もともにＯ（λ）の計算量となる。乗算のときのみ、Ｏ（１）の通信回数とＯ（λ）の通信量を必要とするが、実施例１の方式は乗算の計算がより単純となる。また、非特許文献１では、不正検出のためにGeneralized Reed-Miller Code に基づくエラー訂正処理が行われている。しかし、４つ以上の計算装置が計算に関与する必要があり、本発明とは計算装置の構成が異なる。
【０１０３】
実施例１の秘密計算システムでは、断片を分散して記録した状態からの加減算や定数倍演算は、非特許文献１と同様に、各計算装置が単独で計算できる。乗算や論理回路演算については、非特許文献２と同様に各計算装置の協調計算が必要となる。更に本発明の秘密計算システムは、２進数変換や整数変換についても他の計算の単純な拡張として実現できる。これにより、算術演算および論理回路演算の組合せ計算が可能となる。また計算結果を復元する前に不正の有無を検証できるため、単独の計算装置が不正を働いたとしても入力値の秘匿性は保証される。
【０１０４】
以上のように、実施例１の秘密計算システムは、単純な計算により秘匿関数計算を実現しており、入力や各計算装置の処理の不正を効率良く検出できる特徴を持つ。また算術演算と論理回路演算の組み合わせにも適用できるため、算術演算とともに絶対値や大小比較といった論理回路演算が必要となるマイニングや統計処理に適している。
【実施例２】
【０１０５】
次に、論理回路Ｃの演算結果Ｃ（Ａ）＝Ｅを求める場合の秘密計算システムについて説明する。図２７に、実施例２の秘密計算システムの機能構成例を示す。また、図２８に、実施例２の秘密計算システムの処理フロー例を示す。実施例２の秘密計算システムも、３つの計算装置５００_Ｘ，５００_Ｙ，５００_Ｚと、これらの計算装置をつなぐネットワーク１００から構成される。この実施例では、Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とする。
【０１０６】
計算装置５００_Ｘは、乱数生成部５１１、第１演算送信部５２１、第１演算受信部５３１、第１演算復号部５４１、第１記録部５９１を有し、計算装置５００_Ｙは、第２置換乱数受信部５１２、要素生成部５２２、garbled circuit生成部５３２、第２演算送信部５４２、第２演算復号部５６２、第２記録部５９２を有し、計算装置５００_Ｚは、第３演算受信部５１３、演算実行部５２３、第３演算送信部５３３、第３演算復号部５４３、第３記録部５９３を有す。
【０１０７】
実施例２の秘密計算システムでも、入力である数値Ａは３つの断片に分けられ、３つの計算装置に分配された状態となっている。具体的には、数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を持つ。そして、計算装置５００_Ｘの第１記録部５９１が第１断片を記録し、計算装置５００_Ｙの第２記録部５９２が第２断片を記録し、計算装置５００_Ｚの第３記録部５９３が第３断片を記録する。
【０１０８】
計算装置５００_Ｘの乱数生成部５１１は、２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する（Ｓ５１１）。第１演算送信部５２１は、乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を計算装置５００_Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を計算装置５００_Ｚに送信する（Ｓ５２１）。計算装置５００_Ｙの第２置換乱数受信部５１２は、計算装置５００_Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する（Ｓ５１２）。要素生成部５２２は、Ｎビットの乱数ｅ_２１，ｅ_２２を生成し、第１要素ｅ_２１，第２要素ｅ_２２とする（Ｓ５２２）。
【０１０９】
計算装置５００_Ｙのgarbled circuit生成部５３２は、第１断片ａ_１が入力された場合に第１断片ｅ_１と第３要素ｅ_２３を出力する論理回路Ｃ”の入出力を乱数に置き換えたgarbled circuit ＧＣ”（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、garbled circuit ＧＣ”の出力である第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３それぞれを、第１断片ｅ_１，第３要素ｅ_２３に変換する第１断片関数ｔ_１，第３要素関数ｔ_２３を生成する（Ｓ５３２）。なお、garbled circuit ＧＣ”を生成する方法については、参考許文献１（Koji Chida and Katsumi Takahashi: Privacy Preserving Computations without Public Key Cryptographic Operation, Proc. of IWSEC 2008, pp.184-200.）の3.2 Protocol II、および 2 Previous WorkのYao’s Two Party Secure Function Evaluationに詳しく説明されている。第２演算送信部５４２は、第１断片関数ｔ_１を計算装置５００_Ｘに送信し、garbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を計算装置５００_Ｚに送信する（Ｓ５４２）。
【０１１０】
計算装置５００_Ｚの第３演算受信部５１３は、計算装置５００_Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、計算装置５００_Ｙからgarbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を受信する（Ｓ５１３）。演算実行部５２３は、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ”とを用いて、第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３を求める（Ｓ５２３）。第３演算送信部５３３は、第１乱数断片ｅ’_１を計算装置５００_Ｘに送信する（Ｓ５３３）。
【０１１１】
計算装置５００_Ｘの第１演算受信部５３１は、計算装置５００_Ｙから第１断片関数ｔ_１を受信し、計算装置５００_Ｚから第１乱数断片ｅ’_１を受信する（Ｓ５３１）。第１演算復号部５４１は、第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求め、第１記録部５９１に記録する（Ｓ５４１）。計算装置５００_Ｙの第２演算復号部５６２は、第２断片ｅ_２をｅ_２＝（ｅ_２１，ｅ_２２）とし、第２記録部５９２に記録する（Ｓ５６２）。計算装置５００_Ｚの第３演算復号部５４３は、第３要素ｅ_２３をｅ_２３＝ｔ_２３（ｅ’_２３）のように求め、第３断片ｅ_３をｅ_３＝（ｅ_２１，ｅ_２３）とし、第３記録部５９３に記録する（Ｓ５４３）。
【０１１２】
実施例２の秘密計算システムはこのような構成なので、任意の論理回路Ｃの結果Ｅの第１断片ｅ_１を第１記録部５９０_１が記録し、第２断片ｅ_２を第２記録部５９０_２が記録し、第３断片ｅ_３を第３記録部５９０_３が記録した状態となる。また、garbled circuitを用いているので、いずれの計算装置も入力の数値Ａも結果である数値Ｃも、単独では知ることができない。つまり、実施例２によれば、容易に任意の論理回路Ｃについての秘密計算システムを構築できる。また、数値を分散して記録する方法が実施例１と同じなので、実施例１の秘匿処理手段と復元手段を用いることができる。このように、実施例２の秘密計算システムも実施例１と同様の効果が得られる。
【実施例３】
【０１１３】
実施例２では、実施例１と同じ方法で数値を分散して記録することを前提に、任意の論理回路Ｃについての秘密計算システムを構築した。実施例３では、数値を分散して記録する部分を一般化した秘密計算システムについて説明する。実施例３の秘密計算システムも、論理回路Ｃの演算結果Ｃ（Ａ）＝Ｅを求めるシステムである。図２９に、実施例３の秘密計算システムの機能構成例を示す。また、図３０に、実施例３の秘密計算システムの処理フロー例を示す。実施例３の秘密計算システムも、３つの計算装置７００_Ｘ，７００_Ｙ，７００_Ｚと、これらの計算装置をつなぐネットワーク１００から構成される。この実施例では、Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ_１，ａ_２，ａ_３をＮビット以下の数値Ａの第１断片，第２断片，第３断片、ｅ_１，ｅ_２，ｅ_３を数値Ａを論理回路Ｃに入力したときの出力Ｅ＝Ｃ（Ａ）の第１断片，第２断片，第３断片、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とする。また、ｆ_１を任意の数値から第１断片を求める関数、ｆ_２を任意の数値から第２断片を求める関数、ｆ_３を任意の数値から第３断片を求める関数、ｇ_１２を第１断片と第２断片から元の数値を復元する関数、ｇ_２３を第２断片と第３断片から元の数値を復元する関数、ｇ_１３を第１断片と第３断片から元の数値を復元する関数とする。
【０１１４】
計算装置７００_Ｘは、乱数生成部５１１、第１演算送信部５２１、第１演算受信部５３１、第１演算復号部５４１、第１記録部５９１を有し、計算装置Ｙは、第２置換乱数受信部５１２、garbled circuit生成部７３２、第２演算送信部７４２、第２乱数断片受信部７５２、第２演算復号部７６２、第２記録部７９２を有し、計算装置７００_Ｚは、第３演算受信部７１３、演算実行部７２３、第３演算送信部７３３、第３演算復号部７４３、第３記録部７９３を有す。
【０１１５】
実施例３の秘密計算システムでは、入力である数値Ａは３つの断片に分けられ、３つの計算装置に分配された状態となっている。具体的には、数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ｆ_１（Ａ）
ａ_２＝ｆ_２（Ａ）
ａ_３＝ｆ_３（Ａ）
Ａ＝ｇ_１２（ａ_１，ａ_２）＝ｇ_２３（ａ_２，ａ_３）＝ｇ_１３（ａ_１，ａ_３）
の関係を持つ。そして、計算装置７００_Ｘの第１記録部５９１が第１断片を記録し、計算装置７００_Ｙの第２記録部７９２が第２断片を記録し、計算装置７００_Ｚの第３記録部７９３が第３断片を記録する。
【０１１６】
計算装置７００_Ｘの乱数生成部５１１は、２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する（Ｓ５１１）。第１演算送信部５２１は、乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を計算装置７００_Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を計算装置７００_Ｚに送信する（Ｓ５２１）。
【０１１７】
計算装置７００_Ｙの第２置換乱数受信部５１２は、計算装置７００_Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する（Ｓ５１２）。garbled circuit生成部７３２は、第１断片ａ_１が入力された場合に第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３を出力する論理回路Ｃ’の入出力を乱数に置き換えたgarbled circuit ＧＣ’（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、前記garbled circuit ＧＣ’の出力である第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３それぞれを、第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３に変換する第１断片関数ｔ_１，第２断片関数ｔ_２，第３断片関数ｔ_３を生成する（Ｓ７３２）。なお、garbled circuit ＧＣ’を生成する方法については、参考許文献１（Koji Chida and Katsumi Takahashi: Privacy Preserving Computations without Public Key Cryptographic Operation, Proc. of IWSEC 2008, pp.184-200.）の3.2 Protocol II、および 2 Previous WorkのYao’s Two Party Secure Function Evaluationに詳しく説明されている。第２演算送信部７４２は、第１断片関数ｔ_１を計算装置７００_Ｘに送信し、garbled circuit ＧＣ’と第３断片関数ｔ_３を計算装置７００_Ｚに送信する（Ｓ７４２）。
【０１１８】
計算装置７００_Ｚの第３演算受信部７１３は、計算装置７００_Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、計算装置７００_Ｙからgarbled circuit ＧＣ’と第３断片関数ｔ_３を受信する（Ｓ７１３）。演算実行部７２３は、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ’とを用いて、第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３を求める（Ｓ７２３）。第３演算送信部７３３は、第１乱数断片ｅ’_１を計算装置７００_Ｘに送信し、第２乱数断片ｅ’_２を計算装置７００_Ｙに送信する（Ｓ７３３）。
【０１１９】
計算装置７００_Ｘの第１演算受信部５３１は、計算装置７００_Ｙから第１断片関数ｔ_１を受信し、計算装置７００_Ｚから第１乱数断片ｅ’_１を受信する（Ｓ５３１）。第１演算復号部５４１は、第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求め、第１記録部５９１に記録する（Ｓ５４１）。計算装置７００_Ｙの第２乱数断片受信部７５２は、計算装置７００_Ｚから第２乱数断片ｅ’_２を受信する（Ｓ７５２）。第２演算復号部７６２は、第２断片ｅ_２をｅ_２＝ｔ_２（ｅ’_２）のように求め、第２記録部７９２に記録する（Ｓ７６２）。計算装置７００_Ｚの第３演算復号部７４３は、第３断片ｅ_３をｅ_３＝ｔ_３（ｅ’_３）のように求め、第３記録部７９３に記録する（Ｓ７４３）。
【０１２０】
実施例３の秘密計算システムはこのような構成なので、任意の論理回路Ｃの結果Ｅの第１断片ｅ_１を第１記録部５９０_１が記録し、第２断片ｅ_２を第２記録部７９０_２が記録し、第３断片ｅ_３を第３記録部７９０_３が記録した状態となる。また、garbled circuitを用いているので、いずれの計算装置も入力の数値Ａも結果である数値Ｃも、単独では知ることができない。つまり、実施例３によれば、容易に任意の論理回路Ｃについての秘密計算システムを構築できる。このように、実施例３の秘密計算システムも実施例２と同様の効果が得られる。
【産業上の利用可能性】
【０１２１】
本発明は、プライバシー保護データマイニングなど、情報を秘密性を維持しながら情報を利用するようなシステムに利用することができる。
【符号の説明】
【０１２２】
１００、２００、５００、７００計算装置
１１０_１第１加算部１２０_１第１減算部
１３０_１第１定数倍計算部１４１_１乗算乱数生成部
１４２_１第１乗算部１４３_１第１乗算送信部
１５０_１第１否定部１９０_１、５９１第１記録部
１１０_２第２加算部１２０_２第２減算部
１３０_２第２定数倍計算部１４４_２第２乗算乱数受信部
１４５_２第２乗算中間値計算部１４６_２第２乗算送信部
１４７_２第２乗算中間値受信部１４８_２第２乗算部
１５０_２第２否定部１９０_２、５９２、７９２第２記録部
１１０_３第３加算部１２０_３第３減算部
１３０_３第３定数倍計算部１４４_３第３乗算乱数受信部
１４５_３第３乗算中間値計算部１４６_３第３乗算送信部
１４７_３第３乗算中間値受信部１４８_３第３乗算部
１５０_３第３否定部１９０_３、５９３、７９３第３記録部
１６１_１、１６１_２、１６１_３断片生成部
１６２_１、１６２_２、１６２_３断片分配部
１７１_１第１断片送信部１７２_１第１断片受信部
１７３_１第１復元部１７１_２第２断片送信部
１７２_２第２断片受信部１７３_２第２復元部
１７１_３第３断片送信部１７２_３第３断片受信部
１７３_３第３復元部１０１_１、１０１_２、１０１_３基本処理部
２４１_１第１乱数ｒ_ｘｙ共有部２４２_１第１Ｚ送信部
２３１_１第１乱数ｒ_ｘｚ共有部２３２_１第１Ｙ送信部
２２３_１第１受信部２２４_１第１断片確認部
２５１_１第１確認乱数生成部２１１_２要素送信部
２１２_２Ｙ要素受信部２１３_２Ｙ要素確認部
２４１_２第２乱数ｒ_ｘｙ共有部２４２_２第２Ｚ送信部
２２１_２第２乱数ｒ_ｙｚ共有部２２２_２第２Ｘ送信部
２３３_２第２受信部２３４_２第２断片確認部
２５１_２第２確認乱数生成部２１１_３Ｚ要素送信部
２１２_３Ｚ要素受信部２１３_３Ｚ要素確認部
２３１_３第３乱数ｒ_ｘｚ共有部２３２_３第３Ｙ送信部
２２１_３第３乱数ｒ_ｙｚ共有部２２２_３第３Ｘ送信部
２４３_３第３受信部２４４_３第３断片確認部
２５１_３第３確認乱数生成部２５４復元入力確認部
２５５復元出力確認部５１１乱数生成部
５２１第１演算送信部５３１第１演算受信部
５４１第１演算復号部５１２第２置換乱数受信部
５２２要素生成部５３２、７３２ garbled circuit生成部
５４２、７４２第２演算送信部７５２第２乱数断片受信部
５６２、７６２第２演算復号部５１３、７１３第３演算受信部
５２３、７２３演算実行部５３３、７３３第３演算送信部
５４３、７４３第３演算復号部

【特許請求の範囲】
【請求項１】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密加算手段として、
前記計算装置Ｘが、
Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算部
を有し、
前記計算装置Ｙが、
Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算部
を有し、
前記計算装置Ｚが、
Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算部
を有す
ことを特徴とする秘密計算システム。
【請求項２】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１−ｂ_１
のように求める第１減算部
を有し、
前記計算装置Ｙは、
Ａ−Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１−ｂ_２１，ａ_２２−ｂ_２２）
のように求める第２減算部
を有し、
前記計算装置Ｚは、
Ａ−Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１−ｂ_２１，ａ_２３−ｂ_２３）
のように求める第３減算部
を有す
ことを特徴とする秘密計算システム。
【請求項３】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝Ｂａ_１
のように求める第１定数倍計算部
を有し、
前記計算装置Ｙは、
Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（Ｂａ_２１，Ｂａ_２２）
のように求める第２定数倍計算部
を有し、
前記計算装置Ｚは、
Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（Ｂａ_２１，Ｂａ_２３）
のように求める第３定数倍計算部
を有す
ことを特徴とする秘密計算システム。
【請求項４】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
乱数ｒ_１，ｒ_２，ｒ_３，ｒ_４，ｒ_５を生成する乗算乱数生成部と、
Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１、第２要素ｃ_２２、第３要素ｃ_２３を
ｃ_１＝ａ_１ｂ_１−ｒ_３−r_４
ｃ_２２＝ｒ_５
ｃ_２３＝ｃ_１−ｃ_２２
のように求める第１乗算部と、
前記計算装置Ｙに（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を、前記計算装置Ｚに（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する第１乗算送信部と
を有し、
前記計算装置Ｙは、
前記計算装置Ｘから（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を受信する第２乗算乱数受信部と、
数値ｙを
ｙ＝ａ_２１ｂ_２１＋ａ_２１ｒ_２＋ｒ_１ｂ_２１＋ｒ_３
のように求める第２乗算中間値計算部と、
前記計算装置Ｚに数値ｙを送信する第２乗算送信部と、
前記計算装置Ｚから数値ｚを受信する第２乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ｙ＋ｚ，ｃ_２２）
のように求める第２乗算部
を有し、
前記計算装置Ｚは、
前記計算装置Ｘから（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を受信する第３乗算乱数受信部と、
数値ｚを
ｚ＝ａ_２１（ｂ_１−ｒ_２）＋（ａ_１−ｒ_１）ｂ_２１＋ｒ_４
のように求める第３乗算中間値計算部と、
前記計算装置Ｙに数値ｚを送信する第３乗算送信部と、
前記計算装置Ｙから数値ｙを受信する第３乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ｙ＋ｚ，ｃ_２３）
のように求める第３乗算部
を有す
ことを特徴とする秘密計算システム。
【請求項５】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝−ａ_１
のように求める第１否定部
を有し、
前記計算装置Ｙは、
１−Ａの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（１−ａ_２１，−ａ_２２）
のように求める第２否定部
を有し、
前記計算装置Ｚは、
１−Ａの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（１−ａ_２１，−ａ_２３）
のように求める第３否定部
を有す
ことを特徴とする秘密計算システム。
【請求項６】
請求項１から５のいずれかに記載の秘密計算システムであって、
いずれかの計算装置が、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配部と
を備えることを特徴とする秘密計算システム。
【請求項７】
請求項１記載の秘密計算システムであって、
ｊを１以上３以下の整数、ａ_１^（ｊ），ａ_２^（ｊ），ａ_３^（ｊ）を数値Ａに対するｊ番目の第１断片，第２断片，第３断片、ａ_２１^（ｊ）をｊ番目の第１要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ａ_１^（ｊ），第２断片ａ_２^（ｊ），第３断片ａ_３^（ｊ）に対して計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能する計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ａ_１^（１），ａ_２^（１），ａ_３^（１））、（ａ_１^（２），ａ_２^（２），ａ_３^（２））、（ａ_１^（３），ａ_２^（３），ａ_３^（３））はそれぞれ異なり、
秘匿処理手段は、任意の数値Ｓに対して、
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
前記計算装置Ｘが第１断片ｓ_１を、前記計算装置Ｙが第２断片ｓ_２を、前記計算装置Ｚが第３断片ｓ_３を記録した状態にする断片分配部と
を有する手段であり、
復元手段は、
前記計算装置Ｘが、
前記計算装置Ｙまたは前記計算装置Ｚに第１断片を送信する第１断片送信部と、
前記計算装置Ｙまたは前記計算装置Ｚから第１要素を受信する第１断片受信部と、
前記第１断片受信部が受信した第１要素と当該第１要素に対応する第１断片とを加算することで数値を復元する第１復元部
も有し、
前記計算装置Ｙが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｚに第２要素を送信する第２断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｚから第３要素を受信する第２断片受信部と、
前記第２断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第２断片受信部が受信した第３要素と当該第３要素に対応する第１要素と第２要素とを加算することで数値を復元する第２復元部
も有し、
前記計算装置Ｚが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｙに第３要素を送信する第３断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｙから第２要素を受信する第３断片受信部と、
前記第３断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第３断片受信部が受信した第２要素と当該第２要素に対応する第１要素と第３要素とを加算することで数値を復元する第３復元部
も有する手段であり、
すべての計算装置は、
前記秘匿手段と前記復元手段を有すると共に、
計算装置Ｘ^（ｊ）として機能するために、
計算装置Ｙ^（ｊ）との間で乱数ｒ_ｘｙを共有するための第１乱数ｒ_ｘｙ共有部と、
計算装置Ｚ^（ｊ）にｕ_ｘ（＝ａ_１^（ｊ）＋ｒ_ｘｙ）を送信する第１Ｚ送信部と、
計算装置Ｚ^（ｊ）との間で乱数ｒ_ｘｚを共有するための第１乱数ｒ_ｘｚ共有部と、
計算装置Ｙ^（ｊ）にｕ_ｘ（＝ａ_１^（ｊ）＋ｒ_ｘｚ）を送信する第１Ｙ送信部と、
計算装置Ｙ^（ｊ）からｕ_ｙを、計算装置Ｚ^（ｊ）からｕ_ｚを受信する第１受信部と、
ａ_１^（ｊ）＝ｕ_ｙ＋ｕ_ｚであることを確認する第１断片確認部と、
乱数ｒ_ｘを生成する第１確認乱数生成部と、
を有し、
計算装置Ｙ^（ｊ）として機能するために、
計算装置Ｚ^（ｊ）に自己が保有する第１要素ａ_２１ｙ^（ｊ）を送信するＹ要素送信部と、
計算装置Ｚ^（ｊ）から第１要素ａ_２１ｚ^（ｊ）を受信するＹ要素受信部と、
自己が保有する第１要素ａ_２１ｙ^（ｊ）と計算装置Ｚ^（ｊ）から受信した第１要素ａ_２１ｚ^（ｊ）とが等しいことを確認するＹ要素確認部と、
計算装置Ｘ^（ｊ）との間で乱数ｒ_ｘｙを共有するための第２乱数ｒ_ｘｙ共有部と、
計算装置Ｚ^（ｊ）にｕ_ｙ（＝ａ_２２^（ｊ）＋ｒ_ｘｙ）を送信する第２Ｚ送信部と、
計算装置Ｚ^（ｊ）との間で乱数ｒ_ｙｚを共有するための第２乱数ｒ_ｙｚ共有部と、
計算装置Ｘ^（ｊ）にｕ_ｙ（＝ａ_２２^（ｊ）＋ｒ_ｙｚ）を送信する第２Ｘ送信部と、
計算装置Ｘ^（ｊ）からｕ_ｘを、計算装置Ｚ^（ｊ）からｕ_ｚを受信する第２受信部と、
ａ_２２^（ｊ）＝ｕ_ｘ−ｕ_ｚであることを確認する第２断片確認部と、
乱数ｒ_ｙを生成する第２確認乱数生成部と、
を有し、
計算装置Ｚ^（ｊ）として機能するために、
計算装置Ｙ^（ｊ）に自己が保有する第１要素ａ_２１ｚ^（ｊ）を送信するＺ要素送信部と、
計算装置Ｙ^（ｊ）から第１要素ａ_２１ｙ^（ｊ）を受信するＺ要素受信部と、
自己が保有する第１要素ａ_２１ｚ^（ｊ）と計算装置Ｙ^（ｊ）から受信した第１要素ａ_２１ｙ^（ｊ）とが等しいことを確認するＺ要素確認部と、
計算装置Ｘ^（ｊ）との間で乱数ｒ_ｘｚを共有するための第３乱数ｒ_ｘｚ共有部と、
計算装置Ｙ^（ｊ）にｕ_ｚ（＝ａ_２３^（ｊ）＋ｒ_ｘｚ）を送信する第３Ｙ送信部と、
計算装置Ｙ^（ｊ）との間で乱数ｒ_ｙｚを共有するための第３乱数ｒ_ｙｚ共有部と、
計算装置Ｘ^（ｊ）にｕ_ｚ（＝ａ_２３^（ｊ）−ｒ_ｙｚ）を送信する第３Ｘ送信部と、
計算装置Ｘ^（ｊ）からｕ_ｘを、計算装置Ｙ^（ｊ）からｕ_ｙを受信する第３受信部と、
ａ_２３^（ｊ）＝ｕ_ｘ−ｕ_ｙであることを確認する第３断片確認部と、
乱数ｒ_ｚを生成する第３確認乱数生成部と
を有し、
前記秘匿手段は、
計算装置Ｘ^（ｊ）として機能するときは、第１断片ａ_１^（ｊ），乱数ｒ_ｘの断片を分散した状態とし、
計算装置Ｙ^（ｊ）として機能するときは、第１要素ａ_２１^（ｊ），乱数ｒ_ｙの断片を分散した状態とし、
計算装置Ｚ^（ｊ）として機能するときは、乱数ｒ_ｚの断片を分散した状態とする
手段であり、
前記秘密加算手段は
ａ_１^（ｊ）＋ａ_２１^（ｊ）＋ｒ
の断片を求める手段であり、
前記復元手段は
ａ_１^（１）＋ａ_２１^（１）＋ｒ，ａ_１^（２）＋ａ_２１^（２）＋ｒ，ａ_１^（３）＋ａ_２１^（３）＋ｒ
を復元する手段であり、
３つの復元結果を取得できるいずれかの計算装置が、３つの結果が等しいことを確認する復元入力確認部を備える
ことを特徴とする秘密計算システム。
【請求項８】
同一の数値に対する異なる３種類の断片の組合せを入力とし、それぞれの断片の組合せに対して計算を行う請求項１記載の秘密計算システムであって、
ｊを１以上３以下の整数、ｃ_１^（ｊ），ｃ_２^（ｊ），ｃ_３^（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ_２１^（ｊ），ｃ_２２^（ｊ），ｃ_２３^（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ｃ_１^（ｊ），第２断片ｃ_２^（ｊ），第３断片ｃ_３^（ｊ）を求めたときに計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能した計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ｃ_１^（１），ｃ_２^（１），ｃ_３^（１））、（ｃ_１^（２），ｃ_２^（２），ｃ_３^（２））、（ｃ_１^（３），ｃ_２^（３），ｃ_３^（３））はそれぞれ異なり、
秘匿処理手段は、任意の数値Ｓに対して、
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
前記計算装置Ｘが第１断片ｓ_１を、前記計算装置Ｙが第２断片ｓ_２を、前記計算装置Ｚが第３断片ｓ_３を記録した状態にする断片分配部と
を有する手段であり、
復元手段は、
前記計算装置Ｘが、
前記計算装置Ｙまたは前記計算装置Ｚに第１断片を送信する第１断片送信部と、
前記計算装置Ｙまたは前記計算装置Ｚから第１要素を受信する第１断片受信部と、
前記第１断片受信部が受信した第１要素と当該第１要素に対応する第１断片とを加算することで数値を復元する第１復元部
も有し、
前記計算装置Ｙが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｚに第２要素を送信する第２断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｚから第３要素を受信する第２断片受信部と、
前記第２断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第２断片受信部が受信した第３要素と当該第３要素に対応する第１要素と第２要素とを加算することで数値を復元する第２復元部
も有し、
前記計算装置Ｚが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｙに第３要素を送信する第３断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｙから第２要素を受信する第３断片受信部と、
前記第３断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第３断片受信部が受信した第２要素と当該第２要素に対応する第１要素と第３要素とを加算することで数値を復元する第３復元部
も有する手段であり、
すべての計算装置は、
前記秘匿手段と前記復元手段を有すると共に、
計算装置Ｘ^（ｊ）として機能するために、乱数ｒ_ｘを生成する第１確認乱数生成部を有し、
計算装置Ｙ^（ｊ）として機能するために、乱数ｒ_ｙを生成する第２確認乱数生成部を有し、
計算装置Ｚ^（ｊ）として機能するために、乱数ｒ_ｚを生成する第３確認乱数生成部を有し、
前記秘匿手段は、
計算装置Ｘ^（ｊ）として機能するときは、第１断片ｃ_１^（ｊ），乱数ｒ_ｘの断片を分散した状態とし、
計算装置Ｙ^（ｊ）として機能するときは、第１要素ｃ_２１^（ｊ），乱数ｒ_ｙの断片を分散した状態とし、
計算装置Ｚ^（ｊ）として機能するときは、乱数ｒ_ｚの断片を分散した状態とする
手段であり、
前記秘密加算手段は
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
の断片を求める手段でもあり、
前記復元手段は
ｊ＝１，２，３に対して、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
の計算結果を、計算装置Ｘ^（ｊ）と計算装置Ｙ^（ｊ）による復元と、計算装置Ｙ^（ｊ）と計算装置Ｚ^（ｊ）による復元と、計算装置Ｘ^（ｊ）と計算装置Ｚ^（ｊ）による復元とを行う手段であり、
９つの復元結果を取得できるいずれかの計算装置が、９つの結果が等しいことを確認する復元出力確認部を備える
ことを特徴とする秘密計算システム。
【請求項９】
同一の数値に対する異なる３種類の断片の組合せを入力とし、それぞれの断片の組合せに対して計算を行う請求項２から５のいずれかに記載の秘密計算システムであって、
ｊを１以上３以下の整数、ｃ_１^（ｊ），ｃ_２^（ｊ），ｃ_３^（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ_２１^（ｊ），ｃ_２２^（ｊ），ｃ_２３^（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ｃ_１^（ｊ），第２断片ｃ_２^（ｊ），第３断片ｃ_３^（ｊ）を求めたときに計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能した計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ｃ_１^（１），ｃ_２^（１），ｃ_３^（１））、（ｃ_１^（２），ｃ_２^（２），ｃ_３^（２））、（ｃ_１^（３），ｃ_２^（３），ｃ_３^（３））はそれぞれ異なり、
秘匿処理手段は、任意の数値Ｓに対して、
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
前記計算装置Ｘが第１断片ｓ_１を、前記計算装置Ｙが第２断片ｓ_２を、前記計算装置Ｚが第３断片ｓ_３を記録した状態にする断片分配部と
を有する手段であり、
秘密加算手段は、
前記計算装置Ｘが、
Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算部
を有し、
前記計算装置Ｙが、
Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算部
を有し、
前記計算装置Ｚが、
Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算部
を有する手段であり、
復元手段は、
前記計算装置Ｘが、
前記計算装置Ｙまたは前記計算装置Ｚに第１断片を送信する第１断片送信部と、
前記計算装置Ｙまたは前記計算装置Ｚから第１要素を受信する第１断片受信部と、
前記第１断片受信部が受信した第１要素と当該第１要素に対応する第１断片とを加算することで数値を復元する第１復元部
も有し、
前記計算装置Ｙが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｚに第２要素を送信する第２断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｚから第３要素を受信する第２断片受信部と、
前記第２断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第２断片受信部が受信した第３要素と当該第３要素に対応する第１要素と第２要素とを加算することで数値を復元する第２復元部
も有し、
前記計算装置Ｚが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｙに第３要素を送信する第３断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｙから第２要素を受信する第３断片受信部と、
前記第３断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第３断片受信部が受信した第２要素と当該第２要素に対応する第１要素と第３要素とを加算することで数値を復元する第３復元部
も有する手段であり、
すべての計算装置は、
前記秘匿手段と前記秘密加算手段と前記復元手段を有すると共に、
計算装置Ｘ^（ｊ）として機能するために、乱数ｒ_ｘを生成する第１確認乱数生成部を有し、
計算装置Ｙ^（ｊ）として機能するために、乱数ｒ_ｙを生成する第２確認乱数生成部を有し、
計算装置Ｚ^（ｊ）として機能するために、乱数ｒ_ｚを生成する第３確認乱数生成部を有し、
前記秘匿手段は、
計算装置Ｘ^（ｊ）として機能するときは、第１断片ｃ_１^（ｊ），乱数ｒ_ｘの断片を分散した状態とし、
計算装置Ｙ^（ｊ）として機能するときは、第１要素ｃ_２１^（ｊ），乱数ｒ_ｙの断片を分散した状態とし、
計算装置Ｚ^（ｊ）として機能するときは、乱数ｒ_ｚの断片を分散した状態とする
手段であり、
前記秘密加算手段は
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
の断片を求める手段であり、
前記復元手段は
ｊ＝１，２，３に対して、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
の計算結果を、計算装置Ｘ^（ｊ）と計算装置Ｙ^（ｊ）による復元と、計算装置Ｙ^（ｊ）と計算装置Ｚ^（ｊ）による復元と、計算装置Ｘ^（ｊ）と計算装置Ｚ^（ｊ）による復元とを行う手段であり、
９つの復元結果を取得できるいずれかの計算装置が、９つの結果が等しいことを確認する復元出力確認部を備える
ことを特徴とする秘密計算システム。
【請求項１０】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とし、
前記計算装置Ｘは、
２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する乱数生成部と、
乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を前記計算装置Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を前記計算装置Ｚに送信する第１演算送信部と、
前記計算装置Ｙから第１断片関数ｔ_１を受信し、前記計算装置Ｚから第１乱数断片ｅ’_１を受信する第１演算受信部と、
第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求める第１演算復号部と
を有し、
前記計算装置Ｙは、
前記計算装置Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する第２置換乱数受信部と、
Ｎビットの乱数ｅ_２１，ｅ_２２を生成し、第１要素ｅ_２１，第２要素ｅ_２２とする要素生成部と、
第１断片ａ_１が入力された場合に第１断片ｅ_１と第３要素ｅ_２３を出力する論理回路Ｃ”の入出力を乱数に置き換えたgarbled circuit ＧＣ”（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、前記garbled circuit ＧＣ”の出力である第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３それぞれを、第１断片ｅ_１，第３要素ｅ_２３に変換する第１断片関数ｔ_１，第３要素関数ｔ_２３を生成するgarbled circuit生成部と、
第１断片関数ｔ_１を前記計算装置Ｘに送信し、garbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を前記計算装置Ｚに送信する第２演算送信部と、
第２断片ｅ_２をｅ_２＝（ｅ_２１，ｅ_２２）とする第２演算復号部と
を有し、
前記計算装置Ｚは、
前記計算装置Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、前記計算装置Ｙからgarbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を受信する第３演算受信部と、
ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ”とを用いて、第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３を求める演算実行部と、
第１乱数断片ｅ’_１を前記計算装置Ｘに送信する第３演算送信部と、
第３要素ｅ_２３をｅ_２３＝ｔ_２３（ｅ’_２３）のように求め、第３断片ｅ_３をｅ_３＝（ｅ_２１，ｅ_２３）とする第３演算復号部と
を有す
ことを特徴とする秘密計算システム。
【請求項１１】
請求項１から６、もしくは１０のいずれかに記載の秘密計算システムであって、
さらに、復元手段として、
前記計算装置Ｘが、
前記計算装置Ｙまたは前記計算装置Ｚに第１断片を送信する第１断片送信部と、
前記計算装置Ｙまたは前記計算装置Ｚから第１要素を受信する第１断片受信部と、
前記第１断片受信部が受信した第１要素と当該第１要素に対応する第１断片とを加算することで数値を復元する第１復元部
も有し、
前記計算装置Ｙが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｚに第２要素を送信する第２断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｚから第３要素を受信する第２断片受信部と、
前記第２断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第２断片受信部が受信した第３要素と当該第３要素に対応する第１要素と第２要素とを加算することで数値を復元する第２復元部
も有し、
前記計算装置Ｚが、
前記計算装置Ｘに第１要素を送信する、または前記計算装置Ｙに第３要素を送信する第３断片送信部と、
前記計算装置Ｘから第１断片を受信する、または前記計算装置Ｙから第２要素を受信する第３断片受信部と、
前記第３断片受信部が受信した第１断片と当該第１断片に対応する第１要素とを加算することで数値を復元する、または前記第３断片受信部が受信した第２要素と当該第２要素に対応する第１要素と第３要素とを加算することで数値を復元する第３復元部
も有す
ことを特徴とする秘密計算システム。
【請求項１２】
第１断片を記録する計算装置Ｘと、
第２断片を記録する計算装置Ｙと、
第３断片を記録する計算装置Ｚから構成される秘密計算システムであって、
前記第１断片，第２断片，第３断片は、これらの中の２つが分かれば元の数値が復元できるものであり、
Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ_１，ａ_２，ａ_３をＮビット以下の数値Ａの第１断片，第２断片，第３断片、ｅ_１，ｅ_２，ｅ_３を数値Ａを論理回路Ｃに入力したときの出力Ｅ＝Ｃ（Ａ）の第１断片，第２断片，第３断片、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とし、
前記計算装置Ｘは、
２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する乱数生成部と、
乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を前記計算装置Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を前記計算装置Ｚに送信する第１演算送信部と、
前記計算装置Ｙから第１断片関数ｔ_１を受信し、前記計算装置Ｚから第１乱数断片ｅ’_１を受信する第１演算受信部と、
第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求める第１演算復号部と
を有し、
前記計算装置Ｙは、
前記計算装置Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する第２置換乱数受信部と、
第１断片ａ_１が入力された場合に第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３を出力する論理回路Ｃ’の入出力を乱数に置き換えたgarbled circuit ＧＣ’（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、前記garbled circuit ＧＣ’の出力である第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３それぞれを、第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３に変換する第１断片関数ｔ_１，第２断片関数ｔ_２，第３断片関数ｔ_３を生成するgarbled circuit生成部と、
第１断片関数ｔ_１を前記計算装置Ｘに送信し、garbled circuit ＧＣ’と第３断片関数ｔ_３を前記計算装置Ｚに送信する第２演算送信部と、
前記計算装置Ｚから第２乱数断片ｅ’_２を受信する第２乱数断片受信部と、
第２断片ｅ_２をｅ_２＝ｔ_２（ｅ’_２）のように求める第２演算復号部と
を有し、
前記計算装置Ｚは、
前記計算装置Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、前記計算装置Ｙからgarbled circuit ＧＣ’と第３断片関数ｔ_３を受信する第３演算受信部と、
ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ’とを用いて、第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３を求める演算実行部と、
第１乱数断片ｅ’_１を前記計算装置Ｘに送信し、第２乱数断片ｅ’_２を前記計算装置Ｙに送信する第３演算送信部と、
第３断片ｅ_３をｅ_３＝ｔ_３（ｅ’_３）のように求める第３演算復号部と
を有す
ことを特徴とする秘密計算システム。
【請求項１３】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密加算過程として、
前記計算装置Ｘが、Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算ステップと、
前記計算装置Ｙが、Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算ステップと、
前記計算装置Ｚが、Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１４】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密減算過程として、
前記計算装置Ｘが、Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１−ｂ_１
のように求める第１減算ステップと、
前記計算装置Ｙが、Ａ−Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１−ｂ_２１，ａ_２２−ｂ_２２）
のように求める第２減算ステップと、
前記計算装置Ｚが、Ａ−Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１−ｂ_２１，ａ_２３−ｂ_２３）
のように求める第３減算ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１５】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密定数倍過程として、
前記計算装置Ｘが、Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝Ｂａ_１
のように求める第１定数倍計算ステップと、
前記計算装置Ｙが、Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（Ｂａ_２１，Ｂａ_２２）
のように求める第２定数倍計算ステップと、
前記計算装置Ｚが、Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（Ｂａ_２１，Ｂａ_２３）
のように求める第３定数倍計算ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１６】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密乗算過程として、
前記計算装置Ｘが、乱数ｒ_１，ｒ_２，ｒ_３，ｒ_４，ｒ_５を生成する乗算乱数生成ステップと、
前記計算装置Ｘが、Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１、第２要素ｃ_２２、第３要素ｃ_２３を
ｃ_１＝ａ_１ｂ_１−ｒ_３−r_４
ｃ_２２＝ｒ_５
ｃ_２３＝ｃ_１−ｃ_２２
のように求める第１乗算ステップと、
前記計算装置Ｘが、前記計算装置Ｙに（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を、前記計算装置Ｚに（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する第１乗算送信ステップと、
前記計算装置Ｙが、前記計算装置Ｘから（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を受信する第２乗算乱数受信ステップと、
前記計算装置Ｚが、前記計算装置Ｘから（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を受信する第３乗算乱数受信ステップと、
前記計算装置Ｙが、数値ｙを
ｙ＝ａ_２１ｂ_２１＋ａ_２１ｒ_２＋ｒ_１ｂ_２１＋ｒ_３
のように求める第２乗算中間値計算ステップと、
前記計算装置Ｚが、数値ｚを
ｚ＝ａ_２１（ｂ_１−ｒ_２）＋（ａ_１−ｒ_１）ｂ_２１＋ｒ_４
のように求める第３乗算中間値計算ステップと、
前記計算装置Ｙが、前記計算装置Ｚに数値ｙを送信する第２乗算送信ステップと、
前記計算装置Ｚが、前記計算装置Ｙに数値ｚを送信する第３乗算送信ステップと、
前記計算装置Ｙが、前記計算装置Ｚから数値ｚを受信する第２乗算中間値受信ステップと、
前記計算装置Ｚが、前記計算装置Ｙから数値ｙを受信する第３乗算中間値受信ステップと、
前記計算装置Ｙが、Ａ×Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ｙ＋ｚ，ｃ_２２）
のように求める第２乗算ステップと、
前記計算装置Ｚが、Ａ×Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ｙ＋ｚ，ｃ_２３）
のように求める第３乗算ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１７】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密否定過程として、
前記計算装置Ｘが、１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝−ａ_１
のように求める第１否定ステップと、
前記計算装置Ｙが、１−Ａの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（１−ａ_２１，−ａ_２２）
のように求める第２否定ステップと、
前記計算装置Ｚが、１−Ａの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（１−ａ_２１，−ａ_２３）
のように求める第３否定ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１８】
請求項１３から１７のいずれかに記載の秘密計算方法であって、
いずれかの計算装置が、
秘匿処理過程として、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成ステップと、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配ステップと
を有す
ことを特徴とする秘密計算方法。
【請求項１９】
請求項１３記載の秘密計算方法であって、
ｊを１以上３以下の整数、ａ_１^（ｊ），ａ_２^（ｊ），ａ_３^（ｊ）を数値Ａに対するｊ番目の第１断片，第２断片，第３断片、ａ_２１^（ｊ）をｊ番目の第１要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ａ_１^（ｊ），第２断片ａ_２^（ｊ），第３断片ａ_３^（ｊ）に対して計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能する計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ａ_１^（１），ａ_２^（１），ａ_３^（１））、（ａ_１^（２），ａ_２^（２），ａ_３^（２））、（ａ_１^（３），ａ_２^（３），ａ_３^（３））はそれぞれ異なり、
秘匿処理過程は、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成ステップと、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配ステップと
を有する過程であり、
復元過程は、
計算装置Ｘが、計算装置Ｙに第１断片ａ_１を送信する第１断片Ｙ送信サブステップと、
計算装置Ｙが、計算装置Ｘから第１断片ａ_１を受信する第２断片Ｘ受信サブステップと、
計算装置Ｙが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値Ａを復元する第２Ｘ復元サブステップ
からなる復元ＸＹステップ、
計算装置Ｘが、計算装置１００_Ｚに第１断片ａ_１を送信する第１断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｘから第１断片ａ_１を受信する第３断片Ｘ受信サブステップと、
計算装置Ｚが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値を復元する第３Ｘ復元サブステップと
からなる復元ＸＺステップ、
計算装置Ｙが、計算装置Ｘに第１要素ａ_２１を送信する第２断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｙから第１要素ａ_２１を受信する第１断片Ｙ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｙ復元サブステップと
からなる復元ＹＸステップ、
計算装置Ｙが、計算装置Ｚに第２要素ａ_２２を送信する第２断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｙから第２要素ａ_２１を受信する第３断片Ｙ受信サブステップと、
計算装置Ｚが、受信した第２要素ａ_２２と当該第２要素ａ_２２に対応する第１要素ａ_２１と第３要素ａ_２３とを加算することで数値を復元する第３Ｙ復元サブステップと
からなる復元ＹＺステップ、
計算装置Ｚが、計算装置Ｘに第１要素ａ_２１を送信する第３断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｚから第１要素ａ_２１を受信する第１断片Ｚ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｚ復元サブステップと
からなる復元ＺＸステップ、
計算装置Ｚが、計算装置Ｙに第３要素ａ_２３を送信する第３断片送信サブステップと、
計算装置Ｙが、計算装置Ｚから第３要素ａ_２３を受信する第２断片受信サブステップと、
計算装置Ｙが、受信した第３要素ａ_２３と当該第３要素ａ_２３に対応する第１要素ａ_２１と第２要素ａ_２２とを加算することで数値Ａを復元する第２復元サブステップと
からなる復元ＺＹステップ
の中の少なくともいずれか１つのステップを有する過程であり、
いずれかの計算装置が、ｊ＝１とする初期化ステップと、
計算装置Ｙ^（ｊ）が保有する第１要素ａ_２１ｙ^（ｊ）と計算装置Ｚ^（ｊ）が保有する第１要素ａ_２１ｚ^（ｊ）とが等しいことを確認する第１要素不正検出ステップと、
第１断片ａ_１^（ｊ）が第２要素ａ_２２^（ｊ）と第３要素ａ_２３^（ｊ）の和であることを確認する第１断片不正検出ステップと、
第２要素ａ_２２^（ｊ）が第１断片ａ_１^（ｊ）と第３要素ａ_２３^（ｊ）の差であることを確認する第２要素不正検出ステップと、
第３要素ａ_２３^（ｊ）が第１断片ａ_１^（ｊ）と第２要素ａ_２２^（ｊ）の差であることを確認する第３要素不正検出ステップと、
計算装置Ｘ^（ｊ）が、乱数ｒ_ｘを生成する第１確認乱数生成ステップと、
計算装置Ｘ^（ｊ）が、前記秘匿処理過程によって第１断片ａ_１^（ｊ），乱数ｒ_ｘの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｘステップと、
計算装置Ｙ^（ｊ）が、乱数ｒ_ｙを生成する第２確認乱数生成ステップと、
計算装置Ｙ^（ｊ）が、前記秘匿処理過程によって第１要素ａ_２１^（ｊ），乱数ｒ_ｙの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｙステップと、
計算装置Ｚ^（ｊ）が、乱数ｒ_ｚを生成する第３確認乱数生成ステップと、
計算装置２００_Ｚ^（ｊ）が、前記秘匿処理過程によって乱数ｒ_ｚの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｚステップと、
前記秘密加算過程によって、
ａ_１^（ｊ）＋ａ_２１^（ｊ）＋ｒ
ただし、ｒ＝ｒ_ｘ＋ｒ_ｙ＋ｒ_ｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする秘密加算ステップと、
前記復元過程によって、
ａ_１^（ｊ）＋ａ_２１^（ｊ）＋ｒ
を復元し、いずれかの計算装置に記録しておく入力復元ステップと、
いずれかの計算装置が、ｊ＝３かを確認する条件確認ステップと、
ｊ≠３のときにはｊにｊ＋１を代入し、前記第１要素不正検出ステップに戻る繰返ステップと、
ｊ＝３のときには、いずれかの計算装置が、３つの復元結果ａ_１^（１）＋ａ_２１^（１）＋ｒ，ａ_１^（２）＋ａ_２１^（２）＋ｒ，ａ_１^（３）＋ａ_２１^（３）＋ｒが等しいことを確認する結果確認ステップと
を有すことを特徴とする秘密計算方法。
【請求項２０】
同一の数値に対する異なる３種類の断片の組合せを入力とし、それぞれの断片の組合せに対して計算を行う請求項１３記載の秘密計算方法であって、
ｊを１以上３以下の整数、ｃ_１^（ｊ），ｃ_２^（ｊ），ｃ_３^（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ_２１^（ｊ），ｃ_２２^（ｊ），ｃ_２３^（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ｃ_１^（ｊ），第２断片ｃ_２^（ｊ），第３断片ｃ_３^（ｊ）を求めたときに計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能した計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ｃ_１^（１），ｃ_２^（１），ｃ_３^（１））、（ｃ_１^（２），ｃ_２^（２），ｃ_３^（２））、（ｃ_１^（３），ｃ_２^（３），ｃ_３^（３））はそれぞれ異なり、
秘匿処理過程は、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成ステップと、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配ステップと
を有する過程であり、
復元過程は、
計算装置Ｘが、計算装置Ｙに第１断片ａ_１を送信する第１断片Ｙ送信サブステップと、
計算装置Ｙが、計算装置Ｘから第１断片ａ_１を受信する第２断片Ｘ受信サブステップと、
計算装置Ｙが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値Ａを復元する第２Ｘ復元サブステップ
からなる復元ＸＹステップ、
計算装置Ｘが、計算装置１００_Ｚに第１断片ａ_１を送信する第１断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｘから第１断片ａ_１を受信する第３断片Ｘ受信サブステップと、
計算装置Ｚが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値を復元する第３Ｘ復元サブステップと
からなる復元ＸＺステップ、
計算装置Ｙが、計算装置Ｘに第１要素ａ_２１を送信する第２断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｙから第１要素ａ_２１を受信する第１断片Ｙ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｙ復元サブステップと
からなる復元ＹＸステップ、
計算装置Ｙが、計算装置Ｚに第２要素ａ_２２を送信する第２断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｙから第２要素ａ_２１を受信する第３断片Ｙ受信サブステップと、
計算装置Ｚが、受信した第２要素ａ_２２と当該第２要素ａ_２２に対応する第１要素ａ_２１と第３要素ａ_２３とを加算することで数値を復元する第３Ｙ復元サブステップと
からなる復元ＹＺステップ、
計算装置Ｚが、計算装置Ｘに第１要素ａ_２１を送信する第３断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｚから第１要素ａ_２１を受信する第１断片Ｚ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｚ復元サブステップと
からなる復元ＺＸステップ、
計算装置Ｚが、計算装置Ｙに第３要素ａ_２３を送信する第３断片送信サブステップと、
計算装置Ｙが、計算装置Ｚから第３要素ａ_２３を受信する第２断片受信サブステップと、
計算装置Ｙが、受信した第３要素ａ_２３と当該第３要素ａ_２３に対応する第１要素ａ_２１と第２要素ａ_２２とを加算することで数値Ａを復元する第２復元サブステップと
からなる復元ＺＹステップ
の中の少なくともいずれか１つのステップを有する過程であり、
いずれかの計算装置が、ｊ＝１とする初期化ステップと、
計算装置Ｘ^（ｊ）が、乱数ｒ_ｘを生成する第１確認乱数生成ステップと、
計算装置Ｘ^（ｊ）が、前記秘匿処理過程によって第１断片ｃ_１^（ｊ），乱数ｒ_ｘの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｘステップと、
計算装置Ｙ^（ｊ）が、乱数ｒ_ｙを生成する第２確認乱数生成ステップと、
計算装置Ｙ^（ｊ）が、前記秘匿処理過程によって第１要素ｃ_２１^（ｊ），乱数ｒ_ｙの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｙステップと、
計算装置Ｚ^（ｊ）が、乱数ｒ_ｚを生成する第３確認乱数生成ステップと、
計算装置Ｚ^（ｊ）が、前記秘匿処理過程によって乱数ｒ_ｚの断片を３つの計算装置で分散して記録した状態にする秘匿Ｚステップと、
前記秘密加算過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
ただし、ｒ＝ｒ_ｘ＋ｒ_ｙ＋ｒ_ｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする秘密加算ステップと、
前記復元ＸＹステップまたは復元ＹＸステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＹ^（ｊ）を復元して記録しておき、
前記復元ＹＺステップまたは復元ＺＹステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＹＺ^（ｊ）を復元して記録しておき、
前記復元ＸＺステップまたは復元ＺＸステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＺ^（ｊ）を復元して記録しておく結果復元ステップと、
いずれかの計算装置が、ｊ＝３かを確認する条件確認ステップと、
ｊ≠３のときにはｊにｊ＋１を代入し、前記第１確認乱数生成ステップに戻る繰返ステップと、
ｊ＝３のときには、９つの復元結果Ｃ_ＸＹ^（１），Ｃ_ＹＺ^（１），Ｃ_ＸＺ^（１），Ｃ_ＸＹ^（２），Ｃ_ＹＺ^（２），Ｃ_ＸＺ^（２），Ｃ_ＸＹ^（３），Ｃ_ＹＺ^（３），Ｃ_ＸＺ^（３）がすべて等しいことを確認する結果確認ステップと
を有すことを特徴とする秘密計算方法。
【請求項２１】
同一の数値に対する異なる３種類の断片の組合せを入力とし、それぞれの断片の組合せに対して計算を行う請求項１４から１７のいずれかに記載の秘密計算方法であって、
ｊを１以上３以下の整数、ｃ_１^（ｊ），ｃ_２^（ｊ），ｃ_３^（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ_２１^（ｊ），ｃ_２２^（ｊ），ｃ_２３^（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置Ｘ^（ｊ），計算装置Ｙ^（ｊ），計算装置Ｚ^（ｊ）をｊ番目の第１断片ｃ_１^（ｊ），第２断片ｃ_２^（ｊ），第３断片ｃ_３^（ｊ）を求めたときに計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能した計算装置、乱数ｒを乱数ｒ_ｘ，ｒ_ｙ，ｒ_ｚの和とし、
前記３つの計算装置は、どの計算装置も、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれとしても機能でき、
（Ｘ^（１），Ｙ^（１），Ｚ^（１））、（Ｘ^（２），Ｙ^（２），Ｚ^（２））、（Ｘ^（３），Ｙ^（３），Ｚ^（３））はそれぞれ異なり、
（ｃ_１^（１），ｃ_２^（１），ｃ_３^（１））、（ｃ_１^（２），ｃ_２^（２），ｃ_３^（２））、（ｃ_１^（３），ｃ_２^（３），ｃ_３^（３））はそれぞれ異なり、
秘匿処理過程は、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成ステップと、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配ステップと
を有する過程であり、
秘密加算過程は、
前記計算装置Ｘが、Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算ステップと、
前記計算装置Ｙが、Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算ステップと、
前記計算装置Ｚが、Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算ステップと
を有する過程であり、
復元過程は、
計算装置Ｘが、計算装置Ｙに第１断片ａ_１を送信する第１断片Ｙ送信サブステップと、
計算装置Ｙが、計算装置Ｘから第１断片ａ_１を受信する第２断片Ｘ受信サブステップと、
計算装置Ｙが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値Ａを復元する第２Ｘ復元サブステップ
からなる復元ＸＹステップ、
計算装置Ｘが、計算装置１００_Ｚに第１断片ａ_１を送信する第１断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｘから第１断片ａ_１を受信する第３断片Ｘ受信サブステップと、
計算装置Ｚが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値を復元する第３Ｘ復元サブステップと
からなる復元ＸＺステップ、
計算装置Ｙが、計算装置Ｘに第１要素ａ_２１を送信する第２断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｙから第１要素ａ_２１を受信する第１断片Ｙ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｙ復元サブステップと
からなる復元ＹＸステップ、
計算装置Ｙが、計算装置Ｚに第２要素ａ_２２を送信する第２断片Ｚ送信サブステップと、
計算装置Ｚが、計算装置Ｙから第２要素ａ_２１を受信する第３断片Ｙ受信サブステップと、
計算装置Ｚが、受信した第２要素ａ_２２と当該第２要素ａ_２２に対応する第１要素ａ_２１と第３要素ａ_２３とを加算することで数値を復元する第３Ｙ復元サブステップと
からなる復元ＹＺステップ、
計算装置Ｚが、計算装置Ｘに第１要素ａ_２１を送信する第３断片Ｘ送信サブステップと、
計算装置Ｘが、計算装置Ｚから第１要素ａ_２１を受信する第１断片Ｚ受信サブステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｚ復元サブステップと
からなる復元ＺＸステップ、
計算装置Ｚが、計算装置Ｙに第３要素ａ_２３を送信する第３断片送信サブステップと、
計算装置Ｙが、計算装置Ｚから第３要素ａ_２３を受信する第２断片受信サブステップと、
計算装置Ｙが、受信した第３要素ａ_２３と当該第３要素ａ_２３に対応する第１要素ａ_２１と第２要素ａ_２２とを加算することで数値Ａを復元する第２復元サブステップと
からなる復元ＺＹステップ
の中の少なくともいずれか１つのステップを有する過程であり、
いずれかの計算装置が、ｊ＝１とする初期化ステップと、
計算装置Ｘ^（ｊ）が、乱数ｒ_ｘを生成する第１確認乱数生成ステップと、
計算装置Ｘ^（ｊ）が、前記秘匿処理過程によって第１断片ｃ_１^（ｊ），乱数ｒ_ｘの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｘステップと、
計算装置Ｙ^（ｊ）が、乱数ｒ_ｙを生成する第２確認乱数生成ステップと、
計算装置Ｙ^（ｊ）が、前記秘匿処理過程によって第１要素ｃ_２１^（ｊ），乱数ｒ_ｙの断片を、３つの計算装置で分散して記録した状態にする秘匿Ｙステップと、
計算装置Ｚ^（ｊ）が、乱数ｒ_ｚを生成する第３確認乱数生成ステップと、
計算装置Ｚ^（ｊ）が、前記秘匿処理過程によって乱数ｒ_ｚの断片を３つの計算装置で分散して記録した状態にする秘匿Ｚステップと、
前記秘密加算過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ
ただし、ｒ＝ｒ_ｘ＋ｒ_ｙ＋ｒ_ｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする秘密加算ステップと、
前記復元ＸＹステップまたは復元ＹＸステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＹ^（ｊ）を復元して記録しておき、
前記復元ＹＺステップまたは復元ＺＹステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＹＺ^（ｊ）を復元して記録しておき、
前記復元ＸＺステップまたは復元ＺＸステップからなる前記復元過程によって、
ｃ_１^（ｊ）＋ｃ_２２^（ｊ）＋ｒ＝Ｃ_ＸＺ^（ｊ）を復元して記録しておく結果復元ステップと、
いずれかの計算装置が、ｊ＝３かを確認する条件確認ステップと、
ｊ≠３のときにはｊにｊ＋１を代入し、前記第１確認乱数生成ステップに戻る繰返ステップと、
ｊ＝３のときには、９つの復元結果Ｃ_ＸＹ^（１），Ｃ_ＹＺ^（１），Ｃ_ＸＺ^（１），Ｃ_ＸＹ^（２），Ｃ_ＹＺ^（２），Ｃ_ＸＺ^（２），Ｃ_ＸＹ^（３），Ｃ_ＹＺ^（３），Ｃ_ＸＺ^（３）がすべて等しいことを確認する結果確認ステップと
を有すことを特徴とする秘密計算方法。
【請求項２２】
３つの計算装置から構成される秘密計算システムを用いた秘密計算方法であって、
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とし、
計算装置Ｘが、２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する乱数生成ステップと、
計算装置Ｘが、乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を計算装置Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を計算装置Ｚに送信する第１演算送信ステップと、
計算装置Ｙが、計算装置Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する第２置換乱数受信ステップと、
計算装置Ｙが、Ｎビットの乱数ｅ_２１，ｅ_２２を生成し、第１要素ｅ_２１，第２要素ｅ_２２とする要素生成ステップと、
計算装置Ｙが、第１断片ａ_１が入力された場合に第１断片ｅ_１と第３要素ｅ_２３を出力する論理回路Ｃ”の入出力を乱数に置き換えたgarbled circuit ＧＣ”（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、garbled circuit ＧＣ”の出力である第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３それぞれを、第１断片ｅ_１，第３要素ｅ_２３に変換する第１断片関数ｔ_１，第３要素関数ｔ_２３を生成するgarbled circuit生成ステップと、
計算装置Ｙが、第１断片関数ｔ_１を計算装置Ｘに送信し、garbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を計算装置Ｚに送信する第２演算送信ステップと、
計算装置Ｚが、計算装置Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、計算装置Ｙからgarbled circuit ＧＣ”と第３要素関数ｔ_２３と第１要素ｅ_２１を受信する第３演算受信ステップと、
計算装置Ｚが、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ”とを用いて、第１乱数断片ｅ’_１，第３乱数要素ｅ’_２３を求める演算実行ステップと、
計算装置Ｚが、第１乱数断片ｅ’_１を計算装置Ｘに送信する第３演算送信ステップと、
計算装置Ｘが、計算装置Ｙから第１断片関数ｔ_１を受信し、計算装置Ｚから第１乱数断片ｅ’_１を受信する第１演算受信ステップと、
計算装置Ｘが、第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求める第１演算復号ステップと、
計算装置Ｙが、第２断片ｅ_２をｅ_２＝（ｅ_２１，ｅ_２２）とする第２演算復号ステップと、
計算装置Ｚが、第３要素ｅ_２３をｅ_２３＝ｔ_２３（ｅ’_２３）のように求め、第３断片ｅ_３をｅ_３＝（ｅ_２１，ｅ_２３）とする第３演算復号ステップと
を有することを特徴とする秘密計算方法。
【請求項２３】
請求項１３から１８、もしくは２２のいずれかに記載の秘密計算方法であって、
計算装置Ｘが、計算装置Ｙに第１断片ａ_１を送信する第１断片Ｙ送信ステップと、
計算装置Ｙが、計算装置Ｘから第１断片ａ_１を受信する第２断片Ｘ受信ステップと、
計算装置Ｙが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値Ａを復元する第２Ｘ復元ステップ
からなる復元ＸＹ過程、
計算装置Ｘが、計算装置１００_Ｚに第１断片ａ_１を送信する第１断片Ｚ送信ステップと、
計算装置Ｚが、計算装置Ｘから第１断片ａ_１を受信する第３断片Ｘ受信ステップと、
計算装置Ｚが、受信した第１断片ａ_１と当該第１断片ａ_１に対応する第１要素ａ_２１とを加算することで数値を復元する第３Ｘ復元ステップと
からなる復元ＸＺ過程、
計算装置Ｙが、計算装置Ｘに第１要素ａ_２１を送信する第２断片Ｘ送信ステップと、
計算装置Ｘが、計算装置Ｙから第１要素ａ_２１を受信する第１断片Ｙ受信ステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｙ復元ステップと
からなる復元ＹＸ過程、
計算装置Ｙが、計算装置Ｚに第２要素ａ_２２を送信する第２断片Ｚ送信ステップと、
計算装置Ｚが、計算装置Ｙから第２要素ａ_２１を受信する第３断片Ｙ受信ステップと、
計算装置Ｚが、受信した第２要素ａ_２２と当該第２要素ａ_２２に対応する第１要素ａ_２１と第３要素ａ_２３とを加算することで数値を復元する第３Ｙ復元ステップと
からなる復元ＹＺ過程、
計算装置Ｚが、計算装置Ｘに第１要素ａ_２１を送信する第３断片Ｘ送信ステップと、
計算装置Ｘが、計算装置Ｚから第１要素ａ_２１を受信する第１断片Ｚ受信ステップと、
計算装置Ｘが、受信した第１要素ａ_２１と当該第１要素ａ_２１に対応する第１断片ａ_１とを加算することで数値を復元する第１Ｚ復元ステップと
からなる復元ＺＸ過程、
計算装置Ｚが、計算装置Ｙに第３要素ａ_２３を送信する第３断片送信ステップと、
計算装置Ｙが、計算装置Ｚから第３要素ａ_２３を受信する第２断片受信ステップと、
計算装置Ｙが、受信した第３要素ａ_２３と当該第３要素ａ_２３に対応する第１要素ａ_２１と第２要素ａ_２２とを加算することで数値Ａを復元する第２復元ステップと
からなる復元ＺＹ過程
の中の少なくともいずれか１つの過程も有することを特徴とする秘密計算方法。
【請求項２４】
第１断片を記録する計算装置Ｘと、
第２断片を記録する計算装置Ｙと、
第３断片を記録する計算装置Ｚから構成される秘密計算システムを用いた秘密計算方法であって、
前記第１断片，第２断片，第３断片は、これらの中の２つが分かれば元の数値が復元できるものであり、
Ｎを２以上の整数、ｎを１以上Ｎ以下の整数、ａ_１，ａ_２，ａ_３をＮビット以下の数値Ａの第１断片，第２断片，第３断片、ｅ_１，ｅ_２，ｅ_３を数値Ａを論理回路Ｃに入力したときの出力Ｅ＝Ｃ（Ａ）の第１断片，第２断片，第３断片、ａ１［ｎ］を第１断片ａ_１を２進表現したときの下位ｎ桁目の値とし、
計算装置Ｘが、２Ｎ個の乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を生成する乱数生成ステップと、
計算装置Ｘが、乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を計算装置Ｙに送信し、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を計算装置Ｚに送信する第１演算送信ステップと、
計算装置Ｙが、計算装置Ｘから乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）を受信する第２置換乱数受信ステップと、
計算装置Ｙが、第１断片ａ_１が入力された場合に第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３を出力する論理回路Ｃ’の入出力を乱数に置き換えたgarbled circuit ＧＣ’（ただし、入力である第１断片ａ_１は乱数（ｒ_０，１，ｒ_１，１），…，（ｒ_０，Ｎ，ｒ_１，Ｎ）に置き換えられる）と、前記garbled circuit ＧＣ’の出力である第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３それぞれを、第１断片ｅ_１，第２断片ｅ_２，第３断片ｅ_３に変換する第１断片関数ｔ_１，第２断片関数ｔ_２，第３断片関数ｔ_３を生成するgarbled circuit生成ステップと、
計算装置Ｙが、第１断片関数ｔ_１を計算装置Ｘに送信し、garbled circuit ＧＣ’と第３断片関数ｔ_３を計算装置Ｚに送信する第２演算送信ステップと、
計算装置Ｚが、計算装置Ｘからｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}を受信し、計算装置Ｙからgarbled circuit ＧＣ’と第３断片関数ｔ_３を受信する第３演算受信ステップと、
計算装置Ｚが、ｒ_{ａ１［１］，１}，…，ｒ_{ａ１［Ｎ］，Ｎ}とgarbled circuit ＧＣ’とを用いて、第１乱数断片ｅ’_１，第２乱数断片ｅ’_２，第３乱数断片ｅ’_３を求める演算実行ステップと、
計算装置Ｚが、第１乱数断片ｅ’_１を計算装置Ｘに送信し、第２乱数断片ｅ’_２を計算装置Ｙに送信する第３演算送信ステップと、
計算装置Ｘが、計算装置Ｙから第１断片関数ｔ_１を受信し、計算装置Ｚから第１乱数断片ｅ’_１を受信する第１演算受信ステップと、
計算装置Ｘが、第１断片ｅ_１をｅ_１＝ｔ_１（ｅ’_１）のように求める第１演算復号ステップと、
計算装置Ｙが、計算装置Ｚから第２乱数断片ｅ’_２を受信する第２乱数断片受信ステップと、
計算装置Ｙが、第２断片ｅ_２をｅ_２＝ｔ_２（ｅ’_２）のように求める第２演算復号ステップと、
計算装置Ｚが、第３断片ｅ_３をｅ_３＝ｔ_３（ｅ’_３）のように求める第３演算復号ステップと
を有することを特徴とする秘密計算方法。
【請求項２５】
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録するときに、
計算装置Ｘとして機能する計算装置であって、
Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１＋ｂ_１
のように求める第１加算部と、
Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝ａ_１−ｂ_１
のように求める第１減算部と、
Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝Ｂａ_１
のように求める第１定数倍計算部と、
乱数ｒ_１，ｒ_２，ｒ_３，ｒ_４，ｒ_５を生成する乗算乱数生成部と、
Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１、第２要素ｃ_２２、第３要素ｃ_２３を
ｃ_１＝ａ_１ｂ_１−ｒ_３−r_４
ｃ_２２＝ｒ_５
ｃ_２３＝ｃ_１−ｃ_２２
のように求める第１乗算部と、
前記計算装置Ｙに（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を、前記計算装置Ｚに（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を送信する第１乗算送信部と、
１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ_２１＋ｃ_２２＋ｃ_２３）の第１断片ｃ_１を、
ｃ_１＝−ａ_１
のように求める第１否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配部と、
を備える計算装置。
【請求項２６】
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録するときに、
計算装置Ｙとして機能する計算装置であって、
Ａ＋Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１＋ｂ_２１，ａ_２２＋ｂ_２２）
のように求める第２加算部と、
Ａ−Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ａ_２１−ｂ_２１，ａ_２２−ｂ_２２）
のように求める第２減算部と、
Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（Ｂａ_２１，Ｂａ_２２）
のように求める第２定数倍計算部と、
前記計算装置Ｘから（ｒ_１，ｒ_２，ｒ_３，ｃ_２２）を受信する第２乗算乱数受信部と、
数値ｙを
ｙ＝ａ_２１ｂ_２１＋ａ_２１ｒ_２＋ｒ_１ｂ_２１＋ｒ_３
のように求める第２乗算中間値計算部と、
前記計算装置Ｚに数値ｙを送信する第２乗算送信部と、
前記計算装置Ｚから数値ｚを受信する第２乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（ｙ＋ｚ，ｃ_２２）
のように求める第２乗算部と、
１−Ａの結果である数値Ｃの第２断片ｃ_２を、
ｃ_２＝（ｃ_２１，ｃ_２２）＝（１−ａ_２１，−ａ_２２）
のように求める第２否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配部と
を備える計算装置。
【請求項２７】
数値Ａの第１断片ａ_１，第２断片ａ_２，第３断片ａ_３と、数値Ｂの第１断片ｂ_１，第２断片ｂ_２，第３断片ｂ_３は、
ａ_１＝ａ_２２＋ａ_２３
ａ_２＝（ａ_２１，ａ_２２）
ａ_３＝（ａ_２１，ａ_２３）
ｂ_１＝ｂ_２２＋ｂ_２３
ｂ_２＝（ｂ_２１，ｂ_２２）
ｂ_３＝（ｂ_２１，ｂ_２３）
ただし、第１要素ａ_２１，第２要素ａ_２２，第３要素ａ_２３はＡ＝ａ_２１＋ａ_２２＋ａ_２３を満たす任意の数値の組合せ、第１要素ｂ_２１，第２要素ｂ_２２，第３要素ｂ_２３はＢ＝ｂ_２１＋ｂ_２２＋ｂ_２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録するときに、
計算装置Ｚとして機能する計算装置であって、
Ａ＋Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１＋ｂ_２１，ａ_２３＋ｂ_２３）
のように求める第３加算部と、
Ａ−Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ａ_２１−ｂ_２１，ａ_２３−ｂ_２３）
のように求める第３減算部と、
Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（Ｂａ_２１，Ｂａ_２３）
のように求める第３定数倍計算部と、
前記計算装置Ｘから（ａ_１−ｒ_１，ｂ_１−ｒ_２，ｒ_４，ｃ_２３）を受信する第３乗算乱数受信部と、
数値ｚを
ｚ＝ａ_２１（ｂ_１−ｒ_２）＋（ａ_１−ｒ_１）ｂ_２１＋ｒ_４
のように求める第３乗算中間値計算部と、
前記計算装置Ｙに数値ｚを送信する第３乗算送信部と、
前記計算装置Ｙから数値ｙを受信する第３乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（ｙ＋ｚ，ｃ_２３）
のように求める第３乗算部と、
１−Ａの結果である数値Ｃの第３断片ｃ_３を、
ｃ_３＝（ｃ_２１，ｃ_２３）＝（１−ａ_２１，−ａ_２３）
のように求める第３否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ_２１＋ｓ_２２＋ｓ_２３
を満たすランダムな組合せである第１要素ｓ_２１，第２要素ｓ_２２，第３要素ｓ_２３と
ｓ_１＝ｓ_２２＋ｓ_２３
ｓ_２＝（ｓ_２１，ｓ_２２）
ｓ_３＝（ｓ_２１，ｓ_２３）
の関係を有する第１断片ｓ_１，第２断片ｓ_２，第３断片ｓ_３を求める断片生成部と、
計算装置Ｘとして機能する計算装置が第１断片ｓ_１を、計算装置Ｙとして機能する計算装置が第２断片ｓ_２を、計算装置Ｚとして機能する計算装置が第３断片ｓ_３を記録した状態にする断片分配部と
を備える計算装置。
【請求項２８】
請求項２５記載の計算装置と、
請求項２６記載の計算装置と、
請求項２７記載の計算装置とを有する秘密計算システムであって、
前記第１加算部、前記第２加算部、前記第３加算部で構成される秘密加算手段と、
前記第１減算部、前記第２減算部、前記第３減算部で構成される秘密減算手段と、
前記第１定数倍計算部、前記第２定数倍計算部、前記第３定数倍計算部で構成される秘密定数倍手段と、
前記乗算乱数生成部、前記第１乗算部、前記第１乗算送信部、前記第２乗算乱数受信部、前記第２乗算中間値計算部、前記第２乗算送信部、前記第２乗算中間値受信部、前記第２乗算部、前記第３乗算乱数受信部、前記第３乗算中間値計算部、前記第３乗算送信部、前記第３乗算中間値受信部、前記第３乗算部で構成される秘密乗算手段と、
前記第１否定部、前記第２否定部、前記第３否定部で構成される秘密否定手段と、
少なくとも前記計算装置Ｘの断片生成部と断片分配部と、前記計算装置Ｙの断片生成部と断片分配部とで構成される秘匿処理手段と、
を有し、
さらに、数値Ａを２進数に変換するための秘密２進変換手段も有しており、
前記秘密２進変換手段は、
（１）前記秘匿処理手段を用いて、第１断片ａ_１［１］，…，ａ_１［Ｎ］と、第１要素ａ_２１［１］，…，ａ_２１［Ｎ］を秘匿処理し、
（２）前記秘密加算手段、前記秘密乗算手段、前記秘密定数倍手段、前記秘密減算手段を用いて、
【数１１】

を行って、各前記計算装置が、Ａ［１］の断片を分散して記録した状態とし、
（３−１）ｎ＝２のように初期設定を行い、
（３−２）前記秘密定数倍手段、前記秘密加算手段、前記秘密減算手段によって、
【数１２】

を行って、各前記計算装置が、Ｂ^（ｎ）の断片ｂ_１^（ｎ），ｂ_２^（ｎ），ｂ_３^（ｎ）を分散して記録した状態とし、
（３−３）前記秘匿処理手段によって、Ｂ^（ｎ）の第１断片ｂ_１^（ｎ）とＢ^（ｎ）の第１要素ｂ_２１^（ｎ）を秘匿処理し、
（３−４）前記秘密加算手段、前記秘密乗算手段、前記秘密定数倍手段、前記秘密減算手段によって、
【数１３】

を行って、Ｄ^（ｎ）の断片ｄ_１^（ｎ），ｄ_２^（ｎ），ｄ_３^（ｎ）を分散して記録した状態にし、
（４−１）前記計算装置は、それぞれｃ_１^（ｎ）＝０、ｉ＝１のように初期設定を行い、
（４−２）前記計算装置Ｘは、
【数１４】

を計算し、前記計算装置Ｙと前記計算装置Ｚは、
【数１５】

を計算し、
（４−３）前記計算装置１００は、それぞれ
ｃ_ｉ＋１^（ｎ）＝ｃ_ｉ^（ｎ）ｂ_１^（ｎ）［ｉ］∨ｃ_ｉ^（ｎ）ｂ_２１^（ｎ）［ｉ］∨ｂ_１^（ｎ）［ｉ］ｂ_２１^（ｎ）［ｉ］
を計算し、
（４−４）前記計算装置は、ｉ＝１からｎ−１まで上記の（４−２）と（４−３）を繰返し、
（５−１）ｃ_ｎ^（ｎ）＝０ならば、各計算装置は、分散して記録しているＤ^（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とし、ｃ_ｎ^（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ^（ｎ）の否定を前記秘密否定手段で計算し、Ｄ^（ｎ）の否定の断片を、各計算装置が記録するＡ［ｎ］の断片とし、
（５−２）ｎ＝Ｎかを確認し、Ｎｏの場合には、ｎにｎ＋１を代入して上記（３−２）に戻り、Ｙｅｓの場合には処理を終了する
ことを特徴とする秘密計算システム。
【請求項２９】
請求項２５記載の計算装置と、
請求項２６記載の計算装置と、
請求項２７記載の計算装置とを用いて秘密計算を行う秘密計算方法であって、
前記第１加算部、前記第２加算部、前記第３加算部を用いて秘密加算を行う秘密加算過程と、
前記第１減算部、前記第２減算部、前記第３減算部を用いて秘密減算を行う秘密減算過程と、
前記第１定数倍計算部、前記第２定数倍計算部、前記第３定数倍計算部を用いて秘密定数倍を行う秘密定数倍過程と、
前記乗算乱数生成部、前記第１乗算部、前記第１乗算送信部、前記第２乗算乱数受信部、前記第２乗算中間値計算部、前記第２乗算送信部、前記第２乗算中間値受信部、前記第２乗算部、前記第３乗算乱数受信部、前記第３乗算中間値計算部、前記第３乗算送信部、前記第３乗算中間値受信部、前記第３乗算部を用いて秘密乗算を行う秘密乗算過程と、
前記第１否定部、前記第２否定部、前記第３否定部を用いて秘密否定を行う秘密否定過程と、
少なくとも前記計算装置Ｘの断片生成部と断片分配部と、前記計算装置Ｙの断片生成部と断片分配部を用いて秘匿処理を行う秘匿処理過程と、
を有し、
さらに、数値Ａを２進数に変換するための秘密２進変換過程も有しており、
前記秘密２進変換過程は、
（１）前記秘匿処理過程を用いて、第１断片ａ_１［１］，…，ａ_１［Ｎ］と、第１要素ａ_２１［１］，…，ａ_２１［Ｎ］を秘匿処理するステップと、
（２）前記秘密加算過程、前記秘密乗算過程、前記秘密定数倍過程、前記秘密減算過程を用いて、
【数１６】

を行って、各前記計算装置が、Ａ［１］の断片を分散して記録した状態とするステップと、
（３−１）ｎ＝２のように初期設定を行うステップと、
（３−２）前記秘密定数倍過程、前記秘密加算過程、前記秘密減算過程を用いて、
【数１７】

を行って、各前記計算装置が、Ｂ^（ｎ）の断片ｂ_１^（ｎ），ｂ_２^（ｎ），ｂ_３^（ｎ）を分散して記録した状態とするステップと、
（３−３）前記秘匿処理過程を用いて、Ｂ^（ｎ）の第１断片ｂ_１^（ｎ）とＢ^（ｎ）の第１要素ｂ_２１^（ｎ）を秘匿処理するステップと、
（３−４）前記秘密加算過程、前記秘密乗算過程、前記秘密定数倍過程、前記秘密減算過程を用いて、
【数１８】

を行って、Ｄ^（ｎ）の断片ｄ_１^（ｎ），ｄ_２^（ｎ），ｄ_３^（ｎ）を分散して記録した状態にするステップと、
（４−１）前記計算装置が、それぞれｃ_１^（ｎ）＝０、ｉ＝１のように初期設定を行うステップと、
（４−２）前記計算装置Ｘが、
【数１９】

を計算し、前記計算装置Ｙと前記計算装置Ｚが、
【数２０】

を計算するステップと、
（４−３）前記計算装置１００が、それぞれ
ｃ_ｉ＋１^（ｎ）＝ｃ_ｉ^（ｎ）ｂ_１^（ｎ）［ｉ］∨ｃ_ｉ^（ｎ）ｂ_２１^（ｎ）［ｉ］∨ｂ_１^（ｎ）［ｉ］ｂ_２１^（ｎ）［ｉ］
を計算するステップと、
（４−４）前記計算装置が、ｉ＝１からｎ−１まで上記の（４−２）と（４−３）を繰返し、
（５−１）ｃ_ｎ^（ｎ）＝０ならば、各計算装置が、分散して記録しているＤ^（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とし、ｃ_ｎ^（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ^（ｎ）の否定を前記秘密否定過程で計算し、Ｄ^（ｎ）の否定の断片を、各計算装置が記録するＡ［ｎ］の断片とするステップと、
（５−２）ｎ＝Ｎかを確認し、Ｎｏの場合には、ｎにｎ＋１を代入して上記（３−２）に戻り、Ｙｅｓの場合には処理を終了するステップと
を有することを特徴とする秘密計算方法。

【図１】