(57)【特許請求の範囲】
【請求項１】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３と、数値Ｂの第１断片ｂ１，第２断片ｂ２，第３断片ｂ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ｂ１＝ｂ２２＋ｂ２３
ｂ２＝（ｂ２１，ｂ２２）
ｂ３＝（ｂ２１，ｂ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ、第１要素ｂ２１，第２要素ｂ２２，第３要素ｂ２３はＢ＝ｂ２１＋ｂ２２＋ｂ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
秘密加算手段として、
前記計算装置Ｘが、
Ａ＋Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１を、
ｃ１＝ａ１＋ｂ１
のように求める第１加算部
を有し、
前記計算装置Ｙが、
Ａ＋Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ａ２１＋ｂ２１，ａ２２＋ｂ２２）
のように求める第２加算部
を有し、
前記計算装置Ｚが、
Ａ＋Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ａ２１＋ｂ２１，ａ２３＋ｂ２３）
のように求める第３加算部
を有す
ことを特徴とする秘密計算システム。
【請求項２】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３と、数値Ｂの第１断片ｂ１，第２断片ｂ２，第３断片ｂ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ｂ１＝ｂ２２＋ｂ２３
ｂ２＝（ｂ２１，ｂ２２）
ｂ３＝（ｂ２１，ｂ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ、第１要素ｂ２１，第２要素ｂ２２，第３要素ｂ２３はＢ＝ｂ２１＋ｂ２２＋ｂ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
Ａ−Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１を、
ｃ１＝ａ１−ｂ１
のように求める第１減算部
を有し、
前記計算装置Ｙは、
Ａ−Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ａ２１−ｂ２１，ａ２２−ｂ２２）
のように求める第２減算部
を有し、
前記計算装置Ｚは、
Ａ−Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ａ２１−ｂ２１，ａ２３−ｂ２３）
のように求める第３減算部
を有す
ことを特徴とする秘密計算システム。
【請求項３】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
Ａを数値Ｂ倍した結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１を、
ｃ１＝Ｂａ１
のように求める第１定数倍計算部
を有し、
前記計算装置Ｙは、
Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（Ｂａ２１，Ｂａ２２）
のように求める第２定数倍計算部
を有し、
前記計算装置Ｚは、
Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（Ｂａ２１，Ｂａ２３）
のように求める第３定数倍計算部
を有す
ことを特徴とする秘密計算システム。
【請求項４】
３つの計算装置から構成される秘密計算システムであって、
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３と、数値Ｂの第１断片ｂ１，第２断片ｂ２，第３断片ｂ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ｂ１＝ｂ２２＋ｂ２３
ｂ２＝（ｂ２１，ｂ２２）
ｂ３＝（ｂ２１，ｂ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ、第１要素ｂ２１，第２要素ｂ２２，第３要素ｂ２３はＢ＝ｂ２１＋ｂ２２＋ｂ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録し、
前記計算装置Ｘは、
乱数ｒ１，ｒ２，ｒ３，ｒ４，ｒ５を生成する乗算乱数生成部と、
Ａ×Ｂの結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１、第２要素ｃ２２、第３要素ｃ２３を
ｃ１＝ａ１ｂ１−ｒ３−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４
ｃ２２＝ｒ５
ｃ２３＝ｃ１−ｃ２２
のように求める第１乗算部と、
前記計算装置Ｙに（ｒ１，ｒ２，ｒ３，ｃ２２）を、前記計算装置Ｚに（ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３）を送信する第１乗算送信部と、
１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１を、
ｃ１＝−ａ１
のように求める第１否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ２１＋ｓ２２＋ｓ２３
を満たすランダムな組合せである第１要素ｓ２１，第２要素ｓ２２，第３要素ｓ２３と
ｓ１＝ｓ２２＋ｓ２３
ｓ２＝（ｓ２１，ｓ２２）
ｓ３＝（ｓ２１，ｓ２３）
の関係を有する第１断片ｓ１，第２断片ｓ２，第３断片ｓ３を求める断片生成部と、
計算装置Ｙとして機能する計算装置が第２断片ｓ２を、計算装置Ｚとして機能する計算装置が第３断片ｓ３を記録した状態にする断片分配部と、
を備える計算装置。
【請求項２６】
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３と、数値Ｂの第１断片ｂ１，第２断片ｂ２，第３断片ｂ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ｂ１＝ｂ２２＋ｂ２３
ｂ２＝（ｂ２１，ｂ２２）
ｂ３＝（ｂ２１，ｂ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ、第１要素ｂ２１，第２要素ｂ２２，第３要素ｂ２３はＢ＝ｂ２１＋ｂ２２＋ｂ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録するときに、
計算装置Ｙとして機能する計算装置であって、
Ａ＋Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ａ２１＋ｂ２１，ａ２２＋ｂ２２）
のように求める第２加算部と、
Ａ−Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ａ２１−ｂ２１，ａ２２−ｂ２２）
のように求める第２減算部と、
Ａを数値Ｂ倍した結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（Ｂａ２１，Ｂａ２２）
のように求める第２定数倍計算部と、
前記計算装置Ｘから（ｒ１，ｒ２，ｒ３，ｃ２２）を受信する第２乗算乱数受信部と、
数値ｙを
ｙ＝ａ２１ｂ２１＋ａ２１ｒ２＋ｒ１ｂ２１＋ｒ３
のように求める第２乗算中間値計算部と、
前記計算装置Ｚに数値ｙを送信する第２乗算送信部と、
前記計算装置Ｚから数値ｚを受信する第２乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ｙ＋ｚ，ｃ２２）
のように求める第２乗算部と、
１−Ａの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（１−ａ２１，−ａ２２）
のように求める第２否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ２１＋ｓ２２＋ｓ２３
を満たすランダムな組合せである第１要素ｓ２１，第２要素ｓ２２，第３要素ｓ２３と
ｓ１＝ｓ２２＋ｓ２３
ｓ２＝（ｓ２１，ｓ２２）
ｓ３＝（ｓ２１，ｓ２３）
の関係を有する第１断片ｓ１，第２断片ｓ２，第３断片ｓ３を求める断片生成部と、
計算装置Ｘとして機能する計算装置が第１断片ｓ１を、計算装置Ｚとして機能する計算装置が第３断片ｓ３を記録した状態にする断片分配部と
を備える計算装置。
【請求項２７】
数値Ａの第１断片ａ１，第２断片ａ２，第３断片ａ３と、数値Ｂの第１断片ｂ１，第２断片ｂ２，第３断片ｂ３は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
ｂ１＝ｂ２２＋ｂ２３
ｂ２＝（ｂ２１，ｂ２２）
ｂ３＝（ｂ２１，ｂ２３）
ただし、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３はＡ＝ａ２１＋ａ２２＋ａ２３を満たす任意の数値の組合せ、第１要素ｂ２１，第２要素ｂ２２，第３要素ｂ２３はＢ＝ｂ２１＋ｂ２２＋ｂ２３を満たす任意の数値の組合せ
の関係を有し、
計算装置Ｘとして機能する計算装置が第１断片を記録し、
計算装置Ｙとして機能する計算装置が第２断片を記録し、
計算装置Ｚとして機能する計算装置が第３断片を記録するときに、
計算装置Ｚとして機能する計算装置であって、
Ａ＋Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ａ２１＋ｂ２１，ａ２３＋ｂ２３）
のように求める第３加算部と、
Ａ−Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ａ２１−ｂ２１，ａ２３−ｂ２３）
のように求める第３減算部と、
Ａを数値Ｂ倍した結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（Ｂａ２１，Ｂａ２３）
のように求める第３定数倍計算部と、
前記計算装置Ｘから（ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３）を受信する第３乗算乱数受信部と、
数値ｚを
ｚ＝ａ２１（ｂ１−ｒ２）＋（ａ１−ｒ１）ｂ２１＋ｒ４
のように求める第３乗算中間値計算部と、
前記計算装置Ｙに数値ｚを送信する第３乗算送信部と、
前記計算装置Ｙから数値ｙを受信する第３乗算中間値受信部と、
Ａ×Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ｙ＋ｚ，ｃ２３）
のように求める第３乗算部と、
１−Ａの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（１−ａ２１，−ａ２３）
のように求める第３否定部と、
自己が保持する数値Ｓから
Ｓ＝ｓ２１＋ｓ２２＋ｓ２３
を満たすランダムな組合せである第１要素ｓ２１，第２要素ｓ２２，第３要素ｓ２３と
ｓ１＝ｓ２２＋ｓ２３
ｓ２＝（ｓ２１，ｓ２２）
ｓ３＝（ｓ２１，ｓ２３）
の関係を有する第１断片ｓ１，第２断片ｓ２，第３断片ｓ３を求める断片生成部と、
計算装置Ｘとして機能する計算装置が第１断片ｓ１を、計算装置Ｙとして機能する計算装置が第２断片ｓ２を、計算装置Ｚとして機能する計算装置が第３断片ｓ３を記録した状態にする断片分配部と
を備える計算装置。
【請求項２８】
請求項２５記載の計算装置と、
請求項２６記載の計算装置と、
請求項２７記載の計算装置とを有する秘密計算システムであって、
前記第１加算部、前記第２加算部、前記第３加算部で構成される秘密加算手段と、
前記第１減算部、前記第２減算部、前記第３減算部で構成される秘密減算手段と、
前記第１定数倍計算部、前記第２定数倍計算部、前記第３定数倍計算部で構成される秘密定数倍手段と、
前記乗算乱数生成部、前記第１乗算部、前記第１乗算送信部、前記第２乗算乱数受信部、前記第２乗算中間値計算部、前記第２乗算送信部、前記第２乗算中間値受信部、前記第２乗算部、前記第３乗算乱数受信部、前記第３乗算中間値計算部、前記第３乗算送信部、前記第３乗算中間値受信部、前記第３乗算部で構成される秘密乗算手段と、
前記第１否定部、前記第２否定部、前記第３否定部で構成される秘密否定手段と、
少なくとも前記計算装置Ｘの断片生成部と断片分配部と、前記計算装置Ｙの断片生成部と断片分配部とで構成される秘匿処理手段と、
を有し、
さらに、数値Ａを２進数に変換するための秘密２進変換手段も有しており、
前記秘密２進変換手段は、
（１）前記秘匿処理手段を用いて、第１断片ａ１［１］，…，ａ１［Ｎ］と、第１要素ａ２１［１］，…，ａ２１［Ｎ］を秘匿処理し、
（２）前記秘密加算手段、前記秘密乗算手段、前記秘密定数倍手段、前記秘密減算手段を用いて、
【数１１】
0005400705.tif 000012
を行って、各前記計算装置が、Ａ［１］の断片を分散して記録した状態とし、
（３−１）ｎ＝２のように初期設定を行い、
（３−２）前記秘密定数倍手段、前記秘密加算手段、前記秘密減算手段によって、
【数１２】
0005400705.tif 000013
を行って、各前記計算装置が、Ｂ（ｎ）の断片ｂ１（ｎ），ｂ２（ｎ），ｂ３（ｎ）を分散して記録した状態とし、
（３−３）前記秘匿処理手段によって、Ｂ（ｎ）の第１断片ｂ１（ｎ）とＢ（ｎ）の第１要素ｂ２１（ｎ）を秘匿処理し、
（３−４）前記秘密加算手段、前記秘密乗算手段、前記秘密定数倍手段、前記秘密減算手段によって、
【数１３】
0005400705.tif 000014
を行って、Ｄ（ｎ）の断片ｄ１（ｎ），ｄ２（ｎ），ｄ３（ｎ）を分散して記録した状態にし、
（４−１）前記計算装置は、それぞれｃ１（ｎ）＝０、ｉ＝１のように初期設定を行い、
（４−２）前記計算装置Ｘは、
【数１４】
0005400705.tif 000015
を計算し、前記計算装置Ｙと前記計算装置Ｚは、
【数１５】
0005400705.tif 000016
を計算し、
（４−３）前記計算装置１００は、それぞれ
ｃｉ＋１（ｎ）＝ｃｉ（ｎ）ｂ１（ｎ）［ｉ］∨ｃｉ（ｎ）ｂ２１（ｎ）［ｉ］∨ｂ１（ｎ）［ｉ］ｂ２１（ｎ）［ｉ］
を計算し、
（４−４）前記計算装置は、ｉ＝１からｎ−１まで上記の（４−２）と（４−３）を繰返し、
（５−１）ｃｎ（ｎ）＝０ならば、各計算装置は、分散して記録しているＤ（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とし、ｃｎ（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ（ｎ）の否定を前記秘密否定手段で計算し、Ｄ（ｎ）の否定の断片を、各計算装置が記録するＡ［ｎ］の断片とし、
（５−２）ｎ＝Ｎかを確認し、Ｎｏの場合には、ｎにｎ＋１を代入して上記（３−２）に戻り、Ｙｅｓの場合には処理を終了する
ことを特徴とする秘密計算システム。
【請求項２９】
請求項２５記載の計算装置と、
請求項２６記載の計算装置と、
請求項２７記載の計算装置とを用いて秘密計算を行う秘密計算方法であって、
前記第１加算部、前記第２加算部、前記第３加算部を用いて秘密加算を行う秘密加算過程と、
前記第１減算部、前記第２減算部、前記第３減算部を用いて秘密減算を行う秘密減算過程と、
前記第１定数倍計算部、前記第２定数倍計算部、前記第３定数倍計算部を用いて秘密定数倍を行う秘密定数倍過程と、
前記乗算乱数生成部、前記第１乗算部、前記第１乗算送信部、前記第２乗算乱数受信部、前記第２乗算中間値計算部、前記第２乗算送信部、前記第２乗算中間値受信部、前記第２乗算部、前記第３乗算乱数受信部、前記第３乗算中間値計算部、前記第３乗算送信部、前記第３乗算中間値受信部、前記第３乗算部を用いて秘密乗算を行う秘密乗算過程と、
前記第１否定部、前記第２否定部、前記第３否定部を用いて秘密否定を行う秘密否定過程と、
少なくとも前記計算装置Ｘの断片生成部と断片分配部と、前記計算装置Ｙの断片生成部と断片分配部を用いて秘匿処理を行う秘匿処理過程と、
を有し、
さらに、数値Ａを２進数に変換するための秘密２進変換過程も有しており、
前記秘密２進変換過程は、
（１）前記秘匿処理過程を用いて、第１断片ａ１［１］，…，ａ１［Ｎ］と、第１要素ａ２１［１］，…，ａ２１［Ｎ］を秘匿処理するステップと、
（２）前記秘密加算過程、前記秘密乗算過程、前記秘密定数倍過程、前記秘密減算過程を用いて、
【数１６】
0005400705.tif 000017
を行って、各前記計算装置が、Ａ［１］の断片を分散して記録した状態とするステップと、
（３−１）ｎ＝２のように初期設定を行うステップと、
（３−２）前記秘密定数倍過程、前記秘密加算過程、前記秘密減算過程を用いて、
【数１７】
0005400705.tif 000018
を行って、各前記計算装置が、Ｂ（ｎ）の断片ｂ１（ｎ），ｂ２（ｎ），ｂ３（ｎ）を分散して記録した状態とするステップと、
（３−３）前記秘匿処理過程を用いて、Ｂ（ｎ）の第１断片ｂ１（ｎ）とＢ（ｎ）の第１要素ｂ２１（ｎ）を秘匿処理するステップと、
（３−４）前記秘密加算過程、前記秘密乗算過程、前記秘密定数倍過程、前記秘密減算過程を用いて、
【数１８】
0005400705.tif 000019
を行って、Ｄ（ｎ）の断片ｄ１（ｎ），ｄ２（ｎ），ｄ３（ｎ）を分散して記録した状態にするステップと、
（４−１）前記計算装置が、それぞれｃ１（ｎ）＝０、ｉ＝１のように初期設定を行うステップと、
（４−２）前記計算装置Ｘが、
【数１９】
0005400705.tif 000020
を計算し、前記計算装置Ｙと前記計算装置Ｚが、
【数２０】
0005400705.tif 000021
を計算するステップと、
（４−３）前記計算装置１００が、それぞれ
ｃｉ＋１（ｎ）＝ｃｉ（ｎ）ｂ１（ｎ）［ｉ］∨ｃｉ（ｎ）ｂ２１（ｎ）［ｉ］∨ｂ１（ｎ）［ｉ］ｂ２１（ｎ）［ｉ］
を計算するステップと、
（４−４）前記計算装置が、ｉ＝１からｎ−１まで上記の（４−２）と（４−３）を繰返し、
（５−１）ｃｎ（ｎ）＝０ならば、各計算装置が、分散して記録しているＤ（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とし、ｃｎ（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ（ｎ）の否定を前記秘密否定過程で計算し、Ｄ（ｎ）の否定の断片を、各計算装置が記録するＡ［ｎ］の断片とするステップと、
（５−２）ｎ＝Ｎかを確認し、Ｎｏの場合には、ｎにｎ＋１を代入して上記（３−２）に戻り、Ｙｅｓの場合には処理を終了するステップと
を有することを特徴とする秘密計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関し、ある演算に対して分散された入力データを復元することなく演算結果を得るための秘密計算システム、秘密計算方法、計算装置に関する。
【背景技術】
【０００２】
ある演算に対して暗号化された入力データを復元することなく演算結果を得る方法（以降、当該方法を秘密計算方法と呼ぶ）として、例えば非特許文献１に記載された方法がある。当該方法は、暗号化手段として秘密分散法を用いる。すなわち、複数の装置がそれぞれ異なる分散データ（断片）を所持し、当該断片を一定数以上用いることでデータの復元を可能とし、さらにデータを復元することなく当該データを入力とした演算結果の断片を複数の装置が得ることも可能とする。当該方法を用いて実現可能な演算種別は算術演算（加減乗算）や論理（回路）演算である。また、当該方法は、ｎ台の装置がそれぞれ異なる断片を所持するとき、ｎ≧２ｔ−１を満たすｔ以上の数の断片を用いることでデータの復元を可能とする。
【０００３】
一方、当該方法は、整数値の断片から当該整数値を復元することなく論理演算を行い、演算結果の断片を得る方法が自明でなかったが、非特許文献２ではその解決法が提案されている。また、秘密計算方法を論理演算に用いて実行する方法として、例えば非特許文献３の方法が知られている。非特許文献３の方法は、論理回路の入出力ビットを乱数に置き換える操作により、置き換え後の演算の実行者は入出力の値を知ることなく演算結果に対応する乱数を得ることを可能とする。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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４
ｃ２２＝ｒ５
ｃ２３＝ｃ１−ｃ２２
のように求める（Ｓ１４２１）。第１乗算送信部１４３１は、計算装置１００Ｙに（ｒ１，ｒ２，ｒ３，ｃ２２）を、計算装置１００Ｚに（ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３）を送信する（Ｓ１４３１）。
【００２８】
第２乗算乱数受信部１４４２は、計算装置１００Ｘから（ｒ１，ｒ２，ｒ３，ｃ２２）を受信する（Ｓ１４４２）。第３乗算乱数受信部１４４３は、計算装置１００Ｘから（ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３）を受信する（Ｓ１４４３）。第２乗算中間値計算部１４５２は、数値ｙを
ｙ＝ａ２１ｂ２１＋ａ２１ｒ２＋ｒ１ｂ２１＋ｒ３
のように求める（Ｓ１４５２）。第３乗算中間値計算部１４５３は、数値ｚを
ｚ＝ａ２１（ｂ１−ｒ２）＋（ａ１−ｒ１）ｂ２１＋ｒ４
のように求める（Ｓ１４５３）。第２乗算送信部１４６２は、計算装置１００Ｚに数値ｙを送信する（Ｓ１４６２）。第３乗算送信部１４６３は、計算装置１００Ｙに数値ｚを送信する（Ｓ１４６３）。第２乗算中間値受信部１４７２は、計算装置１００Ｚから数値ｚを受信する（Ｓ１４７２）。第３乗算中間値受信部１４７３は、計算装置１００Ｙから数値ｙを受信する（Ｓ１４７３）。第２乗算部１４８２は、Ａ×Ｂの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（ｙ＋ｚ，ｃ２２）
のように求める（Ｓ１４８２）。第３乗算部１４８３は、Ａ×Ｂの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（ｙ＋ｚ，ｃ２３）
のように求める（Ｓ１４８３）。
【００２９】
このような処理を行えば、乗算の結果Ｃの第１断片ｃ１を第１記録部１９０１が記録し、第２断片ｃ２を第２記録部１９０２が記録し、第３断片ｃ３を第３記録部１９０３が記録した状態となる。また、計算装置１００Ｘは、他の計算装置からデータを受け取らないので、入力の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。計算装置１００Ｙは、ｒ１，ｒ２，ｒ３，ｃ２２，ｚを受信するが、これらの数値は数値Ａ，Ｂとは独立の乱数とみなせるため、数値Ａ，Ｂ，Ｃを単独で復元することはできない。計算装置１００Ｚは、ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３，ｙを受信するが、これらの数値は数値Ａ，Ｂとは独立の乱数とみなせるため、数値Ａ，Ｂ，Ｃを単独で復元することはできない。
【００３０】
＜秘密否定手段（図６，１１参照）＞
これまでの説明は、算術演算についてであったが、論理演算も可能である。まず、否定を行う手段について説明する。実施例１の秘密計算システムの秘密否定手段５０は、計算装置１００Ｘが第１否定部１５０１を有し、計算装置１００Ｙが第２否定部１５０２を有し、計算装置１００Ｚが第３否定部１５０３を有す。そして、秘密否定過程Ｓ５０は以下の処理で構成されている。第１否定部１５０１が、１−Ａの結果である数値Ｃ（ただし、Ｃ＝ｃ２１＋ｃ２２＋ｃ２３）の第１断片ｃ１を、
ｃ１＝−ａ１
のように求める（Ｓ１５０１）。第２否定部１５０２が、１−Ａの結果である数値Ｃの第２断片ｃ２を、
ｃ２＝（ｃ２１，ｃ２２）＝（１−ａ２１，−ａ２２）
のように求める（Ｓ１５０２）。第３否定部１５０３が、１−Ａの結果である数値Ｃの第３断片ｃ３を、
ｃ３＝（ｃ２１，ｃ２３）＝（１−ａ２１，−ａ２３）
のように求める（Ｓ１５０３）。
【００３１】
このような処理を行えば、否定の結果Ｃの第１断片ｃ１を第１記録部１９０１が記録し、第２断片ｃ２を第２記録部１９０２が記録し、第３断片ｃ３を第３記録部１９０３が記録した状態となる。また、互いのデータの授受がないため、いずれの計算装置も数値Ａも計算結果である数値Ｃも、単独では知ることができない。
【００３２】
＜秘密論理積手段＞
次に、論理積を行う方法について説明する。ＡとＢとの論理積（Ｃ＝Ａ∧Ｂ）は、乗算と同じなので、秘密乗算過程Ｓ４０を実行すればよい。
【００３３】
＜秘密論理和手段＞
ＡとＢの論理和（Ｃ＝Ａ∨Ｂ）は、
Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ
の演算を行えばよい。したがって、例えば、以下の処理を行えばよい。
（１）秘密加算過程Ｓ１０によってＤ１＝Ａ＋Ｂを求める。
（２）秘密乗算過程Ｓ４０によってＤ２＝ＡＢを求める。
（３）秘密減算過程Ｓ２０によってＣ＝Ｄ１−Ｄ２を求める。
【００３４】
このような処理を行えば、論理和の結果Ｃの第１断片ｃ１を計算装置１００Ｘの第１記録部１９０１が記録し、第２断片ｃ２を計算装置１００Ｙの第２記録部１９０２が記録し、第３断片ｃ３を計算装置１００Ｚの第３記録部１９０３が記録した状態となる。また、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００３５】
＜秘密排他的論理和手段＞
ＡとＢの排他的論理和は、
【００３６】
【数１】
0005400705.tif 000002
【００３７】
の演算を行えばよい。したがって、例えば、以下の処理を行えばよい。
（１）秘密加算過程Ｓ１０によってＤ１＝Ａ＋Ｂを求める。
（２）秘密乗算過程Ｓ４０によってＤ２＝ＡＢを求める。
（３）秘密定数倍過程Ｓ３０によって、Ｄ３＝２Ｄ２
（４）秘密減算過程Ｓ２０によってＣ＝Ｄ１−Ｄ３を求める。
【００３８】
このような処理を行えば、排他的論理和の結果Ｃの第１断片ｃ１を計算装置１００Ｘの第１記録部１９０１が記録し、第２断片ｃ２を計算装置１００Ｙの第２記録部１９０２が記録し、第３断片ｃ３を計算装置１００Ｚの第３記録部１９０３が記録した状態となる。また、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａ，Ｂも計算結果である数値Ｃも、単独では知ることができない。
【００３９】
＜秘匿処理手段＞
次に、いずれかの計算装置が保有している数値の３つの断片を生成し、断片を３つの計算装置で共有する処理について説明する。図１２は実施例１の秘匿処理手段の構成例を示す図、図１３は秘匿処理のフローを示す図である。図１３（Ａ）は計算装置１００Ｘとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｘ過程）を示す図であり、図１３（Ｂ）は計算装置１００Ｙとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｙ過程）を示す図であり、図１３（Ｃ）は計算装置１００Ｚとして機能する計算装置が保有する数値を秘匿処理する過程（秘匿処理Ｚ過程）を示す図である。
【００４０】
計算装置１００Ｘとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００Ｘは、断片生成部１６１１と断片分配部１６２１を備える。計算装置１００Ｙとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００Ｙは、断片生成部１６１２と断片分配部１６２２を備える。計算装置１００Ｚとして機能する計算装置が保有する数値を秘匿処理するために、計算装置１００Ｚは、断片生成部１６１３と断片分配部１６２３を備える。
【００４１】
数値Ｓをいずれかの計算装置が保有しているとする。断片生成部１６１１、１６１２、１６１３は、自己が保持する数値Ｓから
Ｓ＝ｓ２１＋ｓ２２＋ｓ２３
を満たすランダムな組合せである第１要素ｓ２１，第２要素ｓ２２，第３要素ｓ２３と
ｓ１＝ｓ２２＋ｓ２３
ｓ２＝（ｓ２１，ｓ２２）
ｓ３＝（ｓ２１，ｓ２３）
の関係を有する第１断片ｓ１，第２断片ｓ２，第３断片ｓ３を求める（Ｓ１６１１、Ｓ１６１２、Ｓ１６１３）。断片分配部１６２１、１６２２、１６２３は、計算装置Ｘとして機能する計算装置１００Ｘが第１断片ｓ１を、計算装置Ｙとして機能する計算装置１００Ｙが第２断片ｓ２を、計算装置Ｚとして機能する計算装置１００Ｚが第３断片ｓ３を記録した状態にする（Ｓ１６２１、Ｓ１６２２、Ｓ１６２３）。なお、秘匿処理手段は、秘匿処理したい数値を保有する計算装置に備えればよく、秘匿処理したい数値を保有しない計算装置には具備しなくてもよい。
【００４２】
このような処理を行えば、演算の対象となる数値の第１断片ｓ１を第１記録部１９０１が記録し、第２断片ｓ２を第２記録部１９０２が記録し、第３断片ｓ３を第３記録部１９０３が記録した状態となる。
【００４３】
＜秘密２進変換手段＞
第１の秘密２進変換手段
図１４は、図１の秘密計算システムに秘匿手段を付加した秘密計算システムの機能構成例である。図１５は、図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第１の例を示す図である。なお、図１５のフローでは、計算装置１００Ｘが保有する数値（第１断片ａ１）と計算装置１００Ｙが保有する数値（第１要素ａ２１）を秘匿処理することで、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を秘匿処理する例を示している。この例の場合、断片生成部１６１３と断片分配部１６２３は不要である。なお、数値Ａと断片ａ１と第１要素ａ２１は高々Ｎビットであるとし、Ａ［ｎ］は数値Ａの下位ｎ番目のビットを、ａ１［ｎ］は第１断片ａ１の下位ｎ番目のビットを、ａ２１［ｎ］は第１要素ａ２１の下位ｎ番目のビットをあらわす。
【００４４】
次に、数値Ａを２進表現した時の各ビットＡ［１］，…，Ａ［Ｎ］の断片を３つの計算装置で分散して記録するフローを説明する。
（１−１）計算装置１００Ｘの秘匿処理Ｘ手段６０１によって、第１断片ａ１［１］，…，ａ１［Ｎ］を秘匿処理する（Ｓ３１１）。
（１−２）計算装置１００Ｙの秘匿処理Ｙ手段６０２によって、第１要素ａ２１［１］，…，ａ２１［Ｎ］を秘匿処理する（Ｓ３１２）。
（２−１）秘密計算システムは、ｃ１＝０、ｎ＝１のように初期設定を行う（Ｓ３２１）。具体的には、いずれかの計算装置１００でＳ３２１を行えばよい。
（２−２）秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
ｄｎ＝ａ１［ｎ］＋ａ２１［ｎ］−２ａ１［ｎ］ａ２１［ｎ］
を行う（Ｓ３３０）。これは、第１断片ａ１の下位ｎ番目ａ１［ｎ］と第１要素ａ２１の下位ｎ番目ａ２１［ｎ］の排他的論理和に相当する計算である。排他的論理和の処理の詳細は、上述の秘密排他的論理和手段に示されている。
（２−３）秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
Ａ［ｎ］＝ｄｎ＋ｃｎ−２ｄｎｃｎ
を行う（Ｓ３４０）。これは、ｄｎとｃｎの排他的論理和に相当する計算である。ステップＳ３３０とＳ３４０の処理によって、
【００４５】
【数２】
0005400705.tif 000003
【００４６】
の計算結果の断片が３つの計算装置で分散されて記録された状態となる。
（２−４）次に、ステップＳ３２１を行った計算装置１００が、ｎ＝Ｎかを確認する（Ｓ３２２）。ステップＳ３２２がＹｅｓの場合には処理を終了し、Ｎｏの場合には次の処理に進む。
（２−５）ステップＳ３２２がＮｏの場合には、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密減算過程Ｓ２０によって、
ｃｎ＋１＝ａ１［ｎ］ａ２１［ｎ］＋ｄｎｃｎ−ａ１［ｎ］ａ２１［ｎ］ｄｎｃｎ
を行う（Ｓ３５０）。これは、ａ１［ｎ］ａ２１［ｎ］とｄｎｃｎとの論理和に相当する計算である。
（２−６）ステップＳ３２１を行った計算装置１００が、ｎにｎ＋１を代入し（Ｓ３２３）、ステップＳ３３０に戻る。
【００４７】
このような処理を行えば、数値Ａの下位ｎ番目のビットＡ［ｎ］の第１断片ａ１［ｎ］を計算装置１００Ｘの第１記録部１９０１が記録し、第２断片ａ２［ｎ］を計算装置１００Ｙの第２記録部１９０２が記録し、第３断片ａ３［ｎ］を計算装置１００Ｚの第３記録部１９０３が記録した状態となる。また、秘匿処理Ｘ過程Ｓ６０１と秘匿処理Ｙ過程Ｓ６０２は、第１断片ａ１［１］，…，ａ１［Ｎ］と第１要素ａ２１［１］，…，ａ１［Ｎ］を秘匿処理している。この処理では、いずれの計算装置も、数値Ａを単独では知ることができない。秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａも、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、単独では知ることができない。
【００４８】
第２の秘密２進変換手段
図１６は、図１４に示した秘密計算システムを用いた秘密２進変換過程のフローの第２の例を示す図である。なお、図１６のフローでも、計算装置１００Ｘが保有する数値（第１断片ａ１）と計算装置１００Ｙが保有する数値（第１要素ａ２１）を秘匿処理することで、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を秘匿処理する例を示している。この例の場合、断片生成部１６１３と断片分配部１６２３は不要である。なお、数値Ａと断片ａ１と第１要素ａ２１は高々Ｎビットであるとし、Ａ［ｎ］は数値Ａの下位ｎ番目のビットを、ａ１［ｎ］は第１断片ａ１の下位ｎ番目のビットを、ａ２１［ｎ］は第１要素ａ２１の下位ｎ番目のビットをあらわす。
【００４９】
次に、数値Ａを２進表現した時の各ビットＡ［１］，…，Ａ［Ｎ］の断片を３つの計算装置で分散して記録するフローを説明する。
（１−１）計算装置１００Ｘの秘匿処理Ｘ手段６０１によって、第１断片ａ１［１］，…，ａ１［Ｎ］を秘匿処理する（Ｓ３１１）。
（１−２）計算装置１００Ｙの秘匿処理Ｙ手段６０２によって、第１要素ａ２１［１］，…，ａ２１［Ｎ］を秘匿処理する（Ｓ３１２）。
（２−１）秘密計算システムは、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
【００５０】
【数３】
0005400705.tif 000004
【００５１】
を行う（Ｓ３２４）。この処理によって、各計算装置１００は、Ａ［１］の断片を分散して記録した状態となる。
（３−１）秘密計算システムは、ｎ＝２のように初期設定を行う（Ｓ３２５）。具体的には、いずれかの計算装置１００でＳ３２５を行えばよい。
（３−２）秘密計算システムは、秘密定数倍過程Ｓ３０、秘密加算過程Ｓ１０、秘密減算過程Ｓ２０によって、
【００５２】
【数４】
0005400705.tif 000005
【００５３】
を行う（Ｓ３３１）。この処理によって、各計算装置１００は、Ｂ（ｎ）の断片ｂ１（ｎ），ｂ２（ｎ），ｂ３（ｎ）を分散して記録した状態となる。
（３−３）計算装置１００Ｘの秘匿処理Ｘ手段６０１によって、Ｂ（ｎ）の第１断片ｂ１（ｎ）を秘匿処理する。また、計算装置１００Ｙの秘匿処理Ｙ手段６０２によって、Ｂ（ｎ）の第１要素ｂ２１（ｎ）を秘匿処理する（Ｓ３３２）。
（３−４）秘密計算システムは、秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０によって、
【００５４】
【数５】
0005400705.tif 000006
【００５５】
を行い、Ｄ（ｎ）の断片ｄ１（ｎ），ｄ２（ｎ），ｄ３（ｎ）を分散して記録した状態にする（Ｓ３３３）。
（４−１）各計算装置１００は、それぞれｃ１（ｎ）＝０、ｉ＝１のように初期設定を行う（Ｓ３４１）。
（４−２）計算装置Ｘとして機能する計算装置１００Ｘは、
【００５６】
【数６】
0005400705.tif 000007
【００５７】
を計算する。計算装置Ｙとして機能する計算装置１００Ｙと、計算装置Ｚとして機能する計算装置１００Ｚは、
【００５８】
【数７】
0005400705.tif 000008
【００５９】
を計算する（Ｓ３４２）。
（４−３）各計算装置１００は、それぞれ
ｃｉ＋１（ｎ）＝ｃｉ（ｎ）ｂ１（ｎ）［ｉ］∨ｃｉ（ｎ）ｂ２１（ｎ）［ｉ］∨ｂ１（ｎ）［ｉ］ｂ２１（ｎ）［ｉ］
を計算する（Ｓ３４３）。
（４−４）各計算装置１００は、それぞれｉ＝ｎ−１かを確認する（Ｓ３４４）。各計算装置１００は、ステップＳ３４４がＮｏの場合には、ｉにｉ＋１を代入し（Ｓ３４５）、ステップＳ３４２に戻る。ステップＳ３４４がＹｅｓの場合には、ステップＳ３５１に進む。
（５−１）秘密計算システムは、ｃｎ（ｎ）＝０ならば各計算装置が分散して記録しているＤ（ｎ）の断片を、各計算装置が分散して記録するＡ［ｎ］の断片とする。また、ｃｎ（ｎ）＝１ならば各計算装置が断片を分散して記録しているＤ（ｎ）の否定を秘密否定過程Ｓ５０で計算し、Ｄ（ｎ）の否定の断片を、自己が記録するＡ［ｎ］の断片とする（Ｓ３５１）。
（５−２）秘密計算システムは、ｎ＝Ｎかを確認する（Ｓ３２６）。秘密計算システムは、ステップＳ３２６がＮｏの場合には、ｎにｎ＋１を代入し（Ｓ３２７）、ステップＳ３３１に戻る。ステップＳ３２６がＹｅｓの場合には、処理を終了する。
【００６０】
なお、ステップＳ３４３で計算されるｃｉ＋１（ｎ）は、Ｂ（ｎ）＝ｂ１（ｎ）＋ｂ２１（ｎ）の加算回路における下位ｉ番目のビットの桁上げ（ｃａｒｒｙ）である。Ｂ（ｎ）は、その取り方から、
【００６１】
【数８】
0005400705.tif 000009
【００６２】
となり、Ｂ（ｎ）の最下位ビットから下位ｎ−１ビットまでは０となる。したがって、１≦ｉ≦ｎ−１では
【００６３】
【数９】
0005400705.tif 000010
【００６４】
となるので、ステップＳ３４２の式が成り立つことが分かる。また、ステップＳ３５１の計算結果は明らかにＢ（ｎ）［ｎ］の断片となっているため、Ａ［ｎ］＝Ｂ（ｎ）［ｎ］なので、Ａ［ｎ］の断片でもある。
【００６５】
このような処理を行えば、数値Ａの下位ｎ番目のビットＡ［ｎ］の第１断片ａ１［ｎ］を計算装置１００Ｘの第１記録部１９０１が記録し、第２断片ａ２［ｎ］を計算装置１００Ｙの第２記録部１９０２が記録し、第３断片ａ３［ｎ］を計算装置１００Ｚの第３記録部１９０３が記録した状態となる。また、秘匿処理Ｘ過程Ｓ６０１と秘匿処理Ｙ過程Ｓ６０２は、第１断片ａ１［１］，…，ａ１［Ｎ］と第１要素ａ２１［１］，…，ａ１［Ｎ］を秘匿処理している。この処理では、いずれの計算装置も、数値Ａを単独では知ることができない。秘密加算過程Ｓ１０、秘密乗算過程Ｓ４０、秘密定数倍過程Ｓ３０、秘密減算過程Ｓ２０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、元の数値Ａも、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、単独では知ることができない。
【００６６】
さらに、第１の秘密２進変換手段では、秘密乗算過程Ｓ４０をａ１［ｎ］ａ２１［ｎ］、ｄｎｃｎ、ａ１［ｎ］ａ２１［ｎ］ｄｎｃｎの３回実行し、これをｎ＝１からＮまでＮ回繰り返す必要がある。ただし、ｃ１＝０であり、ｎ＝Ｎのときはａ１［ｎ］ａ２１［ｎ］ｄｎｃｎの計算は不要なため、合計で３Ｎ−３回の秘密乗算過程Ｓ４０を実行する。一方、第２の秘密２進変換手段では、ａ１［ｎ］ａ２１［ｎ］および、ｎ＝２からＮまでのｂ１（ｎ）［ｎ］ｂ２１（ｎ）［ｎ］の合計Ｎ回の秘密乗算過程Ｓ４０の実行で済む。したがって、計算効率が高くなると共に、計算装置間の通信量も低減できる。
【００６７】
＜秘密整数変換手段＞
ここでは、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］の断片が３つの計算装置で分散して記録された状態から、整数表現の数値Ａの断片Ａ１，Ａ２，Ａ３が３つの計算装置に分散して記録された状態にするための手段について説明する。整数表現された数値Ａは、２進表現された数値Ａの各ビットＡ［１］，…，Ａ［Ｎ］を用いて
【００６８】
【数１０】
0005400705.tif 000011
【００６９】
のように求めることができる。したがって、秘密定数倍過程Ｓ３０の処理と秘密加算過程Ｓ１０の処理を繰り返すことで、数値Ａの第１断片Ａ［ｎ］を計算装置１００Ｘの第１記録部１９０１が記録し、第２断片Ａ２を計算装置１００Ｙの第２記録部１９０２が記録し、第３断片Ａ３を計算装置１００Ｚの第３記録部１９０３が記録した状態となる。
【００７０】
また、秘密定数倍過程Ｓ３０、秘密加算過程Ｓ１０は、上述のようにデータを秘匿した状態を維持しながら計算結果の断片を求めることができる。したがって、いずれの計算装置も、数値Ａを２進表現した各ビットＡ［１］，…，Ａ［Ｎ］も、整数表現ざれた数値Ａも、単独では知ることができない。
【００７１】
実施例１の秘密計算装置によれば、上述の秘密２進変換手段によって２進表現された数値に対して、上述の論理演算（秘密否定手段、秘密論理積手段、秘密論理和手段、秘密排他的論理和手段の処理）を行い、その結果を整数表現された数値に戻すことも可能である。しかも、これらの処理の途中の数値も、処理の結果の数値も、いずれの計算装置も単独では知ることができない。
【００７２】
＜復元手段＞
分散して記録された状態の断片から数値を復元する手段について説明する。図１７に実施例１の復元手段を計算装置に配置した構成例を示す。また、図１８に実施例１の復元手段の処理フローを示す。図１８（Ａ）の実線は、計算装置Ｘとして機能する計算装置１００Ｘが、計算装置Ｙとして機能する計算装置１００Ｙに第１断片を送り、計算装置１００Ｙが数値を復元する処理フロー（復元ＸＹ過程Ｓ７０１２）を示している。図１８（Ａ）の点線は、計算装置１００Ｘが、計算装置Ｚとして機能する計算装置１００Ｚに第１断片を送り、計算装置１００Ｚが数値を復元する処理フロー（復元ＸＺ過程Ｓ７０１３）を示している。図１８（Ｂ）の実線は、計算装置１００Ｙが計算装置１００Ｘに第２断片を送り、計算装置１００Ｘが数値を復元する処理フロー（復元ＹＸ過程Ｓ７０２１）を示している。図１８（Ｂ）の点線は、計算装置１００Ｙが計算装置１００Ｚに第２断片を送り、計算装置１００Ｚが数値を復元する処理フロー（復元ＹＺ過程Ｓ７０２３）を示している。図１８（Ｃ）の実線は、計算装置１００Ｚが計算装置１００Ｘに第３断片を送り、計算装置１００Ｘが数値を復元する処理フロー（復元ＺＸ過程Ｓ７０３１）を示している。図１８（Ｃ）の点線は、計算装置１００Ｚが計算装置１００Ｙに第３断片を送り、計算装置１００Ｙが数値を復元する処理フロー（復元ＺＹ過程Ｓ７０３２）を示している。秘密計算システムが、上記の復元処理のすべてを実行できるようにするためには、計算装置１００Ｘが、第１断片送信部１７１１、第１断片受信部１７２１、第１復元部１７３１を有し、計算装置１００Ｙが、第２断片送信部１７１２、第２断片受信部１７２２、第２復元部１７３２を有し、計算装置１００Ｚが、第３断片送信部１７１３、第３断片受信部１７２３、第３復元部１７３３を有する必要がある。なお、システムの設計上必要のない構成部は適宜省略してもよい。
【００７３】
次に、数値Ａの第１断片，第２断片，第３断片をａ１，ａ２，ａ３とし、第１要素，第２要素，第３要素をａ２１，ａ２２，ａ２３として、復元の処理フローについて説明する。なお、これまでの説明で何度も説明しているが、実施例１の秘密計算システムでは、分散して記録された断片は、
ａ１＝ａ２２＋ａ２３
ａ２＝（ａ２１，ａ２２）
ａ３＝（ａ２１，ａ２３）
Ａ＝ａ２１＋ａ２２＋ａ２３
の関係を有していることに注意されたい。
【００７４】
復元ＸＹ過程Ｓ７０１２（図１８（Ａ）実線）
第１断片送信部１７１１は、計算装置１００Ｙに第１断片ａ１を送信する（Ｓ１７１１２）。第２断片受信部１７２２は、計算装置１００Ｘから第１断片ａ１を受信する（Ｓ１７２１２）。第２復元部１７３２は、次式のように第２断片受信部１７２２が受信した第１断片ａ１と当該第１断片ａ１に対応する第１要素ａ２１とを加算することで数値Ａを復元する（Ｓ１７２１３）。
ａ１＋ａ２１＝ａ２２＋ａ２３＋ａ２１＝Ａ
【００７５】
復元ＸＺ過程Ｓ７０１３（図１８（Ａ）点線）
第１断片送信部１７１１は、計算装置１００Ｚに第１断片ａ１を送信する（Ｓ１７１１２）。第３断片受信部１７２３は、計算装置１００Ｘから第１断片ａ１を受信する（Ｓ１７２１２）。第３復元部１７３３は、次式のように第３断片受信部１７２３が受信した第１断片ａ１と当該第１断片ａ１に対応する第１要素ａ２１とを加算することで数値を復元する（Ｓ１７３１２）。
ａ１＋ａ２１＝ａ２２＋ａ２３＋ａ２１＝Ａ
【００７６】
復元ＹＸ過程Ｓ７０２１（図１８（Ｂ）実線）
第２断片送信部１７１２は、計算装置１００Ｘに第１要素ａ２１を送信する（Ｓ１７１２１）。第１断片受信部１７２１は、計算装置１００Ｙから第１要素ａ２１を受信する（Ｓ１７２２１）。第１復元部１７３１は、次式のように第１断片受信部１７２１が受信した第１要素ａ２１と当該第１要素ａ２１に対応する第１断片ａ１とを加算することで数値を復元する（Ｓ１７３２１）。
ａ２１＋ａ１＝ａ２１＋ａ２２＋ａ２３＝Ａ
【００７７】
復元ＹＺ過程Ｓ７０２３（図１８（Ｂ）点線）
第２断片送信部１７１２は、計算装置１００Ｚに第２要素ａ２２を送信する（Ｓ１７１２３）。第３断片受信部１７２３は、計算装置１００Ｙから第２要素ａ２１を受信する（Ｓ１７２２３）。第３復元部１７３３は、次式のように第３断片受信部１７２３が受信した第２要素ａ２２と当該第２要素ａ２２に対応する第１要素ａ２１と第３要素ａ２３とを加算することで数値を復元する（Ｓ１７３２３）。
ａ２２＋ａ２１＋ａ２３＝Ａ
【００７８】
復元ＺＸ過程Ｓ７０３１（図１８（Ｃ）実線）
第３断片送信部１７１３は、計算装置１００Ｘに第１要素ａ２１を送信する（Ｓ１７１３１）。第１断片受信部１７２１は、計算装置１００Ｚから第１要素ａ２１を受信する（Ｓ１７２３１）。第１復元部１７３１は、次式のように第１断片受信部１７２１が受信した第１要素ａ２１と当該第１要素ａ２１に対応する第１断片ａ１とを加算することで数値を復元する（Ｓ１７３３１）。
ａ２１＋ａ１＝ａ２１＋ａ２２＋ａ２３＝Ａ
【００７９】
復元ＺＹ過程Ｓ７０３２（図１８（Ｃ）点線）
第３断片送信部１７１３は、計算装置１００Ｙに第３要素ａ２３を送信する（Ｓ１７１３２）。第２断片受信部１７２２は、計算装置１００Ｚから第３要素ａ２３を受信する（Ｓ１７２３２）。第２復元部１７３２は、次式のように第２断片受信部１７２２が受信した第３要素ａ２３と当該第３要素ａ２３に対応する第１要素ａ２１と第２要素ａ２２とを加算することで数値Ａを復元する（Ｓ１７３３２）。
ａ２３＋ａ２１＋ａ２２＝Ａ
【００８０】
上述のように、実施例１の数値を分散して記録する方法では、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３の３つを加算できれば、元の数値Ａを復元できる。そして、いずれか２つの断片の情報が分かれば、第１要素ａ２１，第２要素ａ２２，第３要素ａ２３の和を求めることができる。したがって、上述の秘密加算手段、秘密減算手段、秘密定数倍手段、秘密乗算手段、もしくは秘密否定手段の計算結果である数値Ｃの断片は、いずれか２つの断片が分かれば、数値Ｃを復元できることが分かる。
【００８１】
＜基本処理部＞
図１９に、図１と図１２と図１７に示した計算装置１００Ｘ，１００Ｙ，１００Ｚのいずれの計算装置としても機能できる計算装置１００１（１００２，１００３）の機能構成例を示す。基本処理部１０１１（１０１２，１０１３）は、図１と図１２と図１７に示した構成部をすべで備えている。このように１つの計算装置が、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置としても機能できるようにしてもよい。この場合は、記録しているデータが第１断片から第３断片のいずれの断片かによって、その計算装置が、計算装置Ｘとして機能するか、計算装置Ｙとして機能するか、計算装置Ｚとして機能するかが決まる。もしくは、どの計算装置として機能させるかによって、秘匿処理などで渡す断片を決めればよい。このように、データごとに計算装置が発揮する機能が異なるようにすることで、より自由度の高い秘密計算システムを構築できる。
【００８２】
＜不正検出＞
次に、１つの計算装置が、計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置としても機能できるようにしたときの例として、入力された断片のデータが正しいかを確認する方法と、計算結果である断片のデータ（出力）が正しいかを確認する方法を示す。図２０は、入力と出力の不正を検出するための計算装置の機能構成例を示す図である。
【００８３】
計算装置２００１は、基本処理部１０１１の他に、入力の不正を検出するために、第１乱数ｒｘｙ共有部２４１１、第１Ｚ送信部２４２１、第１乱数ｒｘｚ共有部２３１１、第１Ｙ送信部２３２１、第１受信部２２３１、第１断片確認部２２４１、第１確認乱数生成部２５１１、Ｙ要素送信部２１１２、Ｙ要素受信部２１２２、Ｙ要素確認部２１３２、第２乱数ｒｘｙ共有部２４１２、第２Ｚ送信部２４２２、第２乱数ｒｙｚ共有部２２１２、第２Ｘ送信部２２２２、第２受信部２３３２、第２断片確認部２３４２、第２確認乱数生成部２５１２、Ｚ要素送信部２１１３、Ｚ要素受信部２１２３、Ｚ要素確認部２１３３、第３乱数ｒｘｚ共有部２３１３、第３Ｙ送信部２３２３、第３乱数ｒｙｚ共有部２２１３、第３Ｘ送信部２２２３、第３受信部２４３３、第３断片確認部２４４３、第３確認乱数生成部２５１３、復元入力確認部２５４を備える。また、計算装置２００１は、基本処理部１０１１の他に、出力の不正を検出するために、第１確認乱数生成部２５１１、第２確認乱数生成部２５１２、第３確認乱数生成部２５１３、復元出力確認部２５５を備える。したがって、入力の不正のみを検出すればよいのであれば、復元出力確認部２５５は不要であり、基本処理部１０１１中では秘匿手段と復元手段を具備していればよい。また、出力の不正のみを検出すればよいのであれば、第１確認乱数生成部２５１１、第２確認乱数生成部２５１２、第３確認乱数生成部２５１３、復元出力確認部２５５と、基本処理部１０１１中の秘匿手段と復元手段と計算に必要な手段のみを備えればよい。なお、各構成部の詳細な処理については後述する。
【００８４】
このときの秘密計算システムは、図２０に示された計算装置２００１，２００２，２００３の３つの計算装置で構成される。そして、同一の入力（数値Ａ）に対して３種類の断片を用意し、各計算装置が計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置として機能するかを変更して断片を分散して記録する。また、元の数値は同じだが断片は異なる３つの入力から、各計算装置が計算装置Ｘ，計算装置Ｙ，計算装置Ｚのいずれの計算装置として機能するかを変更して同一の計算を３回行い、計算結果である断片を分散して記録する。この説明では、ｊ（１以上３以下の整数）を計算が何回目かを示す値とし、ａ１（ｊ），ａ２（ｊ），ａ３（ｊ）を入力である数値Ａに対するｊ番目の第１断片，第２断片，第３断片、ａ２１（ｊ）をｊ番目の第１要素、ｃ１（ｊ），ｃ２（ｊ），ｃ３（ｊ）を計算結果である数値Ｃに対するｊ番目の第１断片，第２断片，第３断片、ｃ２１（ｊ），ｃ２２（ｊ），ｃ２３（ｊ）をｊ番目の第１要素，第２要素，第３要素、計算装置２００Ｘ（ｊ），計算装置２００Ｙ（ｊ），計算装置２００Ｚ（ｊ）をｊ番目の計算装置Ｘ，計算装置Ｙ，計算装置Ｚとして機能する計算装置とする。なお、それぞれの回で数値の断片や計算装置の役割が異なるので、
（ａ１（１），ａ２（１），ａ３（１））、（ａ１（２），ａ２（２），ａ３（２））、（ａ１（３），ａ２（３），ａ３（３））は互いに異なり、
（ｃ１（１），ｃ２（１），ｃ３（１））、（ｃ１（２），ｃ２（２），ｃ３（２））、（ｃ１（３），ｃ２（３），ｃ３（３））は互いに異なり、
（Ｘ（１），Ｙ（１），Ｚ（１））、（Ｘ（２），Ｙ（２），Ｚ（２））、（Ｘ（３），Ｙ（３），Ｚ（３））は互いに異なる。
【００８５】
入力された断片のデータが正しいかを確認する方法
図２１に入力の不正を検出する処理フローを示す。また、図２２は第１要素の不正を検出する処理フローを、図２３は第１断片の不正を検出する処理フローを、図２４は第２要素の不正を検出する処理フローを、図２５は第３要素の不正を検出する処理フローを示す図である。いずれかの計算装置２００１が、ｊ＝１とする（Ｓ２０１）。そして、第１要素不正検出過程Ｓ２１、第１断片不正検出過程Ｓ２２、第２要素不正検出過程Ｓ２３、第３要素不正検出過程Ｓ２４を実行する。
【００８６】
第１要素不正検出過程Ｓ２１（図２２参照）では、計算装置２００Ｙ（ｊ）が保有する第１要素ａ２１ｙ（ｊ）と計算装置２００Ｚ（ｊ）が保有する第１要素ａ２１ｚ（ｊ）とが等しいことを確認する。具体的には、計算装置２００Ｙ（ｊ）のＹ要素送信部２１１２は、計算装置２００Ｚ（ｊ）に自己が保有する第１要素ａ２１ｙ（ｊ）を送信する（Ｓ２１１２）。計算装置２００Ｚ（ｊ）のＺ要素受信部２１２３は、計算装置２００Ｙ（ｊ）から第１要素ａ２１ｙ（ｊ）を受信する（Ｓ２１２３）。計算装置２００Ｚ（ｊ）のＺ要素確認部２１３３は、自己が保有する第１要素ａ２１ｚ（ｊ）と計算装置２００Ｙ（ｊ）から受信した第１要素ａ２１ｙ（ｊ）とが等しいことを確認する（Ｓ２１３３）。計算装置２００Ｚ（ｊ）のＺ要素送信部２１１３は、計算装置２００Ｙ（ｊ）に自己が保有する第１要素ａ２１ｚ（ｊ）を送信する（Ｓ２１１３）。計算装置２００Ｙ（ｊ）のＹ要素受信部２１２２は、計算装置２００Ｚ（ｊ）から第１要素ａ２１ｚ（ｊ）を受信する（Ｓ２１２２）。計算装置２００Ｙ（ｊ）のＹ要素確認部２１３２は、自己が保有する第１要素ａ２１ｙ（ｊ）と計算装置２００Ｚ（ｊ）から受信した第１要素ａ２１ｚ（ｊ）とが等しいことを確認する（Ｓ２１３２）。ステップＳ２１２３とＳ２１３２とで等しいと確認できた場合には、計算装置２００Ｙ（ｊ）が保有する第１要素ａ２１ｙ（ｊ）と計算装置２００Ｚ（ｊ）が保有する第１要素ａ２１ｚ（ｊ）とが等しいと確認できる。一方、ステップＳ２１２３とＳ２１３２のいずれかで等しくないと判断された場合には、入力に不正があったと判断される。
【００８７】
第１断片不正検出過程Ｓ２２（図２３参照）では、第１断片ａ１（ｊ）が第２要素ａ２２（ｊ）と第３要素ａ２３（ｊ）の和であることを確認する。具体的には、計算装置２００Ｙ（ｊ）の第２乱数ｒｙｚ共有部２２１２と計算装置２００Ｚ（ｊ）の第３乱数ｒｙｚ共有部２２１３との間で乱数ｒｙｚを共有する（２２１２，２２１３）。なお、乱数ｒｙｚはどちらの計算装置が生成してもよい。計算装置２００Ｙ（ｊ）の第２Ｘ送信部２２２２は、計算装置２００Ｘ（ｊ）にｕｙ（＝ａ２２（ｊ）＋ｒｙｚ）を送信する（Ｓ２２２２）。計算装置２００Ｚ（ｊ）の第３Ｘ送信部２２２３は、計算装置２００Ｘ（ｊ）にｕｚ（＝ａ２３（ｊ）−ｒｙｚ）を送信する（Ｓ２２２３）。計算装置２００Ｘ（ｊ）の第１受信部２２３１は、計算装置２００Ｙ（ｊ）からｕｙを、計算装置２００Ｚ（ｊ）からｕｚを受信する（Ｓ２２３１）。計算装置２００Ｘ（ｊ）の第１断片確認部２２４１は、ａ１（ｊ）＝ｕｙ＋ｕｚであることを確認する（Ｓ２２４１）。ステップＳ２２４１で等しいと確認できた場合には、第１断片ａ１（ｊ）が第２要素ａ２２（ｊ）と第３要素ａ２３（ｊ）の和であることが確認できる。一方、ステップＳ２２４１で等しくないと判断された場合には、入力に不正があったと判断される。
【００８８】
第２要素不正検出過程Ｓ２３（図２４参照）では、第２要素ａ２２（ｊ）が第１断片ａ１（ｊ）と第３要素ａ２３（ｊ）の差であることを確認する。具体的には、計算装置２００Ｘ（ｊ）の第１乱数ｒｘｚ共有部２３１１と計算装置２００Ｚ（ｊ）の第３乱数ｒｘｚ共有部２３１３との間で、乱数ｒｘｚを共有する（Ｓ２３１１、Ｓ２３１３）。なお、乱数ｒｘｚはどちらの計算装置が生成してもよい。計算装置２００Ｘ（ｊ）の第１Ｙ送信部２３２１は、計算装置２００Ｙ（ｊ）にｕｘ（＝ａ１（ｊ）＋ｒｘｚ）を送信する（Ｓ２３２１）。計算装置２００Ｚ（ｊ）の第３Ｙ送信部２３２３は、計算装置２００Ｙ（ｊ）にｕｚ（＝ａ２３（ｊ）＋ｒｘｚ）を送信する（Ｓ２３２３）。計算装置２００Ｙ（ｊ）の第２受信部２３３２は、計算装置２００Ｘ（ｊ）からｕｘを、計算装置２００Ｚ（ｊ）からｕｚを受信する（Ｓ２３３２）。計算装置２００Ｙ（ｊ）の第２断片確認部２３４２は、ａ２２（ｊ）＝ｕｘ−ｕｚであることを確認する（Ｓ２３４２）。ステップＳ２３４２で等しいと確認できた場合には、第２要素ａ２２（ｊ）が第１断片ａ１（ｊ）と第３要素ａ２３（ｊ）の差であることが確認できる。一方、ステップＳ２３４２で等しくないと判断された場合には、入力に不正があったと判断される。
【００８９】
第３要素不正検出過程Ｓ２４（図２５参照）では、第３要素ａ２３（ｊ）が第１断片ａ１（ｊ）と第２要素ａ２２（ｊ）の差であることを確認する。具体的には、計算装置２００Ｘ（ｊ）の第１乱数ｒｘｙ共有部２４１１と計算装置２００Ｙ（ｊ）の第２乱数ｒｘｙ共有部２４１２との間で乱数ｒｘｙを共有する（Ｓ２４１１，Ｓ２４１２）。なお、乱数ｒｘｙはどちらの計算装置が生成してもよい。計算装置２００Ｘ（ｊ）の第１Ｚ送信部２４２１は、計算装置２００Ｚ（ｊ）にｕｘ（＝ａ１（ｊ）＋ｒｘｙ）を送信する（Ｓ２４２１）。計算装置２００Ｙ（ｊ）の第２Ｚ送信部２４２２は、計算装置２００Ｚ（ｊ）にｕｙ（＝ａ２２（ｊ）＋ｒｘｙ）を送信する（Ｓ２４２２）。計算装置２００Ｚ（ｊ）の第３受信部２４３３は、計算装置２００Ｘ（ｊ）からｕｘを、計算装置２００Ｙ（ｊ）からｕｙを受信する（Ｓ２４３３）。計算装置２００Ｚ（ｊ）の第３断片確認部２４４３は、ａ２３（ｊ）＝ｕｘ−ｕｙであることを確認する（Ｓ２４４３）。ステップＳ２４４３で等しいと確認できた場合には、第３要素ａ２３（ｊ）が第１断片ａ１（ｊ）と第２要素ａ２２（ｊ）の差であることが確認できる。一方、ステップＳ２４４３で等しくないと判断された場合には、入力に不正があったと判断される。
【００９０】
計算装置２００Ｘ（ｊ）の第１確認乱数生成部２５１１は、乱数ｒｘを生成する（Ｓ２５１１）。計算装置２００Ｘ（ｊ）の秘匿処理手段６０１は、第１断片ａ１（ｊ），乱数ｒｘの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０１）。
【００９１】
計算装置２００Ｙ（ｊ）の第２確認乱数生成部２５１２は、乱数ｒｙを生成する（Ｓ２５１２）。計算装置２００Ｙ（ｊ）の秘匿処理手段６０２は、第１要素ａ２１（ｊ），乱数ｒｙの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０２）。
【００９２】
計算装置２００Ｚ（ｊ）の第３確認乱数生成部２５１３は、乱数ｒｚを生成する（Ｓ２５１３）。計算装置２００Ｚ（ｊ）の秘匿処理手段６０３は、乱数ｒｚの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６０３）。
【００９３】
秘密加算手段１０は、
ａ１（ｊ）＋ａ２１（ｊ）＋ｒ
ただし、ｒ＝ｒｘ＋ｒｙ＋ｒｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする（Ｓ２１０）。いずれかの計算装置２００１の復元手段７０は、他の計算装置２００２または計算装置２００３から必要な情報を受け取り、
ａ１（ｊ）＋ａ２１（ｊ）＋ｒ
を復元して記録しておく（Ｓ２７０）。この処理は、ｊの値を変更しながら３回繰り替えされるが、計算装置Ｘ，Ｙ，Ｚのどの計算装置として機能しているかに関わらず、同じ計算装置がおこなえばよい。なお、この復元を行う計算装置は、ステップＳ２０１を行った計算装置（ｊの値を管理している計算装置）とすればよい。そして、その計算装置が、計算装置Ｘ，Ｙ，Ｚのどの計算装置として機能しているかによって、適宜復元手段を選択すればよい。ステップＳ２０１を行った計算装置（ｊの値を管理している計算装置）は、ｊ＝３かを確認し（Ｓ２０２）、Ｎｏの場合にはｊにｊ＋１を代入し（Ｓ２０３）ステップＳ２１〜Ｓ２４に戻る。ステップＳ２０２がＹｅｓの場合には、３つの復元結果ａ１（１）＋ａ２１（１）＋ｒ，ａ１（２）＋ａ２１（２）＋ｒ，ａ１（３）＋ａ２１（３）＋ｒを取得できるいずれかの計算装置（つまり、Ｓ２７０を３回行った計算装置）が、復元入力確認部２５４で、３つの結果が等しいことを確認する（Ｓ２５４）。
【００９４】
計算結果である断片のデータが正しいかを確認する方法
図２６に出力の不正を検出する処理フローを示す。いずれかの計算装置２００１が、ｊ＝１とする（Ｓ２８１）。次に、所定の計算を行う（Ｓ２８５）。所定の計算とは、この秘密計算システムを用いて行う計算と同じにすればよく、加算、乗算、論理演算などのいずれかでも、いくつかの組合せでもかまわない。
【００９５】
計算装置２００Ｘ（ｊ）の第１確認乱数生成部２５１１は、乱数ｒｘを生成する（Ｓ２５１１）。計算装置２００Ｘ（ｊ）の秘匿処理手段６０１は、第１断片ｃ１（ｊ），乱数ｒｘの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６５１）。
【００９６】
計算装置２００Ｙ（ｊ）の第２確認乱数生成部２５１２は、乱数ｒｙを生成する（Ｓ２５１２）。計算装置２００Ｙ（ｊ）の秘匿処理手段６０２は、第１要素ｃ２１（ｊ），乱数ｒｙの断片を、３つの計算装置で分散して記録した状態にする（Ｓ２６５２）。
【００９７】
計算装置２００Ｚ（ｊ）の第３確認乱数生成部２５１３は、乱数ｒｚを生成する（Ｓ２５１３）。計算装置２００Ｚ（ｊ）の秘匿処理手段６０３は、乱数ｒｚの断片を３つの計算装置で分散して記録した状態にする（Ｓ２６５３）。
【００９８】
秘密加算手段は
ｃ１（ｊ）＋ｃ２２（ｊ）＋ｒ
ただし、ｒ＝ｒｘ＋ｒｙ＋ｒｚ
の計算結果の断片を、３つの計算装置で分散して記録した状態にする（Ｓ２１５）。計算装置２００Ｘ（ｊ）と計算装置２００Ｙ（ｊ）の一方は、他方から必要な情報を受け取り、ｃ１（ｊ）＋ｃ２２（ｊ）＋ｒ＝ＣＸＹ（ｊ）を復元して記録しておく（Ｓ２７１）。計算装置２００Ｙ（ｊ）と計算装置２００Ｚ（ｊ）の一方は、他方から必要な情報を受け取り、ｃ１（ｊ）＋ｃ２２（ｊ）＋ｒ＝ＣＹＺ（ｊ）を復元して記録しておく（Ｓ２７２）。計算装置２００Ｘ（ｊ）と計算装置２００Ｚ（ｊ）の一方は、他方から必要な情報を受け取り、ｃ１（ｊ）＋ｃ２２（ｊ）＋ｒ＝ＣＸＺ（ｊ）を復元して記録しておく（Ｓ２７３）。ステップＳ２８１を行った計算装置（ｊの値を管理している計算装置）は、ｊ＝３かを確認し（Ｓ２８２）、Ｎｏの場合にはｊにｊ＋１を代入し（Ｓ２８３）ステップＳ２８５に戻る。ステップＳ２８２がＹｅｓの場合には、９つの復元結果ＣＸＹ（１），ＣＹＺ（１），ＣＸＺ（１），ＣＸＹ（２），ＣＹＺ（２），ＣＸＺ（２），ＣＸＹ（３），ＣＹＺ（３），ＣＸＺ（３）を取得できるいずれかの計算装置（１つの計算装置では不可能なので、他の計算装置から復元結果を受信できる計算装置）が、復元結果ＣＸＹ（１），ＣＹＺ（１），ＣＸＺ（１），ＣＸＹ（２），ＣＹＺ（２），ＣＸＺ（２），ＣＸＹ（３），ＣＹＺ（３），ＣＸＺ（３）がすべて等しいことを確認する（Ｓ２５５）。なお、すべての計算装置が復元結果を出力し、外部の計算装置で確認してもよい。
【００９９】
出力の不正が確認できる理由
計算結果を改ざんする不正は、
Ａ．入力の分散データを不正値とする、
Ｂ．乗算または２進変換処理の秘匿処理の手続きで他の計算装置に不正値を送信する、
Ｃ．復元処理で不正値を開示する
の何れかに帰着されることに着目する。なお、図２１の処理において何れかの計算装置が手続きを偽った場合は、不正Ａの検出ができなくなるが、その場合は不正ＢまたはＣの問題に帰着される。
【０１００】
次に、不正Ｂは１／２λ以下の確率を除き図２６の処理で不正検出されることを示す。ただし、λは適当な整数である。不正Ａは各計算装置が図２１の処理を正しく行えば防ぐことができる。不正Ｃは図２６の処理によって防ぐことができる。したがって以下では不正Ｂについて考える。２進変換処理の秘匿処理で他の計算装置に不正値を送信する場合は、各計算装置が図２１の処理を正しく行えば図２１の処理で検出され、そうでない場合は、次段以降の乗算または２進変換処理の秘匿処理で他の計算装置に不正値を送信することに帰着される。次段以降に乗算および２進変換処理の秘匿処理が無い場合は不正Ｃの問題に帰着される。
【０１０１】
次に、乗算の処理で他の計算装置に不正値を送信する場合を考える。各計算装置は乗算ｃ＝ａｂにおいて計算装置Ｘの処理を行う際、計算装置Ｙ，Ｚにそれぞれ（ｒ１，ｒ２，ｒ３，ｃ２２），（ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３）を送信する。ｒ１，ｒ２，ｒ３，ｃ２２は乱数だから、ａ１−ｒ１，ｂ１−ｒ２，ｒ４，ｃ２３をそれぞれａ〜、ｂ〜、ｃ２３〜に置き換えたとき、計算装置Ｚが得る乗算結果の分散データはｃ３〜＝（ｃ２１〜，ｃ２３〜）＝（ｙ＋ａ２１ｂ〜＋ａ〜ｂ２１＋ｒ４，ｃ２３〜）となる。すなわち、（ｃ２１−ｃ２１〜，ｃ２３−ｃ２３〜）＝（ａ２１（ｂ１−ｒ２−ｂ〜）＋（ａ１−ｒ１−ａ〜）ｂ２１，ｃ２３−ｃ２３〜）の差分が生じる。しかし計算装置Ｘはａ２１，ｂ２１，ｃ２３を知らないため、この差分をもう２回の乗算ｃ＝ａｂの実行時の計算装置Ｚの分散データに付加することができず、図２６の処理で不正検出されない確率は高々１／２λとなる。
【０１０２】
最後に、実施例１の基本処理部と不正検出について、情報理論的安全性に基づく既存方式との比較を行う。非特許文献１では算術演算および論理回路演算を独立に実行することができ、非特許文献２の２進変換処理によってそれらを組み合わせた計算が可能となる。算術演算および論理回路演算は既存方式も本発明の提案方式もともにＯ（λ）の計算量となる。乗算のときのみ、Ｏ（１）の通信回数とＯ（λ）の通信量を必要とするが、実施例１の方式は乗算の計算がより単純となる。また、非特許文献１では、不正検出のために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生成部
５４２、７４２  第２演算送信部            ７５２  第２乱数断片受信部
５６２、７６２  第２演算復号部            ５１３、７１３  第３演算受信部
５２３、７２３  演算実行部                ５３３、７３３  第３演算送信部
５４３、７４３  第３演算復号部
【図１】
0005400705.tif 000022
【図２】
0005400705.tif 000023
【図３】
0005400705.tif 000024
【図４】
0005400705.tif 000025
【図５】
0005400705.tif 000026
【図６】
0005400705.tif 000027
【図７】
0005400705.tif 000028
【図８】
0005400705.tif 000029
【図９】
0005400705.tif 000030
【図１０】
0005400705.tif 000031
【図１１】
0005400705.tif 000032
【図１２】
0005400705.tif 000033
【図１３】
0005400705.tif 000034
【図１４】
0005400705.tif 000035
【図１５】
0005400705.tif 000036
【図１６】
0005400705.tif 000037
【図１７】
0005400705.tif 000038
【図１８】
0005400705.tif 000039
【図１９】
0005400705.tif 000040
【図２０】
0005400705.tif 000041
【図２１】
0005400705.tif 000042
【図２２】
0005400705.tif 000043
【図２３】
0005400705.tif 000044
【図２４】
0005400705.tif 000045
【図２５】
0005400705.tif 000046
【図２６】
0005400705.tif 000047
【図２７】
0005400705.tif 000048
【図２８】
0005400705.tif 000049
【図２９】
0005400705.tif 000050
【図３０】
0005400705.tif 000051