"3個以上の秘密マッチング装置で構成され、それぞれM個のレコードからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に対して所定の処理が施された後の表[X1S],...,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,...,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する秘密マッチングシステムであって、Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[hj]に対応するベクトル、[XjS]は前記所定の処理後の表[Xj]に対応する表とし、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求め、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける対応用ベクトル生成手段と、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める対応用ランダム置換手段と、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求める対応用ベクトル復号手段と、すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替える対応用並び替え手段と、を備える秘密マッチングシステム。請求項1記載の秘密マッチングシステムであって、J=2であり、前記所定の処理は、M個のレコードを持つ表[X1]の各レコードの一部または全部の要素を用いたソートを含み、表[X2]に対しては何も行わないものであり、さらに、表[X]を、前記の表[X1]と前記の表[X2]に、表[X1]が少なくとも前記所定の処理に用いる要素を含むように分割する表分割手段と、異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、前記所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコード対応が維持されるように対応付けするベクトル結合手段と、前記対応用並び替え手段の処理後の表[X1R],[X2R]を結合して表[XR]とする表結合手段と、表[XR]のレコード間を秘密計算でランダム置換し、表[XRR]を求める表ランダム置換手段と、前記表[X1S]に対応付けされた前記ベクトル[c]の表ランダム置換手段の処理後のベクトル[cRR]を復号し、ベクトルcRRを求めるソート用ベクトル復号手段と、ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動するソート手段と、を備える秘密マッチングシステム。請求項1記載の秘密マッチングシステムであって、前記所定の処理はB個の処理F1,...,FBからなり、処理FbはM個のレコードを持つ表[X1],...,[XJ]の一部または全部を用いる処理Fbごとに定められた処理、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b1,...,bDは1以上D以下の異なる整数、D’は1以上の整数とし、さらに、表[X]をJ個に分割して前記の表[X1],...,[XJ]を求める表分割手段と、処理Fbに必要な要素を有する表[Xb1],...,[XbD]を選び、bd=b1,...,bDについて、表[Xbd]とベクトル[hbd]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XbdR]とベクトル[hbdR]とを求める処理用ランダム置換手段と、ベクトル[hb1R],...,[hbDR]を復号し、ベクトルhb1R,...,hbDRを求める処理用ベクトル復号手段と、すべてのbiとbdの組合せただし、ここでのiは1,...,Dのいずれかに対してhbiR=hbdRとなるように表[XbdR]のレコードを並び替え、表[Xb1T],...,[XbDT]を得る処理用並び替え手段と、ベクトルhbiRの各要素を秘密分散したベクトル[hbiR]の各要素を表[Xb1T],...,[XbDT]の各レコードに、処理Fbを施しても対応が維持されるように対応付ける処理用ベクトル対応手段と、ベクトル[hbiR]が対応付けられた表[Xb1T],...,[XbDT]に対して処理Fbを行って、処理Fb後のベクトル[hbiF]が対応付けられた処理Fb後の表[Xb1F],...,[XbD’F]を求め、処理Fb前のJ個の表の中から0個以上、処理Fb後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理Fb後のベクトル[hjbS]と表[X1bS],...,[XJbS]を求める処理手段と、b=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],...,[XJbS]を表[X1S],...,[XJS]とし、Noの場合はベクトル[hjbS]をベクトル[hj]、表[X1bS],...,[XJbS]を表[X1],...,[XJ]とし、b=1からBについて、前記処理用ランダム置換手段、前記処理用ベクトル復号手段、前記処理用並び替え手段、前記処理用ベクトル対応手段、前記処理手段の処理を繰り返す処理用繰返手段と、を備える秘密マッチングシステム。M個のレコードからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に対して所定の処理が施された後の表[X1S],...,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,...,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する3個以上の秘密マッチング装置で構成される秘密マッチングシステムの中の秘密マッチング装置であって、Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[hj]に対応するベクトル、[XjS]は前記所定の処理後の表[Xj]に対応する表とし、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求め、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付けるための対応用ベクトル生成部と、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求めるための対応用ランダム置換部と、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求めるための対応用ベクトル復号部と、すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替えるための対応用並び替え部と、を備える秘密マッチング装置。3個以上の秘密マッチング装置を用いて、それぞれM個のレコードからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に対して所定の処理が施された後の表[X1S],...,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,...,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する秘密マッチング方法であって、Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[hj]に対応するベクトル、[XjS]は前記所定の処理後の表[Xj]に対応する表とし、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求め、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける対応用ベクトル生成ステップと、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める対応用ランダム置換ステップと、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求める対応用ベクトル復号ステップと、すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替える対応用並び替えステップと、を有する秘密マッチング方法。請求項5記載の秘密マッチング方法であって、J=2であり、前記所定の処理は、M個のレコードを持つ表[X1]の各レコードの一部または全部の要素を用いたソートを含み、表[X2]に対しては何も行わないものであり、表[X]を、前記の表[X1]と前記の表[X2]に、表[X1]が少なくとも前記所定の処理に用いる要素を含むように分割する表分割ステップと、異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、前記の表[X1]に対する前記所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付けするベクトル結合ステップと、前記対応用並び替えステップ後の表[X1R],[X2R]を結合して表[XR]とする表結合ステップと、表[XR]のレコード間を秘密計算でランダム置換し、表[XRR]を求める表ランダム置換ステップと、前記表[X1S]に対応付けされた前記ベクトル[c]の表ランダム置換手段の処理後のベクトル[cRR]を復号し、ベクトルcRRを求めるソート用ベクトル復号ステップと、ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動するソートステップと、を有する秘密マッチング方法。請求項5記載の秘密マッチング方法であって、前記所定の処理はB個の処理F1,...,FBからなり、処理FbはM個のレコードを持つ表[X1],...,[XJ]の一部または全部を用いる処理Fbごとに定められた処理、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b1,...,bDは1以上D以下の異なる整数、D’は1以上の整数とし、表[X]をJ個に分割して前記の表[X1],...,[XJ]を求める表分割ステップと、処理Fbに必要な要素を有する表[Xb1],...,[XbD]を選び、bd=b1,...,bDについて、表[Xbd]とベクトル[hbd]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XbdR]とベクトル[hbdR]とを求める処理用ランダム置換ステップと、ベクトル[hb1R],...,[hbDR]を復号し、ベクトルhb1R,...,hbDRを求める処理用ベクトル復号ステップと、すべてのbiとbdの組合せただし、ここでのiは1,...,Dのいずれかに対してhbiR=hbdRとなるように表[XbdR]のレコードを並び替え、表[Xb1T],...,[XbDT]を得る処理用並び替えステップと、ベクトルhbiRの各要素を秘密分散したベクトル[hbiR]の各要素を表[Xb1T],...,[XbDT]の各レコードに、処理Fbを施しても対応が維持されるように対応付ける処理用ベクトル対応ステップと、ベクトル[hbiR]が対応付けられた表[Xb1T],...,[XbDT]に対して処理Fbを行って、処理Fb後のベクトル[hbiF]が対応付けられた処理Fb後の表[Xb1F],...,[XbD’F]を求め、処理Fb前のJ個の表の中から0個以上、処理Fb後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理Fb後のベクトル[hjbS]と表[X1bS],...,[XJbS]を求める処理ステップと、を有しb=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],...,[XJbS]を表[X1S],...,[XJS]とし、Noの場合はベクトル[hjbS]をベクトル[hj]、表[X1bS],...,[XJbS]を表[X1],...,[XJ]とし、b=1からBについて、前記処理用ランダム置換ステップ、前記処理用ベクトル復号ステップ、前記処理用並び替えステップ、前記処理用ベクトル対応ステップ、前記処理ステップの処理を繰り返す秘密マッチング方法。請求項1から3のいずれかに記載の秘密マッチングシステムの各秘密マッチング装置としてコンピュータを機能させるための秘密マッチングプログラム。通常、複数のレコードを有する表のレコードのソートを行う場合、レコードに含まれる要素は、ソートの計算に直接使われる要素値とソートの計算に直接使われない要素値の2種類に分けられる。例えば、各レコードが年齢,性別,体重,年収の4つ要素の組であり、体重に関して昇順にソートしたい場合、各レコードのうち年齢,性別,年収の要素はソートの計算には直接使われない。しかしながら、従来技術では、ソートなどでレコードの並び替えを行う場合に、ソートの計算に直接使われない要素値も含めて並び替えが行われており、計算効率が悪かった。また、秘密計算上のソートなどの処理では、情報を隠すためにソートの前後の対応を誰にも分からないように並び替えを行う必要がある。このため、ソートに必要のない要素をソートに必要な要素から切り離してしまうと、ソートが終わった後にもともと同じレコードであった要素同士を結びつけることができなかった。本発明は、各レコードが対応している2つ以上の表の中でソートに必要な要素を含む表だけで秘密計算によるソートを行った場合でも、ソートが終わった後にすべての表のレコード同士を結びつける技術を提供することを目的とする。本発明の秘密マッチングシステムは、3個以上の秘密マッチング装置で構成され、それぞれM個のレコードx1j,...,xMjからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に対して所定の処理が施された後の表[X1S],...,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,...,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する。ここで、Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[hj]に対応するベクトル、[XjS]は前記所定の処理後の表[Xj]に対応する表とする。なお、上記のように所定の処理では、何個かの表に対しては何の処理も行わない場合もある。何の処理も行わなかった場合は、[XjS]=[Xj]である。本発明の秘密マッチングシステムは、対応用ベクトル生成手段、対応用ランダム置換手段、対応用ベクトル復号手段、対応用並び替え手段を備える。対応用ベクトル生成手段は、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求める。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける。対応用ランダム置換手段は、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める。対応用ベクトル復号手段は、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求める。対応用並び替え手段は、レコードの順番を維持する表[XiR]以外の表[XjR]ただし、j=1,...,Jかつj≠iのレコードをhjR=hiRとなるように並び替える。本発明の秘密マッチングシステムによれば、ソートなどを行う場合にデータ本体を動かすのではなくポインタを動かせばよいという、通常の計算機上ではよく使われるテクニックを秘密計算で実現できる。秘密計算上でソートを行う場合には、情報を隠す必要があるため、ソートの前後のデータ間の対応を誰にもわからないように処理がなされる。そのため、単純に表のレコードを分割して2つ以上の表を作ってしまうと、ソート後に対応するレコード同士のマッチングを行うことができなかった。本発明の秘密マッチングシステムでは、あらかじめ対応するレコード同士に目印となるデータをそれぞれ持たせておく。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。このように、本発明の秘密マッチングシステムによれば、ソートに必要な部分だけでソートを行い、ソートが終わった後でその他の部分を移動させることができるようになるので、計算効率を改善できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。図1に実施例1の秘密マッチングシステムの機能構成例を示す。図2に実施例1の秘密マッチングシステムの処理フローを示す。実施例1の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置101,...,10Nで構成される。そして、実施例1の秘密マッチングシステムは、それぞれM個のレコードx1j,...,xMjからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に対して所定の処理が施された後の表[X1S],...,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,...,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する。ここで、Mは2以上の整数、Nは3以上の整数、Jは2以上の整数、nは1以上N以下の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は所定の処理後のベクトル[hj]に対応するベクトル、[XjS]は所定の処理後の表[Xj]に対応する表とする。なお、上記のように所定の処理では、何個かの表に対しては何の処理も行わない場合もある。何の処理も行わなかった場合は、[XjS]=[Xj]である。秘密マッチング装置10nは、マッチング制御部300n、秘密分散装置100n、記録部190nを備える。秘密分散装置100nは、マッチング制御部300nの指示にしたがって実施例1の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、ランダム置換などがある。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、1つの例であり、本発明が利用できる秘密計算を限定するものではない。記録部190nは、秘密マッチング装置10nの処理に必要な情報を記録する構成部である。図1に示した選択手段105は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。各秘密マッチング装置10nのマッチング制御部300nは、対応用ベクトル生成部310n、対応用ランダム置換部320n、対応用ベクトル復号部330n、対応用並び替え部340nを備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310図示していないは対応用ベクトル生成部3101,...,310Nで構成され、対応用ランダム置換手段320図示していないは対応用ランダム置換部3201,...,320Nで構成され、対応用ベクトル復号手段330図示していないは対応用ベクトル復号部3301,...,330Nで構成され、対応用並び替え手段340図示していないは対応用並び替え部3401,...,340Nで構成される。対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求める。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、所定の処理を施しても対応が維持されるように対応付けるS310。より具体的には、対応用ベクトル生成部3101,...,310N対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、秘密分散装置1001,...,100Nにベクトルhaの各要素を秘密分散させてベクトル[ha]を求めさせ、ベクトル[ha]をランダム置換させてベクトル[h]を求めさせる。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに対応付ける。次に、ソートのようなレコードの順番が変わる可能性がある所定の処理を、表[X1],...,[XJ]一部または全部に対して実行し、処理後の表[X1S],...,[XJS]を得るS315。したがって、表[X1S],...,[XJS]では、もともと対応していたレコード同士が異なる順番となっている可能性がある。なお、ステップS315の所定の処理は、後述の秘密計算の四則演算や秘密計算の論理演算を組み合わせればよい。例えば、x=yかを秘密計算で確認する場合には、従来技術として蓄積された論理回路の技術を用いれば、実現できる。例えば、xとyを2ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。C=1-{xB[∨]yB∨∨x1[∨]y1}1ただし、[∨]は排他的論理和XORを示す記号、∨は論理和ORを示す記号、xbは2ビット展開したときのxの下からbビット目の値、ybは2ビット展開したときのyの下からbビット目の値、Bは2ビット展開したときのxとyの桁数とする。式1では、C=1ならばx=y真、C=0ならばx≠y偽である。また、式1の個々の演算は後述の秘密計算の例に示されているので、式1の演算は秘密計算で実行でき、秘密分散された[C]が求められる。したがって、確認後の分岐も秘密にするのであれば、[C]を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、所望の演算を後述する秘密計算の方法の組合せで実行できる。対応用ランダム置換手段320は、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求めるS320。より具体的には、対応用ランダム置換部3201,...,320N対応用ランダム置換手段320は、j=1~Jについて、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置1001,...,100Nに実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。対応用ベクトル復号手段330は、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求めるS330。より具体的には、対応用ベクトル復号部3301,...,330N対応用ベクトル復号手段330は、秘密分散装置1001,...,100Nにベクトル[h1R],...,[hJR]を復号させ、ベクトルh1R,...,hJRを求める。対応用並び替え手段340は、すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替えるS340。より具体的には、対応用並び替え部3401,...,340N対応用並び替え手段340は、レコードの順番を維持する表[XiR]を特定する。そして、表[XiR]以外の表[XjR]ただし、j=1,...,Jかつj≠iのレコードをhjR=hiRとなるように並び替えればよい。本実施例の秘密マッチングシステムでは、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[hj]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。このように、本実施例の秘密マッチングシステムによれば、ソートに必要な部分だけでソートを行い、ソートが終わった後でその他の部分を移動させることができるようになるので、計算効率を改善できる。図3に実施例2の秘密マッチングシステムの機能構成例を示す。図4に実施例2の秘密マッチングシステムの処理フローを示す。実施例2の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置201,...,20Nで構成される。そして、実施例2の秘密マッチングシステムは、M個のレコードを持つ表[X1]の各レコードの一部または全部の要素を用いてソートを行う。また、表[X2]に対しては何も行わない。ここで、Mは2以上の整数、Nは3以上の整数、J=2、nは1以上N以下の整数、jは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号とする。秘密マッチング装置20nは、マッチング制御部400n、秘密分散装置100n、記録部190nを備える。秘密分散装置100nは、マッチング制御部400nの指示にしたがって実施例2の処理に必要な個々の秘密計算を行う。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではないので、秘密計算については、例を後述することとし、本実施例での説明は省略する。各秘密マッチング装置20nのマッチング制御部400nは、対応用ベクトル生成部310n、対応用ランダム置換部320n、対応用ベクトル復号部330n、対応用並び替え部340n、表分割部405n、ベクトル結合部450n、表結合部460n、表ランダム置換部470n、ソート用ベクトル復号部480n、ソート部490nを備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310図示していないは対応用ベクトル生成部3101,...,310Nで構成され、対応用ランダム置換手段320図示していないは対応用ランダム置換部3201,...,320Nで構成され、対応用ベクトル復号手段330図示していないは対応用ベクトル復号部3301,...,330Nで構成され、対応用並び替え手段340図示していないは対応用並び替え部3401,...,340Nで構成され、表分割手段405図示していないは表分割部4051,...,405Nで構成され、ベクトル結合手段450図示していないはベクトル結合部4501,...,450Nで構成され、表結合手段460図示していないは表結合部4601,...,460Nで構成され、表ランダム置換手段470図示していないは表ランダム置換部4701,...,470Nで構成され、ソート用ベクトル復号手段480図示していないはソート用ベクトル復号部4801,...,480Nで構成され、ソート手段490図示していないはソート部4901,...,490Nで構成される。表分割手段405は、表[X]を、表[X1]と表[X2]に、表[X1]が少なくとも所定の処理に用いる要素を含むように分割するS405。より具体的には、表分割部4051,...,405N表分割手段405は、秘密分散装置1001,...,100Nに、表[X]を、それぞれM個のレコードx1j,...,xMjからなりレコード同士が対応付けられている表[X1]と表[X2]に分割させる。対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求める。そして、j=1,2について、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、所定の処理を施しても対応が維持されるように対応付けるS310。より具体的には、対応用ベクトル生成部3101,...,310N対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、秘密分散装置1001,...,100Nにベクトルhaの各要素を秘密分散させてベクトル[ha]を求めさせ、ベクトル[ha]をランダム置換させてベクトル[h]を求めさせる。そして、j=1,2について、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに対応付ける。次に、レコードの順番が変わる可能性がある所定の処理を、表[X1]に対して実行し、処理後の表[X1S]と表[X2S]を得るS315。なお、表[X2]はソートには関係ない要素のみからなる表なので、ソートは実行されない。したがって、表[X1S]と表[X2S]のレコードの順番は異なる可能性がある。ベクトル結合手段450は、異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付けるS450。より具体的には、ベクトル結合部4501,...,450Nベクトル結合手段450は、異なる値を持つM個の要素からなるベクトルcを作成し、秘密分散装置1001,...,100Nに各要素を秘密分散してベクトル[c]を求めさせる。そして、所定の処理例えば、表[X1]は特定の要素に基づいてソートし、表[X2]に対しては何もしないという処理の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付けさせる。なお、ベクトルcの各要素は、表の各レコードの順番を示すための値であり、例えば1からMの値を用いればよい。しかし、1からMの値に限定する必要はない。また、表[X2]に対しては何も行っていないので、[X2S]=[X2]である。対応用ランダム置換手段320は、j=1,2について、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求めるS320。より具体的には、対応用ランダム置換部3201,...,320N対応用ランダム置換手段320は、j=1,2について、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置1001,...,100Nに実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。対応用ベクトル復号手段330は、ベクトル[h1R],[h2R]を復号し、ベクトルh1R,h2Rを求めるS330。より具体的には、対応用ベクトル復号部3301,...,330N対応用ベクトル復号手段330は、秘密分散装置1001,...,100Nにベクトル[h1R],[h2R]を復号させ、ベクトルh1R,h2Rを求める。対応用並び替え手段340は、表[X2R]のレコードをh2R=h1Rとなるように並び替えるS340。より具体的には、対応用並び替え部3401,...,340N対応用並び替え手段340は、表[X1R]以外の表[X2R]のレコードをh2R=h1Rとなるように並び替える。表結合手段460は、表[X1R],[X2R]を結合して表[XR]を得るS460。より具体的には、表結合部4601,...,460N表結合手段460は、表[X1R],[X2R]へのベクトル[h1R],[h2R]の対応付けを解除し、表[X1R],[X2R]を結合して表[XR]を得る。表ランダム置換手段470は、表[XR]のレコード間を秘密計算でランダム置換し、表[XRR]を求めるS470。より具体的には、表ランダム置換部4701,...,470N表ランダム置換手段470は、秘密分散装置1001,...,100Nに表[XR]のレコード間を秘密計算でランダム置換させ、表[XRR]を求めさせる。ソート用ベクトル復号手段480は、表[X1S]に対応付けされたベクトル[c]の表ランダム置換手段470の処理後のベクトル[cRR]を復号し、ベクトルcRRを求めるS480。より具体的には、表[X1S]に対応付けされたベクトル[c]は、表ランダム置換手段470の処理によってランダム置換されベクトル[cRR]となっている。ソート用ベクトル復号部4801,...,480Nソート用ベクトル復号手段480は、このベクトル[cRR]と表[XRR]との対応付けを解除して、秘密分散装置1001,...,100Nにベクトル[cRR]を復号させ、ベクトルcRRを求める。ソート手段490は、ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動するS490。例えば、ベクトルcが1からMまで順番に並んだベクトルであれば、ソート手段S490は、ベクトルcRRの各要素に示された順番に、表[XRR]の各レコードを移動すればよいS490。本実施例の秘密マッチングシステムも、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[hj]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。また、所定の処理ソートのようにレコードの順番が変わる可能性のある処理の前に、所定の処理に必要な要素を含む表[X1]と所定の処理に必要ない要素からなる表[X2]に表[X]を分割した上で、表[X1]に対してのみ所定の処理を行い、所定の処理が終わった後で表[X2]を結合し、所定の処理後の順番にレコードの順番を戻すので、計算効率を改善できる。図5に実施例3の秘密マッチングシステムの機能構成例を示す。図6に実施例3の秘密マッチングシステムの処理フローを示す。実施例3の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置301,...,30Nで構成される。そして、実施例3の秘密マッチングシステムでは、所定の処理がB個の処理F1,...,FBからなる。処理FbはM個のレコードを持つ表[X1],...,[XJ]の一部または全部用いる処理である。また、所定の処理は、処理Fbごとに定められた処理であり、処理に用いる表も処理Fbごとに決められる。ここで、Mは2以上の整数、Nは3以上の整数、Jは2以上の整数、nは1以上N以下の整数、iとjは1以上J以下の整数、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b1,...,bDは1以上D以下の異なる整数、D’は1以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号とする。秘密マッチング装置30nは、マッチング制御部500n、秘密分散装置100n、記録部190nを備える。秘密分散装置100nは、マッチング制御部500nの指示にしたがって実施例3の処理に必要な個々の秘密計算を行う。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではないので、秘密計算については、例を後述することとし、本実施例での説明は省略する。各秘密マッチング装置30nのマッチング制御部500nは、対応用ベクトル生成部310n、対応用ランダム置換部320n、対応用ベクトル復号部330n、対応用並び替え部340n、表分割部505n、処理用ランダム置換部520n、処理用ベクトル復号部530n、処理用並び替え部540n、処理用ベクトル対応部550n、処理部560n、処理用繰返部570nを備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310図示していないは対応用ベクトル生成部3101,...,310Nで構成され、対応用ランダム置換手段320図示していないは対応用ランダム置換部3201,...,320Nで構成され、対応用ベクトル復号手段330図示していないは対応用ベクトル復号部3301,...,330Nで構成され、対応用並び替え手段340図示していないは対応用並び替え部3401,...,340Nで構成され、表分割手段505図示していないは表分割部5051,...,505Nで構成され、処理用ランダム置換手段520図示していないは処理用ランダム置換部5201,...,520Nで構成され、処理用ベクトル復号手段530図示していないは処理用ベクトル復号部5301,...,530Nで構成され、処理用並び替え手段540図示していないは処理用並び替え部5401,...,540Nで構成され、処理用ベクトル対応手段550図示していないは処理用ベクトル対応部5501,...,550Nで構成され、処理手段560図示していないは処理部5601,...,560Nで構成され、処理用繰返手段570図示していないは処理用繰返部5701,...,570Nで構成される。表分割手段505は、表[X]をJ個に分割して前記の表[X1],...,[XJ]を求めるS505。より具体的には、表分割部5051,...,505N表分割手段505は、表[X]を、それぞれM個のレコードx1j,...,xMjからなりレコード同士が対応付けられているJ個の表[X1],...,[XJ]に分割する。これらの表[X1],...,[XJ]が実施例1の表[X1],...,[XJ]と同じである。なお、表分割手段505は、ベクトルc0=1,2,...,MTただし、ここでのTは転置を示すの各要素を秘密分散することで生成した表[c0]をJ個の表[X1],...,[XJ]の中に含めてもよい。このように、J個の表とは表[X]に含まれた要素以外を含んでもよい。対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、ベクトルhaの各要素を秘密分散してベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求める。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに、所定の処理を施しても対応が維持されるように対応付けるS310。より具体的には、対応用ベクトル生成部3101,...,310N対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhaを生成し、秘密分散装置1001,...,100Nにベクトルhaの各要素を秘密分散させてベクトル[ha]を求めさせ、ベクトル[ha]をランダム置換させてベクトル[h]を求めさせる。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[Xj]の各レコードに対応付ける。処理用繰返手段570処理用繰返部5701,...,570Nは、bに1を代入し、繰返し処理の初期化を行うS571。処理用ランダム置換手段520は、処理Fbに必要な要素を有する表[Xb1],...,[XbD]を選び、bd=b1,...,bDについて、表[Xbd]とベクトル[hbd]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XbdR]とベクトル[hbdR]とを求めるS520。より具体的には、処理用ランダム置換部5201,...,520N処理用ランダム置換手段520は、処理Fbに必要な要素を有する表[Xb1],...,[XbD]を表[X1],...,[XJ]の中から選ぶ。ここで、Dはbごとに決まる1以上J以下の整数である。例えば、処理F1のときには2つの表を選び、処理F2のときには3つの表を選ぶのであれば、b=1のときはD=2、b=2のときはD=3となる。また、b1,...,bDは、1~Jのいずれかの数であり、b1<...<bDのように順番に並んでいる必要はない。例えば、ソートの処理などで優先度の高い方をbDとし、優先度が低い方をb1としてもよい。そして、処理用ランダム置換部5201,...,520N処理用ランダム置換手段520は、bd=b1,...,bDについて、表[Xbd]の各レコードとベクトル[hbd]の各要素に対して同一の全単射によるランダム置換を秘密分散装置1001,...,100Nに実行させ、ランダム置換された表[XbdR]とベクトル[hbdR]とを求める。なお、表[Xbd]の各レコードとベクトル[hbd]の各要素に対して同一の全単射とは、同じd同士の表[Xbd]の各レコードとベクトル[hbd]の各要素に対して同一の全単射であればよく、dが異なる場合は同一の全単射である必要はない。処理用ベクトル復号手段530は、ベクトル[hb1R],...,[hbDR]を復号し、ベクトルhb1R,...,hbDRを求めるS530。より具体的には、処理用ベクトル復号部5301,...,530N処理用ベクトル復号手段530は、秘密分散装置1001,...,100Nにベクトル[hb1R],...,[hbDR]を復号させ、ベクトルhb1R,...,hbDRを求める。処理用並び替え手段540は、すべてのbiとbdの組合せただし、ここでのiは1,...,Dのいずれかに対してhbiR=hbdRとなるように表[XbdR]のレコードを並び替え、表[Xb1T],...,[XbDT]を得るS540。より具体的には、処理用並び替え部5401,...,540N処理用並び替え手段540は、レコードの順番を維持する表[XbiR]を、表[Xb1R],...,[XbDR]の中から特定する。そして、表[XbiR]以外の表[XbdR]bd≠biのレコードをhbiR=hbdRとなるように並び替え、表[Xb1T],...,[XbDT]を得る。処理用ベクトル対応手段550は、ベクトルhbiRの各要素を秘密分散したベクトル[hbiR]の各要素を表[Xb1T],...,[XbDT]の各レコードに、処理Fbを施しても対応が維持されるように対応付けるS550。より具体的には、処理用ベクトル対応部5501,...,550N処理用ベクトル対応手段550は、秘密分散装置1001,...,100NにベクトルhbiRの各要素を秘密分散させてベクトル[hbiR]をもとめる。そして、ベクトル[hbiR]の各要素を表[Xb1T],...,[XbDT]の各レコードに、処理Fbを施しても対応が維持されるように対応付ける。処理手段560は、ベクトル[hbiR]が対応付けられた表[Xb1T],...,[XbDT]に対して処理Fbを行って、処理Fb後のベクトル[hbiF]が対応付けられた処理Fb後の表[Xb1F],...,[XbD’F]を求める。そして、処理Fb前のJ個の表の中から0個以上、処理Fb後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理Fb後のベクトル[hjbS]と表[X1bS],...,[XJbS]を求めるS560。例えば、D’=Dであり、処理Fb後の表[Xb1F],...,[XbD’F]を、対応する処理Fb前の表[Xb1],...,[XbD]に置き換えるのであれば、J’=Jとなるので、表の数Jは同じままである。また、処理Fb後の表[Xb1F],...,[XbD’F]を単に加えてもよく、この場合はJ’=JD’であり、表の数JはD’だけ増える。より具体的には、処理部5601,...,560N処理手段560は、ベクトル[hbiR]の対応付けを維持したまま表[Xb1T],...,[XbDT]に対して処理Fbを行って、処理Fb後のベクトル[hbiF]が対応付けられた処理Fb後の表[Xb1F],...,[XbD’F]を求める。そして、処理Fb前のJ個の表の中から0個以上、処理Fb後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理Fb後のベクトル[hjbS]と表[X1bS],...,[XJbS]とする。処理用繰返手段570処理用繰返部5701,...,570Nは、b=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],...,[XJbS]を表[X1S],...,[XJS]としてステップS320に進む。Noの場合はベクトル[hjbS]をベクトル[hj]、表[X1bS],...,[XJbS]を表[X1],...,[XJ]とし、ステップS573に進むS572。ステップS573では、処理用繰返手段570処理用繰返部5701,...,570Nは、bにb1を代入し、ステップS520に戻る。対応用ランダム置換手段320は、j=1~Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求めるS320。より具体的には、対応用ランダム置換部3201,...,320N対応用ランダム置換手段320は、j=1~Jについて、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置1001,...,100Nに実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。対応用ベクトル復号手段330は、ベクトル[h1R],...,[hJR]を復号し、ベクトルh1R,...,hJRを求めるS330。より具体的には、対応用ベクトル復号部3301,...,330N対応用ベクトル復号手段330は、秘密分散装置1001,...,100Nにベクトル[h1R],...,[hJR]を復号させ、ベクトルh1R,...,hJRを求める。対応用並び替え手段340は、レコードの順番を維持する表[XiR]以外の表[XjR]ただし、j=1,...,Jかつj≠iのレコードをhjR=hiRとなるように並び替えるS340。より具体的には、対応用並び替え部3401,...,340N対応用並び替え手段340は、表[XiR]ソートの対象となる要素を含んだ表を特定する。そして、表[XiR]以外の表[XjR]ただし、j=1,...,Jかつj≠iのレコードをhjR=hiRとなるように並び替える。実施例3の具体例について説明する。例えば表[X]のM個のレコードは要素としてそれぞれ属性値[vm]、キー[km1],...,[kmB]を有しているとする。そして、キー[km1],...,[kmB]の順にソートを行う場合を説明する。つまり、処理Fbはキー[k1b],...,[kMb]に基づいたソートを行う処理である。表分割手段505は、表[X]を要素[vm],[km1],...,[kmB]ごとに分割して表[v],[k1],...,[kB]を求める。また、ベクトルc0=1,2,...,MTただし、ここでのTは転置を示すの各要素を秘密分散したベクトル[c0]を表[c0]とするS505。この場合は、J=B2であり、表[v]が表[X1]、表[k1]が表[X2]、...、表[kB]が表[XJ-1]、表[c0]が表[XJ]に相当する。対応用ベクトル生成手段310は、ベクトルha=1,2,...,MTただし、ここでのTは転置を示すの各要素を秘密分散したベクトル[ha]を求め、ベクトル[ha]をランダム置換してベクトル[h]を求める。そして、j=1~Jについて、ベクトル[h]と同一のベクトル[hj]の各要素を表[v],[k1],...,[kB],[c0]の各レコードに、所定の処理を施しても対応が維持されるように対応付けるS310。処理用繰返手段570処理用繰返部5701,...,570Nは、bに1を代入し、繰返し処理の初期化を行うS571。処理用ランダム置換手段520は、処理Fbに必要な要素を有する表として表[v],[kb],[cb-1]を選択する。つまり、D=3であり、表[v]が表[Xb1]、表[kb]が表[Xb2]、表[cb-1]が表[Xb3]に相当する。処理用ランダム置換手段520は、表[v]とベクトル[hb1]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[kb]とベクトル[hb2]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[cb-1]とベクトル[hb3]との対応を維持したまま秘密計算でレコード間をランダム置換する。そして、ランダム置換された表[vR],[kbR],[cb-1R]とベクトル[hb1R],[hb2R],[hb3R]とを求めるS520。処理用ベクトル復号手段530は、ベクトル[hb1R],[hb2R],[hb3R]を復号し、ベクトルhb1R,hb2R,hb3Rを求めるS530。処理用並び替え手段540は、すべてのbiとbdの組合せただし、ここでのiは1,...,Dのいずれかに対してhbiR=hbdRとなるように表[vR],[kbR],[cb-1R]のレコードを並び替え、表[vT],[kbT],[cb-1T]を得るS540。処理用ベクトル対応手段550は、ベクトルhbiRの各要素を秘密分散したベクトル[hbiR]の各要素を表[vT],[kbT],[cb-1T]の各レコードに、処理Fbを施しても対応が維持されるように対応付けるS550。処理手段560は、ベクトル[hbiR]が対応付けられた表[vT],[kbT],[cb-1T]に対して処理Fbを行う。例えばFbは、表[cb-1T]を復号して表cb-1Tを求める。そして、表cb-1Tに従って並べ替え、表[kbT]に従って表[vT]をソートして表[vNEW]を求める。また、ベクトルcb=1,2,...,MTただし、ここでのTは転置を示すの各要素を秘密分散して、表[cb]を求める。つまり、処理Fb後のD’個の表は、表[vNEW]と表[cb]であり、D’=2である。そして、表[kb1],...,[kB],[vNEW],[cb]を抽出し、J’個のベクトルとする。つまり、J’=B-b2である。そして、J’を新しいJに更新し、表[vNEW]を新しい表[v]とし、処理Fb後のベクトル[hjbS]と表[kb1],...,[kB],[v],[cb]を求めるS560。処理用繰返手段570は、b=Bかを確認し、Yesの場合はベクトル[hjBS]をベクトル[hjS]としてステップS320に進む。Noの場合はベクトル[hjbS]をベクトル[hj]とし、ステップS573に進むS572。ステップS573では、処理用繰返手段570処理用繰返部5701,...,570Nは、bにb1を代入し、ステップS520に戻る。対応用ランダム置換手段320は、表[v]とベクトル[h1S]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[cB]とベクトル[h2S]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[vR],[cBR]とベクトル[h1R],[h2R]とを求めるS320。対応用ベクトル復号手段330は、ベクトル[h1R],[h2R]を復号し、ベクトルh1R,h2Rを求めるS330。対応用並び替え手段340は、表[cB]を復号してcB=1,2,...,MTただし、ここでのTは転置を示す、かつh1R=h2Rとなるように、表cBと表[vR]のレコードを並び替え、表[vL]を求めるS340。表[vL]が所望の表である。本実施例の秘密マッチングシステムも、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[hj]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。また、表[X]を分割して表[X1],...,[XJ]を求め、所定の処理の前に必要な要素を含む表[Xb1],...,[XbD]を選定した上で、表[Xb1],...,[XbD]に対してのみ所定の処理を行い、所定の処理が終わった後で他の表の中に戻すので、計算効率を改善できる。[秘密計算]上述の説明では、秘密計算については1つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密マッチング装置101,...,10N201,...,20Nまたは301,...,30Nが実行するランダム置換とその他の秘密計算について説明する。なお、以下の説明では秘密マッチング装置10nについて説明するが、秘密マッチング装置20n,30nについても同じである。また、以下の秘密計算に関する説明は、1つの例でありこれに限定されるものではない。本発明の秘密マッチングシステムでは他の秘密計算を用いてもよい。ランダム置換1図7に本発明に利用できる秘密分散装置100nの機能構成例を詳しく示した秘密マッチングシステムを示す。図8にランダム置換の1つ目の処理フロー例を示す。この例では、秘密マッチングシステムは選択手段105も備える。ここで、A1,...,AKを各秘密マッチング装置10nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密マッチング装置10nが記録するk番目の断片とする。なお、数値A1,...,AKが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Akが各々の人の年収を示すような数値群が考えられる。選択手段105は、いずれかの秘密マッチング装置の内部に配置されてもよいし、単独の装置であってもよい。秘密マッチングシステムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置100nは、少なくとも断片置換部110nと再分散部120nと記録部190nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は、N未満の数の秘密マッチング装置10nを選択するS105。例えば、N個の断片のうちN’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がN’個以上N未満の秘密マッチング装置を選べばよい。断片置換手段は、少なくとも断片置換部1101,...,110Nを含んで構成される。そして、選択手段105に選択された秘密マッチング装置10iただし、iは選択された秘密マッチング装置を示す番号の断片置換部110i間で{1,...,K}→{1,...,K}の全単射πを作成し、選択された秘密マッチング装置10iの記録部190iが記録する断片aπkiをk番目の断片にするS110。全単射πは、1~Kを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisherYatesshuffle参考文献1:RichardDurstenfeldAlgorithm235RandompermutationCommunicationsoftheACMarchiveVolume7Issue71964などを用いて作成すればよい。また、全単射πは選択された秘密マッチング装置10i間で生成してもよいし、選択された秘密マッチング装置10iのうちの1つの秘密マッチング装置が生成して、選択された秘密マッチング装置10i間で共有してもよい。再分散手段は、少なくとも再分散部1201,...,120Nを含んで構成される。再分散手段は、断片置換手段によって置換された数値Aπkに対応する断片aπkik番目に置換されているを用いて再分散化して新しい断片bk1,...,bkNを求め、数値Bkの断片とするS120。つまり、Aπk=Bkの関係が成り立つが、選ばれなかった秘密マッチング装置は全単射πを知らないので、Aπk=Bkであることを知らない。なお、各秘密マッチング装置10nの記録部190nは、断片bknを記録するだけでなく、自身が記録しているk番目の断片である断片bknが数値Bkの断片であるという情報も記録する。また、数値B1,...,BKを新しい数値A1,...,AKとし、選択手段で選択する秘密マッチング装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。本発明の秘密マッチングシステムによれば、限定された秘密マッチング装置間で断片をシャッフルする。したがって、選ばれなかった秘密マッチング装置は、全単射πを知らないので、数値A1,...,AKと数値B1,...,BKとの対応が分からない。つまり、特定の秘密マッチング装置からは数値A1,...,AKと数値B1,...,BKとの対応が分からない状態にしたいのであれば、その秘密マッチング装置を選択手段105で選ばないように、選択する秘密マッチング装置をあらかじめ定めればよい。また、選択手段105が選ぶ秘密マッチング装置を変更しながらこの処理を繰り返し、全ての秘密マッチング装置が選ばれなかったことがある状態にすれば、全ての秘密マッチング装置が数値A1,...,AKと対応付けることができない数値B1,...,BKを得ることができる。ランダム置換2次のランダム置換のための秘密マッチングシステムの秘密分散装置100nを詳細に示した機能構成例も図7に示す。図9にランダム置換の2つ目の処理フロー例を示す。この例でも、秘密マッチングシステムは選択手段105も備える。ここで、A1,...,AKを各秘密マッチング装置10nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密マッチング装置10nが記録する数値Akの断片とする。本発明の秘密マッチングシステムは、選択手段105、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置100nは、初期情報分散部130n、初期乗算部140n、断片置換部110n、再分散部120n、確認分散部150n、確認乗算部160n、改ざん検出部170nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105はランダム置換1と同じである。初期情報分散手段は、初期情報分散部1301,...,130Nで構成される。そして、選択手段105に選択された秘密マッチング装置10iの初期情報分散部130iは、秘密マッチング装置101,...,10Nのどれも知らないK個の数値P1,...,PKそれぞれの断片p1n,...,pKnを秘密計算によって求め、記録部190nに記録するS130。具体的には、選択手段105に選択された秘密マッチング装置から、2つ以上の秘密マッチング装置を選定する。そして、選定された秘密マッチング装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、2つの秘密マッチング装置10i,10jを選定しただし、i≠j、秘密マッチング装置10iが生成した数値の断片と、秘密マッチング装置10jが生成した数値の断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密マッチング装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を2つとしたが、2つ以上でもかまわない。初期乗算手段は、初期乗算部1401,...,140Nで構成される。初期乗算部1401,...,140Nは、Sk=Pk×Akである数値Skの断片sk1,...,skNを秘密計算によって求め、記録部1901,...,190Nに分散して記録するS140。断片置換手段と再分散手段は、ランダム置換1と同じである。確認分散手段は、確認分散部1501,...,150Nで構成される。確認分散部1501,...,150Nは、k=1~Kについて、Qk=Pπkである数値Qkの断片qk1,...,qkNを秘密計算によって生成し、記録部1901,...,190Nに分散して記録するS150。具体的には、ステップS130で選定された秘密マッチング装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップS130で選定された秘密マッチング装置10iが数値Pπk用に生成した数値の別の断片新しい断片と、ステップS130で選定された秘密マッチング装置10jが数値Pπk用に生成した数値の別の断片新しい断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Qk=Pπkであり、かつ、全ての秘密マッチング装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密マッチング装置を2つとしたが、ステップS130と同じように2つ以上でもかまわない。確認乗算手段は、確認乗算部1601,...,160Nで構成される。確認乗算部1601,...,160Nは、Tk=Qk×Bkである数値Tkの断片tk1,...,tkNを秘密計算によって求め、記録部1901,...,190Nに分散して記録するS160。改ざん検出手段は、改ざん検出部1701,...,170Nで構成される。改ざん検出部1701,...,170Nは、k=1~Kについて、Tk=Sπkであることを確認するS170。tkn≠sπknの場合には、改ざんがあったとして異常終了する。また、数値B1,...,BKを新しい数値A1,...,AKとし、選択手段で選択する秘密マッチング装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。[その他の秘密計算]ここでは、秘密マッチングシステムが3個の秘密マッチング装置で構成された場合の秘密計算の例を示す。また、秘密マッチング装置101,102,103の番号を固定する必要はないので、秘密マッチング装置10α,10β,10γと表現することにする。つまり、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかである。以下の秘密計算では、秘密マッチング装置10α,10β,10γが分散して記録する数値Aの断片をaγα,aαβ、aαβ,aβγ、aβγ,aγα、数値Bの断片をbγα,bαβ、bαβ,bβγ、bβγ,bγα、数値Cの断片をcγα,cαβ、cαβ,cβγ、cβγ,cγαとする。なお、以下の説明では、Wを2以上のあらかじめ定めた整数とし、計算結果はWで除した余りである。言い換えると、以下の説明の計算式ではmodWを省略している。数値Aの秘密分散1乱数aαβ,aβγを生成する。2aγα=A-aαβ-aβγを計算し、断片をaγα,aαβ、aαβ,aβγ、aβγ,aγαとし、秘密マッチング装置10α,10β,10γに分散して記録する。数値Aの復元1秘密マッチング装置10αは秘密マッチング装置10βにaγαを送信し、秘密マッチング装置10γにaαβを送信する。秘密マッチング装置10βは秘密マッチング装置10γにaαβを送信し、秘密マッチング装置10αにaβγを送信する。秘密マッチング装置10γは秘密マッチング装置10αにaβγを送信し、秘密マッチング装置10βにaγαを送信する。2秘密マッチング装置10αは秘密マッチング装置10βから受信したaβγと秘密マッチング装置10γから受信したaβγとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密マッチング装置10βは秘密マッチング装置10γから受信したaγαと秘密マッチング装置10αから受信したaγαとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密マッチング装置10γは秘密マッチング装置10αから受信したaαβと秘密マッチング装置10βから受信したaαβとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。C=ABの秘密計算1秘密マッチング装置10αはcγα,cαβ=aγαbγα,aαβbαβを計算して記録し、秘密マッチング装置10βはcαβ,cβγ=aαβbαβ,aβγbβγを計算して記録し、秘密マッチング装置10γはcβγ,cγα=aβγbβγ,aγαbγαを計算して記録する。C=A-Bの秘密計算1秘密マッチング装置10αはcγα,cαβ=aγα-bγα,aαβ-bαβを計算して記録し、秘密マッチング装置10βはcαβ,cβγ=aαβ-bαβ,aβγ-bβγを計算して記録し、秘密マッチング装置10γはcβγ,cγα=aβγ-bβγ,aγα-bγαを計算して記録する。C=ASの秘密計算ただし、Sは既知の定数1秘密マッチング装置10αはcγα,cαβ=aγαS,aαβを計算して記録し、秘密マッチング装置10γはcβγ,cγα=aβγ,aγαSを計算して記録する。秘密マッチング装置10βの処理はない。C=ASの秘密計算ただし、Sは既知の定数1秘密マッチング装置10αはcγα,cαβ=aγαS,aαβSを計算して記録し、秘密マッチング装置10βはcαβ,cβγ=aαβS,aβγSを計算して記録し、秘密マッチング装置10γはcβγ,cγα=aβγS,aγαSを計算して記録する。C=ABの秘密計算1秘密マッチング装置10αは、乱数r1,r2,cγαを生成し、cαβ=aγαaαβbγαbαβ-r1-r2-cγαを計算する。そして、秘密マッチング装置10αは、秘密マッチング装置10βにr1,cαβを、秘密マッチング装置10γにr2,cγαを送信する。2秘密マッチング装置10βは、y=aαβbβγaβγbαβr1を計算し、秘密マッチング装置10γに送信する。3秘密マッチング装置10γは、z=aβγbγαaγαbβγr2を計算し、秘密マッチング装置10αに送信する。4秘密マッチング装置10βと秘密マッチング装置10γは、それぞれcβγ=yzaβγbβγを計算する。5秘密マッチング装置10αはcγα,cαβを記録し、秘密マッチング装置10βはcαβ,cβγを記録し、秘密マッチング装置10γはcβγ,cγαを記録する。ビットAの否定C=1-Aの秘密計算秘密マッチング装置10αはcγα,cαβ=1-aγα,-aαβmodWを計算して記録し、秘密マッチング装置10βはcαβ,cβγ=-aαβmodW,-aβγmodWを計算して記録し、秘密マッチング装置10γはcβγ,cγα=-aβγmodW,1-aγαを計算して記録する。ビットの論理積C=A∧B=ABの秘密計算秘密マッチング装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行う。ビットの論理和C=A∨B=AB-ABの秘密計算1秘密マッチング装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C’=ABの結果として、秘密マッチング装置10αが断片cγα’,cαβ’を、秘密マッチング装置10βが断片cαβ’,cβγ’を、秘密マッチング装置10γが断片cβγ’,cγα’を記録する。また、秘密マッチング装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行い、C=ABの結果として、秘密マッチング装置10αが断片cγα,cαβを、秘密マッチング装置10βが断片cαβ,cβγを、秘密マッチング装置10γが断片cβγ,cγαを記録する。2秘密マッチング装置10α,10β,10γは、S=-1として整数の乗算C=ASmodWの秘密計算ただし、Sは既知の定数と同じ処理を行い、C’’’=-Cの結果として、秘密マッチング装置10αが断片cγα’’’,cαβ’’’を、秘密マッチング装置10βが断片cαβ’’’,cβγ’’’を、秘密マッチング装置10γが断片cβγ’’’,cγα’’’を記録する。3秘密マッチング装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C=C’C’’’の結果として、秘密マッチング装置10αが断片cγα,cαβを、秘密マッチング装置10βが断片cαβ,cβγを、秘密マッチング装置10γが断片cβγ,cγαを記録する。ビットの排他的論理和C=A[∨]B=AB-2ABの秘密計算1秘密マッチング装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C’=ABの結果として、秘密マッチング装置10αが断片cγα’,cαβ’を、秘密マッチング装置10βが断片cαβ’,cβγ’を、秘密マッチング装置10γが断片cβγ’,cγα’を記録する。また、秘密マッチング装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行い、C=ABの結果として、秘密マッチング装置10αが断片cγα,cαβを、秘密マッチング装置10βが断片cαβ,cβγを、秘密マッチング装置10γが断片cβγ,cγαを記録する。2秘密マッチング装置10α,10β,10γは、S=-2として整数の乗算C=ASmodWの秘密計算ただし、Sは既知の定数の秘密計算と同じ処理を行い、C’’’=-2Cの結果として、秘密マッチング装置10αが断片cγα’’’,cαβ’’’を、秘密マッチング装置10βが断片cαβ’’’,cβγ’’’を、秘密マッチング装置10γが断片cβγ’’’,cγα’’’を記録する。3秘密マッチング装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C=C’C’’’の結果として、秘密マッチング装置10αが断片cγα,cαβを、秘密マッチング装置10βが断片cαβ,cβγを、秘密マッチング装置10γが断片cβγ,cγαを記録する。ビットAn,n=0,...,N-1の整数変換の秘密計算ビットAnの整数変換とは、を求めることである。また、秘密マッチング装置10α,10β,10γが分散して記録するビットAnの断片をanγα,anαβ、anαβ,anβγ、anβγ,anγαとする。秘密マッチング装置10αは、を計算して記録し、秘密マッチング装置10βはを計算して記録し、秘密マッチング装置10γはを計算して記録する。Nビットの整数Aの二進数変換の秘密計算xnは、xの下位n1番目のビットを示すものとする。1n=0からN-1について、秘密マッチング装置10βがaαβaβγmodWnを秘密分散し、秘密マッチング装置10α,10β,10γがaαβaβγmodWnの断片bnγα,bnαβ、bnαβ,bnβγ、bnβγ,bnγαを分散して記録する。n=0からN-1について、秘密マッチング装置10γがaγαnを秘密分散し、秘密マッチング装置10α,10β,10γがaγαnの断片aγαnγα,aγαnαβ、aγαnαβ,aγαnβγ、aγαnβγ,aγαnγαを分散して記録する。2cγα=0とし、n=0からN-1について2-1から2-3の処理を繰返し実行する。2-1dn=bnaγαn-2bnaγαnの秘密計算を実行し、dnの断片を分散して記録する。2-2an=dncn-2dncnの秘密計算を実行し、anの断片を分散して記録する。2-3n<N-1であれば、cn1=bnaγαndncn-bnaγαndncnの秘密計算を実行し、cn1の断片を分散して記録する。[プログラム、記録媒体]上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"