(57)【要約】  本発明の秘密分散システムは、Ｎ個の秘密分散装置で構成される。本発明の秘密分散システムは、断片置換手段と再分散手段を備える。断片置換手段は、Ｎ未満の数の秘密分散装置を選択し、選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置が記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（ただし、ｉは選択された秘密分散装置を示す番号）。再分散手段は、断片置換手段によって置換された数値に対応する断片を用いて再分散化して新しい断片を求める。
2012046692.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個の秘密分散装置で構成された秘密分散システムであって、
Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ（１），…，Ａｋ（Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ（ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ（ｍ）の断片、ｉをＮ個の秘密分散装置の中から選択された秘密分散装置を示すための１以上Ｎ以下の中の一部の整数とし、
２以上Ｎ未満の数の秘密分散装置を選択する選択手段と、
前記選択手段で選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択されたｉ番目の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする断片置換手段と、
前記断片置換手段によって置換された数値Ａπ（ｋ）（１），…，Ａπ（ｋ）（Ｍ）に対応する断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）を用いて再分散化して新しい断片ｂｋ１（１），…，ｂｋＮ（１），…，ｂｋ１（Ｍ），…，ｂｋＮ（Ｍ）を求め、数値Ｂｋ（１），…，Ｂｋ（Ｍ）の断片とする再分散手段と、
を備える秘密分散システム。
【請求項２】
請求項１記載の秘密分散システムであって、
Ｍ＝１である秘密分散システム。
【請求項３】
請求項２記載の秘密分散システムであって、
Ｎ個の秘密分散装置のどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片を秘密計算によって求め、ｎ番目の秘密分散装置に断片ｐ１ｎ，…，ｐＫｎを記録する初期情報分散手段と、
Ｎ個の秘密分散装置で、Ｓｋ＝Ｐｋ×Ａｋ（１）である数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する初期乗算手段と、
ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、Ｎ個の秘密分散装置に分散して記録する確認分散手段と、
Ｎ個の秘密分散装置で、Ｔｋ＝Ｑｋ×Ｂｋ（１）である数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する確認乗算手段と、
ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する改ざん検出手段、
も備える秘密分散システム。
【請求項４】
請求項１記載の秘密分散システムであって、
Ｎ＝３、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａｋ（ｍ）＝ａｋαβ（ｍ）＋ａｋβγ（ｍ）＋ａｋγα（ｍ）の３つの断片を（ａｋγα（ｍ），ａｋαβ（ｍ））と（ａｋαβ（ｍ），ａｋβγ（ｍ））と（ａｋβγ（ｍ），ａｋγα（ｍ））、前記の３つの断片は３つの秘密分散装置に分散して記録されているとし、
前記選択手段は、２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置とし、
前記断片置換手段は、第１の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ１（ｍ）＝（ａｋ３１（ｍ），ａｋ１２（ｍ））、第２の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ２（ｍ）＝（ａｋ１２（ｍ），ａｋ２３（ｍ））、第３の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ３（ｍ）＝（ａｋ２３（ｍ），ａｋ３１（ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）１（１），…，ａπ（ｋ）１（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）２（１），…，ａπ（ｋ）２（Ｍ）を対応付けられたｋ番目の数値群の断片にし、
前記再分散手段として、各秘密分散装置が、
第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１（１），…，ｂｋ３１（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３（１），…，ｂｋ２３（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘｋ（ｍ）＝ｂｋ３１（ｍ）−ａπ（ｋ）３１（ｍ）を計算し、ｘｋ（１），…，ｘｋ（Ｍ）を第２の秘密分散装置に送信する第１計算部と、
第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙｋ（ｍ）＝ｂｋ２３（ｍ）−ａπ（ｋ）２３（ｍ）を計算し、ｙｋ（１），…，ｙｋ（Ｍ）を第１の秘密分散装置に送信する第２計算部と、
第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂｋ１２（ｍ）＝ａπ（ｋ）１２（ｍ）−ｘｋ（ｍ）−ｙｋ（ｍ）を計算する第３計算部と、
第１の秘密分散装置のときには（ｂｋ３１（ｍ），ｂｋ１２（ｍ））を断片ｂｋ１（ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２（ｍ），ｂｋ２３（ｍ））を断片ｂｋ２（ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３（ｍ），ｂｋ３１（ｍ））を断片ｂｋ３（ｍ）とする断片更新部と、
を備え、断片ｂｋ１（ｍ）、ｂｋ２（ｍ）、ｂｋ３（ｍ）を数値Ｂｋ（ｍ）の断片として記録する
秘密分散システム。
【請求項５】
請求項４記載の秘密分散システムであって、
Ｍ＝１である秘密分散システム。
【請求項６】
請求項５記載の秘密分散システムであって、
第１の秘密分散装置でＫ個のランダムな値Ｒ（１）１，…，Ｒ（１）Ｋを生成し、第２の秘密分散装置でＫ個のランダムな値Ｒ（２）１，…，Ｒ（２）Ｋを生成し、前記３つの秘密分散装置で、Ｒ（１）ｋの断片（ｒ（１）ｋ３１，ｒ（１）ｋ１２）、（ｒ（１）ｋ１２，ｒ（１）ｋ２３）、（ｒ（１）ｋ２３，ｒ（１）ｋ３１）と、Ｒ（２）ｋの断片（ｒ（２）ｋ３１，ｒ（２）ｋ１２）、（ｒ（２）ｋ１２，ｒ（２）ｋ２３）、（ｒ（２）ｋ２３，ｒ（２）ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置で、Ｐｋ＝Ｒ（１）ｋ＋Ｒ（２）ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散手段と、
前記３つの秘密分散装置で、Ｓｋ＝Ｐｋ×Ａｋ（１）である数値Ｓｋの断片（ｓｋ３１，ｓｋ１２）、（ｓｋ１２，ｓｋ２３）、（ｓｋ２３，ｓｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算手段と、
前記の数値Ｒ（１）π（ｋ）の別の断片（ｒ’（１）π（ｋ）３１，ｒ’（１）π（ｋ）１２）、（ｒ’（１）π（ｋ）１２，ｒ’（１）π（ｋ）２３）、（ｒ’（１）π（ｋ）２３，ｒ’（１）π（ｋ）３１）と、前記の数値Ｒ（２）π（ｋ）の別の断片（ｒ’（２）π（ｋ）３１，ｒ’（２）π（ｋ）１２）、（ｒ’（２）π（ｋ）１２，ｒ’（２）π（ｋ）２３）、（ｒ’（２）π（ｋ）２３，ｒ’（２）π（ｋ）３１）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑｋ＝Ｒ（１）π（ｋ）＋Ｒ（２）π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散手段と、
前記３つの秘密分散装置で、Ｔｋ＝Ｑｋ×Ｂｋ（１）である数値Ｔｋの断片（ｔｋ３１，ｔｋ１２）、（ｔｋ１２，ｔｋ２３）、（ｔｋ２３，ｔｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算手段と、
第１の秘密分散装置が記録する断片をｓｋ１＝（ｓｋ３１，ｓｋ１２）、ｔｋ１＝（ｔｋ３１，ｔｋ１２）とし、第２の秘密分散装置が記録する断片をｓｋ２＝（ｓｋ１２，ｓｋ２３）、ｔｋ２＝（ｔｋ１２，ｔｋ２３）とし、第３の秘密分散装置が記録する断片をｓｋ３＝（ｓｋ２３，ｓｋ３１）、ｔｋ３＝（ｔｋ２３，ｔｋ３１）とし、
各秘密分散装置が、
第１の秘密分散装置のときに、ランダムな値であるｕｋを生成し、第２の秘密分散装置に送信する第３乱数生成部と、
第２の秘密分散装置のときに、ランダムな値であるｖｋを生成し、第１の秘密分散装置に送信する第４乱数生成部と、
第１の秘密分散装置のときに、ｄｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置に送信する第４計算部と、
第２の秘密分散装置のときに、ｅｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置に送信する第５計算部と、
第３の秘密分散装置のときに、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する第１確認部と、
第１の秘密分散装置のときに、ｆｋ＝ｓπ（ｋ）３１−ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置に送信する第６計算部と、
第２の秘密分散装置のときに、ｇｋ＝ｓπ（ｋ）２３−ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置に送信する第７計算部と、
第３の秘密分散装置のときに、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する第２確認部と、
を備える
秘密分散システム。
【請求項７】
請求項４記載の秘密分散システムの中の秘密分散装置であって、
第１の秘密分散装置として選ばれたときには記録する数値Ａｋ（ｍ）の断片をａｋ１（ｍ）＝（ａｋ３１（ｍ），ａｋ１２（ｍ））、第２の秘密分散装置として選ばれたときには記録する数値Ａｋ（ｍ）の断片をａｋ２（ｍ）＝（ａｋ１２（ｍ），ａｋ２３（ｍ））、第３の秘密分散装置として選ばれたときには記録する数値Ａｋ（ｍ）の断片をａｋ３（ｍ）＝（ａｋ２３（ｍ），ａｋ３１（ｍ））とし、
第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、対応付けられたπ（ｋ）番目の数値群の断片を対応付けられたｋ番目の数値群の断片にする断片置換部と、
第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１（１），…，ｂｋ３１（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３（１），…，ｂｋ２３（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘｋ（ｍ）＝ｂｋ３１（ｍ）−ａπ（ｋ）３１（ｍ）を計算し、ｘｋ（１），…，ｘｋ（Ｍ）を第２の秘密分散装置に送信する第１計算部と、
第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙｋ（ｍ）＝ｂｋ２３（ｍ）−ａπ（ｋ）２３（ｍ）を計算し、ｙｋ（１），…，ｙｋ（Ｍ）を第１の秘密分散装置に送信する第２計算部と、
第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂｋ１２（ｍ）＝ａπ（ｋ）１２（ｍ）−ｘｋ（ｍ）−ｙｋ（ｍ）を計算する第３計算部と、
第１の秘密分散装置のときには（ｂｋ３１（ｍ），ｂｋ１２（ｍ））を断片ｂｋ１（ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２（ｍ），ｂｋ２３（ｍ））を断片ｂｋ２（ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３（ｍ），ｂｋ３１（ｍ））を断片ｂｋ３（ｍ）とする断片更新部と、
を備える秘密分散装置。
【請求項８】
請求項７記載の秘密分散装置であって、
Ｍ＝１である秘密分散装置。
【請求項９】
Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、Ｍを１以上の整数、ｍを１以上Ｍ以下の整数、Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）をＫ×Ｍ個の数値、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａｋ（ｍ）＝ａｋαβ（ｍ）＋ａｋβγ（ｍ）＋ａｋγα（ｍ）の３つの断片を（ａｋγα（ｍ），ａｋαβ（ｍ））と（ａｋαβ（ｍ），ａｋβγ（ｍ））と（ａｋβγ（ｍ），ａｋγα（ｍ））、対応付けられたｋ番目の数値群をＡｋ（１），…，Ａｋ（Ｍ）とし、前記断片を分散して記録する３つの秘密分散装置を用いた秘密分散方法であって、
２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置する選択ステップと、
第１の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ１（ｍ）＝（ａｋ３１（ｍ），ａｋ１２（ｍ））、第２の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ２（ｍ）＝（ａｋ１２（ｍ），ａｋ２３（ｍ））、第３の秘密分散装置が記録する数値Ａｋ（ｍ）の断片をａｋ３（ｍ）＝（ａｋ２３（ｍ），ａｋ３１（ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）１（１），…，ａπ（ｋ）１（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）２（１），…，ａπ（ｋ）２（Ｍ）を対応付けられたｋ番目の数値群の断片にする断片置換ステップと、
第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１（１），…，ｂｋ３１（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成ステップと、
第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３（１），…，ｂｋ２３（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成ステップと、
第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘｋ（ｍ）＝ｂｋ３１（ｍ）−ａπ（ｋ）３１（ｍ）を計算し、ｘｋ（１），…，ｘｋ（Ｍ）を第２の秘密分散装置に送信する第１計算ステップと、
第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙｋ（ｍ）＝ｂｋ２３（ｍ）−ａπ（ｋ）２３（ｍ）を計算し、ｙｋ（１），…，ｙｋ（Ｍ）を第１の秘密分散装置に送信する第２計算ステップと、
第１の秘密分散装置と第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂｋ１２（ｍ）＝ａπ（ｋ）１２（ｍ）−ｘｋ（ｍ）−ｙｋ（ｍ）を計算する第３計算ステップと、
第１の秘密分散装置が（ｂｋ３１（ｍ），ｂｋ１２（ｍ））を断片ｂｋ１（ｍ）とし、第２の秘密分散装置が（ｂｋ１２（ｍ），ｂｋ２３（ｍ））を断片ｂｋ２（ｍ）とし、第３の秘密分散装置が（ｂｋ２３（ｍ），ｂｋ３１（ｍ））を断片ｂｋ３（ｍ）とする断片更新ステップと、
を有する秘密分散方法。
【請求項１０】
請求項９記載の秘密分散方法であって、
Ｍ＝１である秘密分散方法。
【請求項１１】
請求項１０記載の秘密分散方法であって、
第１の秘密分散装置がＫ個のランダムな値Ｒ（１）１，…，Ｒ（１）Ｋを生成し、第２の秘密分散装置がＫ個のランダムな値Ｒ（２）１，…，Ｒ（２）Ｋを生成し、前記３つの秘密分散装置がＲ（１）ｋの断片（ｒ（１）ｋ３１，ｒ（１）ｋ１２）、（ｒ（１）ｋ１２，ｒ（１）ｋ２３）、（ｒ（１）ｋ２３，ｒ（１）ｋ３１）とＲ（２）ｋの断片（ｒ（２）ｋ３１，ｒ（２）ｋ１２）、（ｒ（２）ｋ１２，ｒ（２）ｋ２３）、（ｒ（２）ｋ２３，ｒ（２）ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置がＰｋ＝Ｒ（１）ｋ＋Ｒ（２）ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散ステップと、
前記３つの秘密分散装置が、Ｓｋ＝Ｐｋ×Ａｋ（１）である数値Ｓｋの断片（ｓｋ３１，ｓｋ１２）、（ｓｋ１２，ｓｋ２３）、（ｓｋ２３，ｓｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算ステップと、
前記３つの秘密分散装置が、請求項１０記載の秘密分散システムによって得られた断片ｂｋ１、ｂｋ２、ｂｋ３を数値Ｂｋ（１）の断片として記録する秘密分散更新ステップと、
前記の数値Ｒ（１）π（ｋ）の別の断片（ｒ’（１）π（ｋ）３１，ｒ’（１）π（ｋ）１２）、（ｒ’（１）π（ｋ）１２，ｒ’（１）π（ｋ）２３）、（ｒ’（１）π（ｋ）２３，ｒ’（１）π（ｋ）３１）と、前記の数値Ｒ（２）π（ｋ）の別の断片（ｒ’（２）π（ｋ）３１，ｒ’（２）π（ｋ）１２）、（ｒ’（２）π（ｋ）１２，ｒ’（２）π（ｋ）２３）、（ｒ’（２）π（ｋ）２３，ｒ’（２）π（ｋ）３１）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑｋ＝Ｒ（１）π（ｋ）＋Ｒ（２）π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散ステップと、
前記３つの秘密分散装置が、Ｔｋ＝Ｑｋ×Ｂｋ（１）である数値Ｔｋの断片（ｔｋ３１，ｔｋ１２）、（ｔｋ１２，ｔｋ２３）、（ｔｋ２３，ｔｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算ステップと、
第１の秘密分散装置が記録する断片をｓｋ１＝（ｓｋ３１，ｓｋ１２）、ｔｋ１＝（ｔｋ３１，ｔｋ１２）とし、第２の秘密分散装置が記録する断片をｓｋ２＝（ｓｋ１２，ｓｋ２３）、ｔｋ２＝（ｔｋ１２，ｔｋ２３）とし、第３の秘密分散装置が記録する断片をｓｋ３＝（ｓｋ２３，ｓｋ３１）、ｔｋ３＝（ｔｋ２３，ｔｋ３１）とし、
第１の秘密分散装置が、ランダムな値であるｕｋを生成し、第２の秘密分散装置に送信する第３乱数生成ステップと、
第２の秘密分散装置が、ランダムな値であるｖｋを生成し、第１の秘密分散装置に送信する第４乱数生成ステップと、
第１の秘密分散装置が、ｄｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置に送信する第４計算ステップと、
第２の秘密分散装置が、ｅｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置に送信する第５計算ステップと、
第３の秘密分散装置が、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する第１確認ステップと、
第１の秘密分散装置が、ｆｋ＝ｓπ（ｋ）３１−ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置に送信する第６計算ステップと、
第２の秘密分散装置が、ｇｋ＝ｓπ（ｋ）２３−ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置に送信する第７計算ステップと、
第３の秘密分散装置が、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する第２確認ステップと、
を有する秘密分散方法。
【請求項１２】
請求項９から１１のいずれかに記載の秘密分散方法であって、
前記断片更新ステップで得られた断片ｂｋ１（ｍ）、ｂｋ２（ｍ）、ｂｋ３（ｍ）を新しい断片ａｋ１（ｍ）、ａｋ２（ｍ）、ａｋ３（ｍ）とし、
前記断片置換ステップで、あらかじめ定めた全ての組合せで前記秘密分散装置を選択するまで、前記の秘密分散方法を繰り返す
ことを特徴とする秘密分散方法。
【請求項１３】
請求項１２記載の秘密分散方法を用いた秘密ソート方法であって、
請求項１２記載の秘密分散方法によって断片を分散して記録した複数の数値に対して、
３つの秘密分散装置が、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する比較ステップと、
秘密分散装置のそれぞれが、前記比較ステップの結果に基づいて数値の断片を入れ替える交換ステップと、
を有する秘密ソート方法。
【請求項１４】
請求項１から６のいずれかに記載の秘密分散システムの各秘密分散装置としてコンピュータを機能させる秘密分散プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラムに関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある(例えば、非特許文献１に記載された方法)。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させ、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算(否定，論理積，論理和，排他的論理和)、データ形式変換(整数,二進数)の結果を３つの秘密計算装置に分散保持させることができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司，五十嵐大，高橋克巳，“効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察”，第48回情報処理学会研究報告，CSEC, pp.1-7, 2010，3月.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術はデータの対応を隠したまま複数のデータをランダムに置換できないという課題がある。本発明の目的は、入力された複数のデータと対応つけることができないデータを出力する秘密計算技術を提供することである。
【課題を解決するための手段】
【０００５】
本発明は秘密分散に関する。一般に、（ｋ，ｎ）−秘密分散では、秘密分散システムが２つのパラメータｋ，ｎを持っており、秘密にしたい値をｎ個に分割し、そのうちｋ個未満を集めても元の値に関する情報は漏れないが、ｋ個以上を集めると元の値を復元できる。本発明の秘密分散システムは、Ｎ個の秘密分散装置Ｒ１，…，ＲＮで構成される。ここで、Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ（１），…，Ａｋ（Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ（ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ（ｍ）の断片とする。本発明の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。選択手段は、２以上Ｎ未満の数の秘密分散装置を選択する。断片置換手段は、選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置Ｒｉ（ただし、ｉは選択された秘密分散装置を示す番号）が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）（１），…，Ａπ（ｋ）（Ｍ）に対応する断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）を用いて再分散化して新しい断片ｂｋ１（１），…，ｂｋＮ（１），…，ｂｋ１（Ｍ），…，ｂｋＮ（Ｍ）を求める（以下、これを「再分散化」と呼ぶ）。なお、対応つけられた数値群の対応を維持したまま数値群を再分散化する場合は、同一の全単射πを用いて、対応つけられた数値群の各数値の断片を置換すればよい。【０００６】
また、本発明の秘密分散システムは、初期情報分散手段、初期乗算手段、確認分散手段、確認乗算手段、改ざん検出手段も備えてもよい。初期情報分散手段は、秘密分散装置Ｒ１，…，ＲＮのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、秘密分散装置Ｒｎに記録させる。初期乗算手段は、秘密分散装置Ｒ１，…，ＲＮで、Ｓｋ＝Ｐｋ×Ａｋ（１）である数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、秘密分散装置Ｒ１，…，ＲＮに分散して記録する。確認分散手段は、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、秘密分散装置Ｒ１，…，ＲＮに分散して記録させる。確認乗算手段は、秘密分散装置Ｒ１，…，ＲＮで、Ｔｋ＝Ｑｋ×Ｂｋ（１）である数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、秘密分散装置Ｒ１，…，ＲＮに分散して記録する。改ざん検出手段は、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する。【０００７】
例えば、３つの秘密分散装置で構成する場合であれば、ｋ番目の対応つけられた数値群のｍ番目の数値Ａｋ（ｍ）＝ａｋαβ（ｍ）＋ａｋβγ（ｍ）＋ａｋγα（ｍ）（ただし、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）の３つの断片を（ａｋγα（ｍ），ａｋαβ（ｍ））、（ａｋαβ（ｍ），ａｋβγ（ｍ））、（ａｋβγ（ｍ），ａｋγα（ｍ））とする。秘密分散装置が、第１の秘密分散装置として選ばれたときには記録する断片をａｋ１（ｍ）＝（ａｋ３１（ｍ），ａｋ１２（ｍ））、第２の秘密分散装置として選ばれたときには記録する断片をａｋ２（ｍ）＝（ａｋ１２（ｍ），ａｋ２３（ｍ））、第３の秘密分散装置として選ばれたときには記録する断片をａｋ３（ｍ）＝（ａｋ２３（ｍ），ａｋ３１（ｍ））とする。そして、各秘密分散装置は、断片置換部、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部を備えればよい。断片置換部は、第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、π（ｋ）番目の対応つけられた数値群の各数値の断片をｋ番目の対応つけられた数値群の各数値の断片にする。第１乱数生成部は、第１の秘密分散装置のときには、移動後のｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂｋ３１（１），…，ｂｋ３１（Ｍ）を生成し、第３の秘密分散装置に送信する。第２乱数生成部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂｋ２３（１），…，ｂｋ２３（Ｍ）を生成し、第３の秘密分散装置に送信する。第１計算部は、第１の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｘｋ（ｍ）＝ｂｋ３１（ｍ）−ａπ（ｋ）３１（ｍ）を計算し、第２の秘密分散装置に送信する。第２計算部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｙｋ（ｍ）＝ｂｋ２３（ｍ）−ａπ（ｋ）２３（ｍ）を計算し、第１の秘密分散装置に送信する。第３計算部は、第１の秘密分散装置または第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｂｋ１２（ｍ）＝ａπ（ｋ）１２（ｍ）−ｘｋ（ｍ）−ｙｋ（ｍ）を計算する。断片更新部は、第１の秘密分散装置のときには（ｂｋ３１（ｍ），ｂｋ１２（ｍ））を断片ｂｋ１（ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２（ｍ），ｂｋ２３（ｍ））を断片ｂｋ２（ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３（ｍ），ｂｋ３１（ｍ））を断片ｂｋ３（ｍ）とする。なお、全ての秘密分散装置の断片置換部で、秘密分散システムの断片置換手段が構成される。また、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部で、秘密分散システムの再分散手段が構成される。
【発明の効果】
【０００８】
本発明の秘密分散システムによれば、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）と数値Ｂ１（１），…，ＢＫ（１），…，Ｂ１（Ｍ），…，ＢＫ（Ｍ）との対応が分からない。本発明を用いることにより、クイックソートなどの比較に基づくソーティングアルゴリズムを、比較回数を増やすことなく秘密計算上で実現できる。
【図面の簡単な説明】
【０００９】
【図１】実施例１，２の秘密分散システムの機能構成例を示す図。
【図２】実施例１の秘密分散システムでの秘密分散の処理フローを示す図。
【図３】本発明の秘密分散システムでの数値のソートの処理フローを示す図。
【図４】クイックソートのアルゴリズムを示す図。
【図５】実施例２の秘密分散システムでの秘密分散の処理フローを示す図。
【図６】実施例３，４の秘密分散システムの機能構成例を示す図。
【図７】実施例３，４の再分散部の詳細な構成の例を示す図。
【図８】実施例３の秘密分散システムでの秘密分散の処理フローを示す図。
【図９】実施例４の改ざん検出部の詳細な構造を示す図。
【図１０】実施例４の秘密分散システムでの秘密分散の処理フローを示す図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１１】
課題を解決するための手段では、数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ（１），…，Ａｋ（Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ（ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ（ｍ）の断片として説明した。本実施例では、まず本発明の理解を助けるために、Ｍ＝１の場合について説明し、その後Ｍを１に限定しない場合について説明する。また、Ｍ＝１の場合の説明では、Ａｋ（１）をＡｋと、ａｋｎ（１）をａｋｎと表現する。【００１２】
［限定シャッフル］
図１に実施例１の秘密分散システムの機能構成例を示す。図２に実施例１の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００１，…，１００Ｎと選択手段１０５で構成される。ここで、Ａ１，…，ＡＫを各秘密分散装置１００ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密分散装置１００ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。【００１３】
本実施例の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。【００１４】
選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。【００１５】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密分散装置１００ｉ間で生成してもよいし、選択された秘密分散装置１００ｉのうちの１つの秘密分散装置が生成して、選択された秘密分散装置１００ｉ間で共有してもよい。【００１６】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。【００１７】
本発明の秘密分散システムによれば、限定された秘密分散装置間で断片をシャッフルする。したがって、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密分散装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密分散装置を断片置換部で選ばないように、選択する秘密分散装置をあらかじめ定めればよい。また、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。【００１８】
［再分散］
上述の限定シャッフルの説明では、再分散については詳しく説明しなかった。ここでは、再分散の方法について説明する。再分散の方法としては、参考文献２（Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung, “Proactive secret sharing or: How to cope with perpetual leakage”, In Don Coppersmith, editor, CRYPTO 1995, volume 963 of LNCS, pages 339-352. Springer, 1995.）の3.3節に示された更新方法と、参考文献３（Haiyun Luo and Songwu Lu, “Ubiquitous and robust authentication services for ad hoc wireless networks”, In UCLA-CSD-TR-200030, 2000.）の6.1節に示された再作成方法を用いる。選択手段１０５が選択した秘密計算装置間で参考文献２の更新方法を用いて新しい断片を生成し、その後、参考文献３の再作成方法を用いて選択手段１０５が選択しなかった秘密計算装置の新しい断片を生成する。【００１９】
参考文献２の更新方法を、本件に適用したアルゴリズムを以下に示す。選択手段１０５がＮ’個の秘密分散装置を選択したとする。そして、ｉとｊは選択された秘密分散装置を示す番号（１〜Ｎの中から選ばれたＮ’個の数の中のいずれか）であって、ｊ≠ｉとする。また、値ｚ１，…，ｚＮはあらかじめ決められた値であり、すべての秘密分散装置間で共有されているとする。
（１）すべての秘密分散装置１００ｉは、Ｎ’−１個の乱数ｕｉ，１，ｕｉ，２，…，ｕｉ，Ｎ’−１を作成する。
（２）すべての秘密分散装置１００ｉは、Ｚｉ（ｚ）：＝０＋ｕｉ，１ｚ＋ｕｉ，２ｚ２＋…＋ｕｉ，Ｎ’−１ｚＮ’−１を定める。
（３）すべての秘密分散装置１００ｉは、選択された他の秘密分散装置１００ｊ（Ｎ’−１個存在する）のすべてに対して、それぞれＺｉ（ｚｊ）の値を送信する。
（４）すべての秘密分散装置１００ｉは、選択された他の秘密分散装置１００ｊ（Ｎ’−１個存在する）から受け取ったすべてのＺｊ（ｚｉ）の和をＺ（ｚｉ）とし、新しい断片ｂｋｉを置換された断片ａπ（ｋ）ｉを用いて、
ｂｋｉ＝ａπ（ｋ）ｉ＋Ｚ（ｚｉ）
のように求める。【００２０】
次に、参考文献３の再作成方法を、本件に適用したアルゴリズムを以下に示す。ｈは選択されなかった秘密分散装置を示す番号（１〜Ｎの中から選ばれなかったＮ−Ｎ’個の数のなかのいずれか）とする。また、Ｌｉｊ（ｚ）＝（ｚ−ｚｊ）／（ｚｉ−ｚｊ）とし、Ｌｉ（ｚ）は、すべてのｊについてのＬｉｊ（ｚ）の積とする。
（５）すべての秘密分散装置１００ｉは、ｉ＜ｊであるｊと、選択されなかった秘密分散装置１００ｈのすべての組み合わせに対して、乱数ｖｉ，ｊ（ｈ）を生成する。
（６）すべての秘密分散装置１００ｉは、ｖｉ，ｊ（ｈ）を秘密分散装置１００ｊに送信する。
（７）すべての秘密分散装置１００ｉは、すべての選択されなかった秘密分散装置１００ｈについて、ｊ＜ｉのすべての乱数ｖｉ，ｊ（ｈ）の和をＶ（ｈ＋）とし、ｉ＜ｊのすべての乱数ｖｉ，ｊ（ｈ）の和をＶ（ｈ−）とし、値ｗｈｉを、
ｗｈｉ＝ｂｋｉＬｉ（ｚｈ）＋Ｖ（ｈ＋）−Ｖ（ｈ−）
のように求め、秘密分散装置１００ｈに値ｗｈｉを送信する。
（８）すべての秘密分散装置１００ｈは、受信したすべての値ｗｈｉの和を新しい断片ｂｋｈとする。【００２１】
上述のように、（１）〜（４）の処理で、すべての選択された秘密分散装置が、新しい断片を記録する。（５）〜（８）の処理で、すべての選択されなかった秘密分散装置が、新しい断片を記録する。【００２２】
なお、（３）と（６）の処理を同時に行えば、処理の高速化を図ることができる。具体的には、（１）、（２）、（５）の処理をまず行い、（３）と（６）を同時に行い、（４）、（７）、（８）の処理を行えばよい。【００２３】
［ソート］
図３に実施例１の秘密分散システムでの数値のソートの処理フローを示す。上述の方法によって初期の数値Ａ１，…，ＡＫと対応つけることができない新しい数値Ａ１，…，ＡＫを得ている（Ｓ１０１）。ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。比較部２１０１，…，２１０Ｎは、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する（Ｓ２１０）。【００２４】
交換部２２０１，…，２２０Ｎは、それぞれ比較部２１０１，…，２１０Ｎでの比較結果に基づいて、０組または１組または複数組の数値の断片を入れ替える（Ｓ２２０）。そして、全ての数値に対するソート処理が終わるまで、ステップＳ２１０とＳ２２０（比較、交換、組合せの変更などの必要な処理）を繰り返せばよい（Ｓ２１１，Ｓ２１２）。【００２５】
ステップＳ２１０の比較結果は、全ての秘密分散装置の次の処理に必要な情報なので全ての秘密分散装置が知る情報である。しかし、ステップＳ１０１によって全ての秘密分散装置が初期の数値Ａ１，…，ＡＫと対応できなくなった新しい数値Ａ１，…，ＡＫに対して処理しているので、初期の数値Ａ１，…，ＡＫに関する情報は漏れない。さらに、比較結果は、ソートの出力という公開情報から計算可能な情報でもある。そのため、本実施例のプロトコル全体で見ても、比較結果が開示されることは必要以上の情報を漏らしたことにはならない。【００２６】
なお、より具体的には、ソートの部分（ステップＳ２１０，Ｓ２２０，Ｓ２１１，Ｓ２１２）には図４に示すクイックソートのアルゴリズムを適用すればよい。この場合もＡ［ｉ］とＡ［ｊ］とを比較する処理はＡ［ｉ］とＡ［ｊ］の値を秘匿したままで行い、比較結果は公開される。この方法の場合、比較回数は元のクイックソートと同じであり、平均Ｏ（Ｎ・ｌｏｇＮ）回である。また、この他にも、数値の大小比較の処理と配列の２つの要素を入れ替える処理で構成できるソーティングアルゴリズムにも本実施例は適用できる。【００２７】
このように、本実施例の秘密分散システムを用いれば、比較と要素の入れ替えからなるソーティングアルゴリズムを比較回数を増やすことなく秘密計算で実現できる。【００２８】
［限定シャッフルの変形例］
次に、Ｍを１に限定しない場合について説明する。Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ（１），…，Ａ（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ（ｍ）＝(Ａ１（ｍ），…，ＡＫ（ｍ）)とする。また、ベクトルＡ（１），…，Ａ（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａｋ（１），…，Ａｋ（Ｍ）は対応付けられたｋ番目の数値群とする。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、ａｋｎ（ｍ）を秘密分散装置１００ｎが記録する数値Ａｋ（ｍ）の断片とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。【００２９】
秘密分散システムの構成は図１と同じであり、秘密分散の処理フローは図２と同じである。秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。ただし、各構成部とその処理は以下のようになる。【００３０】
記録部１９０ｎは断片ａ１ｎ（１），…，ａＫｎ（１），…，ａ１ｎ（Ｍ），…，ａＫｎ（Ｍ）などを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。【００３１】
選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。この処理は同じである。【００３２】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。【００３３】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値群Ａπ（ｋ）（１），…，Ａπ（ｋ）（Ｍ）に対応する断片ａπ（ｋ）ｉ（１），…，ａπ（ｋ）ｉ（Ｍ）（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１（１），…，ｂｋＮ（１），…，ｂｋ１（Ｍ），…，ｂｋＮ（Ｍ）を求め、数値Ｂｋ（１），…，Ｂｋ（Ｍ）の断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）（ｍ）＝Ｂｋ（ｍ）の関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａπ（ｋ）（ｍ）＝Ｂｋ（ｍ）であることを知らない。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎ（ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎ（ｍ）が数値Ｂｋ（ｍ）の断片であるという情報も記録する。また、数値Ｂ１（１），…，ＢＫ（１），…，Ｂ１（Ｍ），…，ＢＫ（Ｍ）を新しい数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。【００３４】
このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。
【実施例２】
【００３５】
［限定シャッフル］
実施例２の秘密分散システムの構成も図１に示す。なお、本実施例の秘密分散装置１００ｎは、点線で示された構成部も備えている。図５に実施例２の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００１，…，１００Ｎと選択手段１０５で構成される。ここで、Ａ１，…，ＡＫを各秘密分散装置１００ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密分散装置１００ｎが記録する数値Ａｋの断片とする。【００３６】
本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎ、記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。【００３７】
選択手段１０５は実施例１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密計算装置１００ｉの初期情報分散部１３０ｉは、秘密分散装置１００１，…，１００Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１１，…，ｐＫ１，…，ｐ１ｎ，…，ｐＫｎ，…，ｐ１Ｎ，…，ｐＫＮを秘密計算によって求め、秘密分散装置１００ｎに断片ｐ１ｎ，…，ｐＫｎを記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密分散装置から、２つ以上の秘密分散装置を選定する。そして、選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密分散装置１００ｉ，１００ｊを選定し（ただし、ｉ≠ｊ）、秘密分散装置１００ｉが生成した数値の断片と、秘密分散装置１００ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、２つ以上でもかまわない。【００３８】
初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１４０）。【００３９】
断片置換手段と再分散手段は、実施例１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密分散装置１００ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密分散装置１００ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。【００４０】
確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１６０）。【００４１】
改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。【００４２】
実施例２の秘密分散システムによれば、実施例１の秘密分散装置と同じ効果が得られると共に、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。
【実施例３】
【００４３】
実施例１、２では、秘密分散装置の数をＮ（Ｎは３以上の整数）としていた。実施例３では、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。【００４４】
［限定シャッフル］
図６に実施例３の秘密分散システムの機能構成例を示す。図７に実施例３の再分散部の詳細な構成の例を示す。図８に実施例３の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００α，１００β，１００γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａｋ＝ａｋαβ＋ａｋβγ＋ａｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａｋγα，ａｋαβ）、（ａｋαβ，ａｋβγ）、（ａｋβγ，ａｋγα）とする。なお、選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。【００４５】
本実施例の秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。各秘密分散装置１００ｎは、断片置換部１１０ｎ、再分散部１２０ｎ、記録部１９０ｎを備えている（ただし、ｎはα、β、γのいずれか）。記録部１９０ｎは、数値Ａ１，…，ＡＫの断片などを記録する。【００４６】
選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録するｋ番目の断片をａｋ１＝（ａｋ３１，ａｋ１２）、第２の秘密分散装置１００２が記録するｋ番目の断片をａｋ２＝（ａｋ１２，ａｋ２３）、第３の秘密分散装置１００３が記録するｋ番目の断片をａｋ３＝（ａｋ２３，ａｋ３１）とする。【００４７】
断片置換手段は、少なくとも断片置換部１１０α，１１０β，１１０γを含んで構成される。断片置換手段は、第１の秘密分散装置１００１または第２の秘密分散装置１００２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００１が記録する断片ａπ（ｋ）１をｋ番目の断片にし、第２の秘密分散装置１００２が記録する断片ａπ（ｋ）２をｋ番目の断片にする（Ｓ１１０）。実施例１で説明した通り、全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffleなどを用いて作成すればよい。【００４８】
再分散手段は、少なくとも再分散部１２０α，１２０β，１２０γを含んで構成される。図７に示すように再分散部１２０ｎは、第１乱数生成部１２１ｎ、第２乱数生成部１２２ｎ、第１計算部１２３ｎ、第２計算部１２４ｎ、第３計算部１２５ｎ、断片更新部１２６ｎを備えている。【００４９】
第１の秘密分散装置１００１の第１乱数生成部１２１１は、ｋ番目の断片の再分散化のために、ランダムな値であるｂｋ３１を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２１）。第２の秘密分散装置１００２の第２乱数生成部１２２２は、ｋ番目の断片の再分散化のために、ランダムな値であるｂｋ２３を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２２）。第１の秘密分散装置１００１の第１計算部１２３１は、ｋ番目の断片の再分散化のために、ｘｋ＝ｂｋ３１−ａπ（ｋ）３１を計算し、第２の秘密分散装置１００２に送信する（Ｓ１２３）。【００５０】
第２の秘密分散装置１００２の第２計算部１２４２は、ｋ番目の断片の再分散化のために、ｙｋ＝ｂｋ２３−ａπ（ｋ）２３を計算し、第１の秘密分散装置１００１に送信する（Ｓ１２４）。第１の秘密分散装置１００１の第３計算部１２５１と第２の秘密分散装置１００２の第３計算部１２５２は、ｋ番目の断片の再分散化のために、それぞれｂｋ１２＝ａπ（ｋ）１２−ｘｋ−ｙｋを計算する（Ｓ１２５）。第１の秘密分散装置１００１の断片更新部１２６１は（ｂｋ３１，ｂｋ１２）を断片ｂｋ１とし、第２の秘密分散装置１００２の断片更新部１２６２は（ｂｋ１２，ｂｋ２３）を断片ｂｋ２とし、第３の秘密分散装置１００３の断片更新部１２６３は（ｂｋ２３，ｂｋ３１）を断片ｂｋ３とする（Ｓ１２６）。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。実施例１と同じように、断片ｂｋ１，ｂｋ２，ｂｋ３は、数値Ｂｋの断片である。つまり、ステップＳ１２１〜Ｓ１２６が、ステップＳ１２０に相当する。【００５１】
また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。そして、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。本実施例では、断片置換手段が選択する秘密分散装置を、｛１００α，１００β｝，｛１００β，１００γ｝，｛１００γ，１００α｝のように選択すれば、全ての秘密分散装置が選ばれなかったことがある状態にできる。【００５２】
したがって、実施例３の秘密分散システムは、実施例１と同様の効果が得られる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。【００５３】
［限定シャッフルの変形例］
Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ（１），…，Ａ（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ（ｍ）＝(Ａ１（ｍ），…，ＡＫ（ｍ）)とする。また、ベクトルＡ（１），…，Ａ（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａｋ（１），…，Ａｋ（Ｍ）は対応付けられたｋ番目の数値群である。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、数値Ａｋ（ｍ）＝ａｋαβ（ｍ）＋ａｋβγ（ｍ）＋ａｋγα（ｍ）（ただし、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、の３つの断片を（ａｋγα（ｍ），ａｋαβ（ｍ））、（ａｋαβ（ｍ），ａｋβγ（ｍ））、（ａｋβγ（ｍ），ａｋγα（ｍ））とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。【００５４】
秘密分散システムの機能構成例は図６と同じであり、再分散部の詳細な構成例は図７と同じであり、秘密分散の処理フローは図８と同じである。秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える（ただし、ｎはα、β、γのいずれか）。ただし、各構成部とその処理は以下のようになる。【００５５】
記録部１９０ｎは断片ａ１ｎ（１），…，ａＫｎ（１），…，ａ１ｎ（Ｍ），…，ａＫｎ（Ｍ）などを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。【００５６】
選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録する数値Ａｋ（ｍ）の断片をａｋ１（ｍ）＝（ａｋ３１（ｍ），ａｋ１２（ｍ））、第２の秘密分散装置１００２が記録する数値Ａｋ（ｍ）の断片をａｋ２（ｍ）＝（ａｋ１２（ｍ），ａｋ２３（ｍ））、第３の秘密分散装置１００３が記録する数値Ａｋ（ｍ）の断片をａｋ３（ｍ）＝（ａｋ２３（ｍ），ａｋ３１（ｍ））とする。【００５７】
断片置換手段は、少なくとも断片置換部１１０α，１１０β，１１０γを含んで構成される。断片置換手段は、第１の秘密分散装置１００１または第２の秘密分散装置１００２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００１が記録する断片ａπ（ｋ）１（１），…，ａπ（ｋ）１（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置１００２が記録する断片ａπ（ｋ）２（１），…，ａπ（ｋ）２（Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。【００５８】
再分散手段は、少なくとも再分散部１２０α，１２０β，１２０γを含んで構成される。図７に示すように再分散部１２０ｎは、第１乱数生成部１２１ｎ、第２乱数生成部１２２ｎ、第１計算部１２３ｎ、第２計算部１２４ｎ、第３計算部１２５ｎ、断片更新部１２６ｎを備えている。【００５９】
第１の秘密分散装置１００１の第１乱数生成部１２１１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１（１），…，ｂｋ３１（Ｍ）を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２１）。第２の秘密分散装置１００２の第２乱数生成部１２２２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３（１），…，ｂｋ２３（Ｍ）を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２２）。第１の秘密分散装置１００１の第１計算部１２３１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘｋ（ｍ）＝ｂｋ３１（ｍ）−ａπ（ｋ）３１（ｍ）を計算し、ｘｋ（１），…，ｘｋ（Ｍ）を第２の秘密分散装置１００２に送信する（Ｓ１２３）。【００６０】
第２の秘密分散装置１００２の第２計算部１２４２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙｋ（ｍ）＝ｂｋ２３（ｍ）−ａπ（ｋ）２３（ｍ）を計算し、ｙｋ（１），…，ｙｋ（Ｍ）を第１の秘密分散装置１００１に送信する（Ｓ１２４）。第１の秘密分散装置１００１の第３計算部１２５１と第２の秘密分散装置１００２の第３計算部１２５２は、対応付けられたｋ番目の数値群の断片の再分散化のために、それぞれｍ＝１〜Ｍについてｂｋ１２（ｍ）＝ａπ（ｋ）１２（ｍ）−ｘｋ（ｍ）−ｙｋ（ｍ）を計算する（Ｓ１２５）。第１の秘密分散装置１００１の断片更新部１２６１は（ｂｋ３１（ｍ），ｂｋ１２（ｍ））を断片ｂｋ１（ｍ）とし、第２の秘密分散装置１００２の断片更新部１２６２は（ｂｋ１２（ｍ），ｂｋ２３（ｍ））を断片ｂｋ２（ｍ）とし、第３の秘密分散装置１００３の断片更新部１２６３は（ｂｋ２３（ｍ），ｂｋ３１（ｍ））を断片ｂｋ３（ｍ）とする（Ｓ１２６）。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎ（ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎ（ｍ）が数値Ｂｋ（ｍ）の断片であるという情報も記録する。実施例１と同じように、断片ｂｋ１（ｍ），ｂｋ２（ｍ），ｂｋ３（ｍ）は、数値Ｂｋ（ｍ）の断片である。つまり、ステップＳ１２１〜Ｓ１２６が、ステップＳ１２０に相当する。【００６１】
また、数値Ｂ１（１），…，ＢＫ（１），…，Ｂ１（Ｍ），…，ＢＫ（Ｍ）を新しい数値Ａ１（１），…，ＡＫ（１），…，Ａ１（Ｍ），…，ＡＫ（Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。【００６２】
このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。
【実施例４】
【００６３】
実施例４でも、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。また、実施例４では、実施例２と同じように不正検出機能を具備した例を説明する。【００６４】
［限定シャッフル］
実施例４の秘密分散システムの構成も図６に示す。なお、本実施例の秘密分散装置１００ｎは、点線で示された構成部も備えている。図９に改ざん検出部の詳細な構造を示す。図１０に実施例４の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００α，１００β，１００γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａｋ＝ａｋαβ＋ａｋβγ＋ａｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａｋγα，ａｋαβ）、（ａｋαβ，ａｋβγ）、（ａｋβγ，ａｋγα）とする。【００６５】
本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎ、記録部１９０ｎを備える（ただし、ｎはα、β、γのいずれか）。記録部１９０ｎは、数値Ａ１，…，ＡＫの断片などを記録する。【００６６】
選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録するｋ番目の断片をａｋ１＝（ａｋ３１，ａｋ１２）、第２の秘密分散装置１００２が記録するｋ番目の断片をａｋ２＝（ａｋ１２，ａｋ２３）、第３の秘密分散装置１００３が記録するｋ番目の断片をａｋ３＝（ａｋ２３，ａｋ３１）とする。【００６７】
初期情報分散手段は、初期情報分散部１３０α，１３０β，１３０γで構成される。初期情報分散部１３０α，１３０β，１３０γは、秘密分散装置１００α，１００β，１００γのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐｋｎを秘密計算によって求め、秘密分散装置１００ｎに記録する（Ｓ１３０）。例えば、第１の秘密分散装置１００１でＫ個のランダムな値Ｒ（１）１，…，Ｒ（１）Ｋを生成し、第２の秘密分散装置１００２でＫ個のランダムな値Ｒ（２）１，…，Ｒ（２）Ｋを生成する。そして、秘密分散装置１００１，１００２，１００３で、Ｒ（１）ｋの断片（ｒ（１）ｋ３１，ｒ（１）ｋ１２）、（ｒ（１）ｋ１２，ｒ（１）ｋ２３）、（ｒ（１）ｋ２３，ｒ（１）ｋ３１）と、Ｒ（２）ｋの断片（ｒ（２）ｋ３１，ｒ（２）ｋ１２）、（ｒ（２）ｋ１２，ｒ（２）ｋ２３）、（ｒ（２）ｋ２３，ｒ（２）ｋ３１）とを秘密分散して記録する。その後、秘密分散装置１００１，１００２，１００３で、Ｐｋ＝Ｒ（１）ｋ＋Ｒ（２）ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、秘密分散装置１００１，１００２，１００３に分散して記録する。このような処理によって、全ての秘密分散装置１００α，１００β，１００γが知らない数値の断片を分散して記録できる。【００６８】
初期乗算手段は、初期乗算部１４０α，１４０β，１４０γで構成される。初期乗算部１４０α，１４０β，１４０γは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片（ｓｋγα，ｓｋαβ）、（ｓｋαβ，ｓｋβγ）、（ｓｋβγ，ｓｋγα）を秘密計算によって求め、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１４０）。【００６９】
断片置換手段と再分散手段は、実施例３と同じである。断片置換手段と再分散手段によって、秘密分散装置１００α，１００β，１００γに数値Ｂｋの断片として断片ｂｋ１、ｂｋ２、ｂｋ３が記録される。確認分散手段は、確認分散部１５０α，１５０β，１５０γで構成される。確認分散部１５０α，１５０β，１５０γは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片（ｑｋγα，ｑｋαβ）、（ｑｋαβ，ｑｋβγ）、（ｑｋβγ，ｑｋγα）を秘密計算によって生成し、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１５０）。例えば、ステップＳ１３０で第１の秘密分散装置１００１が生成した数値Ｒ（１）π（ｋ）の別の断片（ｒ’（１）π（ｋ）３１，ｒ’（１）π（ｋ）１２）、（ｒ’（１）π（ｋ）１２，ｒ’（１）π（ｋ）２３）、（ｒ’（１）π（ｋ）２３，ｒ’（１）π（ｋ）３１）と、第２の秘密分散装置１００２が生成した数値Ｒ（２）π（ｋ）の別の断片（ｒ’（２）π（ｋ）３１，ｒ’（２）π（ｋ）１２）、（ｒ’（２）π（ｋ）１２，ｒ’（２）π（ｋ）２３）、（ｒ’（２）π（ｋ）２３，ｒ’（２）π（ｋ）３１）とを秘密分散して記録する。その後、秘密分散装置１００１，１００２，１００３で、Ｑｋ＝Ｒ（１）π（ｋ）＋Ｒ（２）π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を別の断片を用いて秘密計算によって求め、秘密分散装置１００１，１００２，１００３に分散して記録する。このような処理によって、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密分散装置１００α，１００β，１００γが知らない数値の断片を分散して記録できる。【００７０】
確認乗算手段は、確認乗算部１６０α，１６０β，１６０γで構成される。確認乗算部１６０α，１６０β，１６０γは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片（ｔｋγα，ｔｋαβ）、（ｔｋαβ，ｔｋβγ）、（ｔｋβγ，ｔｋγα）を秘密計算によって求め、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１６０）。【００７１】
改ざん検出手段は、改ざん検出部１７０α，１７０β，１７０γで構成される。また、図９に示すように、改ざん検出部１７０ｎは、第３乱数生成部１７１ｎ、第４乱数生成部１７２ｎ、第４計算部１７３ｎ、第５計算部１７４ｎ、第１確認部１７５ｎ、第６計算部１７６ｎ、第７計算部１７７ｎ、第２確認部１７８ｎを備える。改ざん検出手段は、秘密分散装置１００α，１００β，１００γが第１の秘密分散装置１００１、第２の秘密分散装置１００２、第３の秘密分散装置１００３のいずれの装置として動作するかにしたがって、以下のように処理を行う。【００７２】
第１の秘密分散装置１００１の第３乱数生成部１７１１は、ランダムな値であるｕｋを生成し、第２の秘密分散装置１００２に送信する（Ｓ１７１）。第２の秘密分散装置１００２の第４乱数生成部１７２２は、ランダムな値であるｖｋを生成し、第１の秘密分散装置１００１に送信する（Ｓ１７２）。第１の秘密分散装置１００１の第４計算部１７３１は、ｄｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７３）。【００７３】
第２の秘密分散装置１００２の第５計算部１７４２は、ｅｋ＝ｓπ（ｋ）１２−ｔｋ１２−ｕｋ−ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７４）。第３の秘密分散装置１００３の第１確認部１７５３は、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する（Ｓ１７５）。【００７４】
第１の秘密分散装置１００１の第６計算部１７６１は、ｆｋ＝ｓπ（ｋ）３１−ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７６）。第２の秘密分散装置１００２の第７計算部１７７２は、ｇｋ＝ｓπ（ｋ）２３−ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７７）。第３の秘密分散装置１００３の第２確認部１７８３は、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する（Ｓ１７８）。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。【００７５】
実施例４の秘密分散システムによれば、実施例３の秘密分散装置と同じ効果が得られると共に、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。【００７６】
［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、実施例３、４の秘密分散システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、秘密分散装置１００α，１００β，１００γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。【００７７】
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ−ａαβ−ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密分散装置１００α，１００β，１００γに分散して記録する。【００７８】
数値Ａの復元
（１）秘密分散装置１００αは秘密分散装置１００βにａγαを送信し、秘密分散装置１００γにａαβを送信する。秘密分散装置１００βは秘密分散装置１００γにａαβを送信し、秘密分散装置１００αにａβγを送信する。秘密分散装置１００γは秘密分散装置１００αにａβγを送信し、秘密分散装置１００βにａγαを送信する。
（２）秘密分散装置１００αは秘密分散装置１００βから受信したａβγと秘密分散装置１００γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密分散装置１００βは秘密分散装置１００γから受信したａγαと秘密分散装置１００αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密分散装置１００γは秘密分散装置１００αから受信したａαβと秘密分散装置１００βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。【００７９】
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。【００８０】
Ｃ＝Ａ−Ｂの秘密計算
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα−ｂγα，ａαβ−ｂαβ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβ−ｂαβ，ａβγ−ｂβγ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ−ｂβγ，ａγα−ｂγα）を計算して記録する。【００８１】
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密分散装置１００βの処理はない。【００８２】
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。【００８３】
Ｃ＝ＡＢの秘密計算
（１）秘密分散装置１００αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）−ｒ１−ｒ２−ｃγαを計算する。そして、秘密分散装置１００αは、秘密分散装置１００βに（ｒ１，ｃαβ）を、秘密分散装置１００γに（ｒ２，ｃγα）を送信する。
（２）秘密分散装置１００βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密分散装置１００γに送信する。
（３）秘密分散装置１００γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密分散装置１００αに送信する。
（４）秘密分散装置１００βと秘密分散装置１００γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密分散装置１００αは（ｃγα，ｃαβ）を記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）を記録し、秘密分散装置１００γは（ｃβγ，ｃγα）を記録する。【００８４】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。【００８５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。【００８６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。【００８７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。【００８８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。【００８９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2012046692.tif 000003
【図２】
2012046692.tif 000004
【図３】
2012046692.tif 000005
【図４】
2012046692.tif 000006
【図５】
2012046692.tif 000007
【図６】
2012046692.tif 000008
【図７】
2012046692.tif 000009
【図８】
2012046692.tif 000010
【図９】
2012046692.tif 000011
【図１０】
2012046692.tif 000012
【国際調査報告】
2012046692.tif 000013
2012046692.tif 000014
2012046692.tif 000015