"N個の秘密分散装置で構成された秘密分散システムであって、Nを3以上の整数、nを1以上N以下の整数、Mを1以上の整数、mを1以上M以下の整数、Kを2以上の整数、kを1以上K以下の整数、数値A11,...,AK1,...,A1M,...,AKMを各秘密分散装置が断片を分散して記録するK×M個の数値、数値Ak1,...,AkMを対応付けられたk番目の数値群、aknmをn番目の秘密分散装置が記録する数値Akmの断片、iをN個の秘密分散装置の中から選択された秘密分散装置を示すための1以上N以下の中の一部の整数とし、2以上N未満の数の秘密分散装置を選択する選択手段と、前記選択手段で選択された秘密分散装置の間で{1,...,K}→{1,...,K}の全単射πを作成し、選択されたi番目の秘密分散装置が記録する対応付けられたπk番目の数値群の断片aπki1,...,aπkiMをそれぞれ対応付けられたk番目の数値群の断片にする断片置換手段と、前記断片置換手段によって置換された数値Aπk1,...,AπkMに対応する断片aπki1,...,aπkiMを用いて再分散化して新しい断片bk11,...,bkN1,...,bk1M,...,bkNMを求め、数値Bk1,...,BkMの断片とする再分散手段と、を備える秘密分散システム。請求項1記載の秘密分散システムであって、M=1である秘密分散システム。請求項2記載の秘密分散システムであって、N個の秘密分散装置のどれも知らないK個の数値P1,...,PKそれぞれの断片を秘密計算によって求め、n番目の秘密分散装置に断片p1n,...,pKnを記録する初期情報分散手段と、N個の秘密分散装置で、Sk=Pk×Ak1である数値Skの断片sk1,...,skNを秘密計算によって求め、N個の秘密分散装置に分散して記録する初期乗算手段と、k=1~Kについて、Qk=Pπkである数値Qkの断片qk1,...,qkNを秘密計算によって生成し、N個の秘密分散装置に分散して記録する確認分散手段と、N個の秘密分散装置で、Tk=Qk×Bk1である数値Tkの断片tk1,...,tkNを秘密計算によって求め、N個の秘密分散装置に分散して記録する確認乗算手段と、k=1~Kについて、Tk=Sπkであることを確認する改ざん検出手段、も備える秘密分散システム。請求項1記載の秘密分散システムであって、N=3、α,β,γを1,2,3と2,3,1と3,1,2のいずれかの組み合わせ、数値Akm=akαβmakβγmakγαmの3つの断片をakγαm,akαβmとakαβm,akβγmとakβγm,akγαm、前記の3つの断片は3つの秘密分散装置に分散して記録されているとし、前記選択手段は、2つの秘密分散装置を選択し、選択された秘密分散装置の一方を第1の秘密分散装置、他方を第2の秘密分散装置、選択されなかった秘密分散装置を第3の秘密分散装置とし、前記断片置換手段は、第1の秘密分散装置が記録する数値Akmの断片をak1m=ak31m,ak12m、第2の秘密分散装置が記録する数値Akmの断片をak2m=ak12m,ak23m、第3の秘密分散装置が記録する数値Akmの断片をak3m=ak23m,ak31mとし、第1の秘密分散装置または第2の秘密分散装置で{1,...,K}→{1,...,K}の全単射πを作成し、第1の秘密分散装置が記録する対応付けられたπk番目の数値群の断片aπk11,...,aπk1Mを対応付けられたk番目の数値群の断片にし、第2の秘密分散装置が記録する対応付けられたπk番目の数値群の断片aπk21,...,aπk2Mを対応付けられたk番目の数値群の断片にし、前記再分散手段として、各秘密分散装置が、第1の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk311,...,bk31Mを生成し、第3の秘密分散装置に送信する第1乱数生成部と、第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk231,...,bk23Mを生成し、第3の秘密分散装置に送信する第2乱数生成部と、第1の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてxkm=bk31m-aπk31mを計算し、xk1,...,xkMを第2の秘密分散装置に送信する第1計算部と、第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてykm=bk23m-aπk23mを計算し、yk1,...,ykMを第1の秘密分散装置に送信する第2計算部と、第1の秘密分散装置または第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてbk12m=aπk12m-xkm-ykmを計算する第3計算部と、第1の秘密分散装置のときにはbk31m,bk12mを断片bk1mとし、第2の秘密分散装置のときにはbk12m,bk23mを断片bk2mとし、第3の秘密分散装置のときにはbk23m,bk31mを断片bk3mとする断片更新部と、を備え、断片bk1m、bk2m、bk3mを数値Bkmの断片として記録する秘密分散システム。請求項4記載の秘密分散システムであって、M=1である秘密分散システム。請求項5記載の秘密分散システムであって、第1の秘密分散装置でK個のランダムな値R11,...,R1Kを生成し、第2の秘密分散装置でK個のランダムな値R21,...,R2Kを生成し、前記3つの秘密分散装置で、R1kの断片r1k31,r1k12、r1k12,r1k23、r1k23,r1k31と、R2kの断片r2k31,r2k12、r2k12,r2k23、r2k23,r2k31とを秘密分散して記録し、前記3つの秘密分散装置で、Pk=R1kR2kである数値Pkの断片pk31,pk12、pk12,pk23、pk23,pk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する初期情報分散手段と、前記3つの秘密分散装置で、Sk=Pk×Ak1である数値Skの断片sk31,sk12、sk12,sk23、sk23,sk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する初期乗算手段と、前記の数値R1πkの別の断片r’1πk31,r’1πk12、r’1πk12,r’1πk23、r’1πk23,r’1πk31と、前記の数値R2πkの別の断片r’2πk31,r’2πk12、r’2πk12,r’2πk23、r’2πk23,r’2πk31とを前記3つの秘密分散装置に分散して記録し、前記3つの秘密分散装置で、Qk=R1πkR2πkである数値Qkの断片qk31,qk12、qk12,qk23、qk23,qk31を当該別の断片を用いて秘密計算によって求め、前記3つの秘密分散装置に分散して記録する確認分散手段と、前記3つの秘密分散装置で、Tk=Qk×Bk1である数値Tkの断片tk31,tk12、tk12,tk23、tk23,tk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する確認乗算手段と、第1の秘密分散装置が記録する断片をsk1=sk31,sk12、tk1=tk31,tk12とし、第2の秘密分散装置が記録する断片をsk2=sk12,sk23、tk2=tk12,tk23とし、第3の秘密分散装置が記録する断片をsk3=sk23,sk31、tk3=tk23,tk31とし、各秘密分散装置が、第1の秘密分散装置のときに、ランダムな値であるukを生成し、第2の秘密分散装置に送信する第3乱数生成部と、第2の秘密分散装置のときに、ランダムな値であるvkを生成し、第1の秘密分散装置に送信する第4乱数生成部と、第1の秘密分散装置のときに、dk=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置に送信する第4計算部と、第2の秘密分散装置のときに、ek=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置に送信する第5計算部と、第3の秘密分散装置のときに、dk=ekであることを確認し、異なっていれば処理を中止する第1確認部と、第1の秘密分散装置のときに、fk=sπk31-tk31ukを計算し、第3の秘密分散装置に送信する第6計算部と、第2の秘密分散装置のときに、gk=sπk23-tk23vkを計算し、第3の秘密分散装置に送信する第7計算部と、第3の秘密分散装置のときに、fkgkdk=0であることを確認し、異なっていれば処理を中止する第2確認部と、を備える秘密分散システム。請求項4記載の秘密分散システムの中の秘密分散装置であって、第1の秘密分散装置として選ばれたときには記録する数値Akmの断片をak1m=ak31m,ak12m、第2の秘密分散装置として選ばれたときには記録する数値Akmの断片をak2m=ak12m,ak23m、第3の秘密分散装置として選ばれたときには記録する数値Akmの断片をak3m=ak23m,ak31mとし、第1の秘密分散装置または第2の秘密分散装置として選ばれたときは、{1,...,K}→{1,...,K}の全単射πを作成し、対応付けられたπk番目の数値群の断片を対応付けられたk番目の数値群の断片にする断片置換部と、第1の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk311,...,bk31Mを生成し、第3の秘密分散装置に送信する第1乱数生成部と、第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk231,...,bk23Mを生成し、第3の秘密分散装置に送信する第2乱数生成部と、第1の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてxkm=bk31m-aπk31mを計算し、xk1,...,xkMを第2の秘密分散装置に送信する第1計算部と、第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてykm=bk23m-aπk23mを計算し、yk1,...,ykMを第1の秘密分散装置に送信する第2計算部と、第1の秘密分散装置または第2の秘密分散装置のときには、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてbk12m=aπk12m-xkm-ykmを計算する第3計算部と、第1の秘密分散装置のときにはbk31m,bk12mを断片bk1mとし、第2の秘密分散装置のときにはbk12m,bk23mを断片bk2mとし、第3の秘密分散装置のときにはbk23m,bk31mを断片bk3mとする断片更新部と、を備える秘密分散装置。請求項7記載の秘密分散装置であって、M=1である秘密分散装置。Kを2以上の整数、kを1以上K以下の整数、Mを1以上の整数、mを1以上M以下の整数、A11,...,AK1,...,A1M,...,AKMをK×M個の数値、α,β,γを1,2,3と2,3,1と3,1,2のいずれかの組み合わせ、数値Akm=akαβmakβγmakγαmの3つの断片をakγαm,akαβmとakαβm,akβγmとakβγm,akγαm、対応付けられたk番目の数値群をAk1,...,AkMとし、前記断片を分散して記録する3つの秘密分散装置を用いた秘密分散方法であって、2つの秘密分散装置を選択し、選択された秘密分散装置の一方を第1の秘密分散装置、他方を第2の秘密分散装置、選択されなかった秘密分散装置を第3の秘密分散装置する選択ステップと、第1の秘密分散装置が記録する数値Akmの断片をak1m=ak31m,ak12m、第2の秘密分散装置が記録する数値Akmの断片をak2m=ak12m,ak23m、第3の秘密分散装置が記録する数値Akmの断片をak3m=ak23m,ak31mとし、第1の秘密分散装置または第2の秘密分散装置で{1,...,K}→{1,...,K}の全単射πを作成し、第1の秘密分散装置が記録する対応付けられたπk番目の数値群の断片aπk11,...,aπk1Mを対応付けられたk番目の数値群の断片にし、第2の秘密分散装置が記録する対応付けられたπk番目の数値群の断片aπk21,...,aπk2Mを対応付けられたk番目の数値群の断片にする断片置換ステップと、第1の秘密分散装置が、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk311,...,bk31Mを生成し、第3の秘密分散装置に送信する第1乱数生成ステップと、第2の秘密分散装置が、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk231,...,bk23Mを生成し、第3の秘密分散装置に送信する第2乱数生成ステップと、第1の秘密分散装置が、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてxkm=bk31m-aπk31mを計算し、xk1,...,xkMを第2の秘密分散装置に送信する第1計算ステップと、第2の秘密分散装置が、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてykm=bk23m-aπk23mを計算し、yk1,...,ykMを第1の秘密分散装置に送信する第2計算ステップと、第1の秘密分散装置と第2の秘密分散装置が、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてbk12m=aπk12m-xkm-ykmを計算する第3計算ステップと、第1の秘密分散装置がbk31m,bk12mを断片bk1mとし、第2の秘密分散装置がbk12m,bk23mを断片bk2mとし、第3の秘密分散装置がbk23m,bk31mを断片bk3mとする断片更新ステップと、を有する秘密分散方法。請求項9記載の秘密分散方法であって、M=1である秘密分散方法。請求項10記載の秘密分散方法であって、第1の秘密分散装置がK個のランダムな値R11,...,R1Kを生成し、第2の秘密分散装置がK個のランダムな値R21,...,R2Kを生成し、前記3つの秘密分散装置がR1kの断片r1k31,r1k12、r1k12,r1k23、r1k23,r1k31とR2kの断片r2k31,r2k12、r2k12,r2k23、r2k23,r2k31とを秘密分散して記録し、前記3つの秘密分散装置がPk=R1kR2kである数値Pkの断片pk31,pk12、pk12,pk23、pk23,pk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する初期情報分散ステップと、前記3つの秘密分散装置が、Sk=Pk×Ak1である数値Skの断片sk31,sk12、sk12,sk23、sk23,sk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する初期乗算ステップと、前記3つの秘密分散装置が、請求項10記載の秘密分散システムによって得られた断片bk1、bk2、bk3を数値Bk1の断片として記録する秘密分散更新ステップと、前記の数値R1πkの別の断片r’1πk31,r’1πk12、r’1πk12,r’1πk23、r’1πk23,r’1πk31と、前記の数値R2πkの別の断片r’2πk31,r’2πk12、r’2πk12,r’2πk23、r’2πk23,r’2πk31とを前記3つの秘密分散装置に分散して記録し、前記3つの秘密分散装置で、Qk=R1πkR2πkである数値Qkの断片qk31,qk12、qk12,qk23、qk23,qk31を当該別の断片を用いて秘密計算によって求め、前記3つの秘密分散装置に分散して記録する確認分散ステップと、前記3つの秘密分散装置が、Tk=Qk×Bk1である数値Tkの断片tk31,tk12、tk12,tk23、tk23,tk31を秘密計算によって求め、前記3つの秘密分散装置に分散して記録する確認乗算ステップと、第1の秘密分散装置が記録する断片をsk1=sk31,sk12、tk1=tk31,tk12とし、第2の秘密分散装置が記録する断片をsk2=sk12,sk23、tk2=tk12,tk23とし、第3の秘密分散装置が記録する断片をsk3=sk23,sk31、tk3=tk23,tk31とし、第1の秘密分散装置が、ランダムな値であるukを生成し、第2の秘密分散装置に送信する第3乱数生成ステップと、第2の秘密分散装置が、ランダムな値であるvkを生成し、第1の秘密分散装置に送信する第4乱数生成ステップと、第1の秘密分散装置が、dk=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置に送信する第4計算ステップと、第2の秘密分散装置が、ek=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置に送信する第5計算ステップと、第3の秘密分散装置が、dk=ekであることを確認し、異なっていれば処理を中止する第1確認ステップと、第1の秘密分散装置が、fk=sπk31-tk31ukを計算し、第3の秘密分散装置に送信する第6計算ステップと、第2の秘密分散装置が、gk=sπk23-tk23vkを計算し、第3の秘密分散装置に送信する第7計算ステップと、第3の秘密分散装置が、fkgkdk=0であることを確認し、異なっていれば処理を中止する第2確認ステップと、を有する秘密分散方法。請求項9から11のいずれかに記載の秘密分散方法であって、前記断片更新ステップで得られた断片bk1m、bk2m、bk3mを新しい断片ak1m、ak2m、ak3mとし、前記断片置換ステップで、あらかじめ定めた全ての組合せで前記秘密分散装置を選択するまで、前記の秘密分散方法を繰り返すことを特徴とする秘密分散方法。請求項12記載の秘密分散方法を用いた秘密ソート方法であって、請求項12記載の秘密分散方法によって断片を分散して記録した複数の数値に対して、3つの秘密分散装置が、2つの数値を選択し、当該2つの数値の大小を秘密計算によって比較する比較ステップと、秘密分散装置のそれぞれが、前記比較ステップの結果に基づいて数値の断片を入れ替える交換ステップと、を有する秘密ソート方法。請求項1から6のいずれかに記載の秘密分散システムの各秘密分散装置としてコンピュータを機能させる秘密分散プログラム。しかしながら、従来技術はデータの対応を隠したまま複数のデータをランダムに置換できないという課題がある。本発明の目的は、入力された複数のデータと対応つけることができないデータを出力する秘密計算技術を提供することである。本発明は秘密分散に関する。一般に、k,n-秘密分散では、秘密分散システムが2つのパラメータk,nを持っており、秘密にしたい値をn個に分割し、そのうちk個未満を集めても元の値に関する情報は漏れないが、k個以上を集めると元の値を復元できる。本発明の秘密分散システムは、N個の秘密分散装置R1,...,RNで構成される。ここで、Nを3以上の整数、nを1以上N以下の整数、Mを1以上の整数、mを1以上M以下の整数、Kを2以上の整数、kを1以上K以下の整数、数値A11,...,AK1,...,A1M,...,AKMを各秘密分散装置が断片を分散して記録するK×M個の数値、数値Ak1,...,AkMを対応付けられたk番目の数値群、aknmをn番目の秘密分散装置が記録する数値Akmの断片とする。本発明の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。選択手段は、2以上N未満の数の秘密分散装置を選択する。断片置換手段は、選択された秘密分散装置の間で{1,...,K}→{1,...,K}の全単射πを作成し、選択された秘密分散装置Riただし、iは選択された秘密分散装置を示す番号が記録する対応付けられたπk番目の数値群の断片aπki1,...,aπkiMをそれぞれ対応付けられたk番目の数値群の断片にする。再分散手段は、断片置換手段によって置換された数値Aπk1,...,AπkMに対応する断片aπki1,...,aπkiMを用いて再分散化して新しい断片bk11,...,bkN1,...,bk1M,...,bkNMを求める以下、これを再分散化と呼ぶ。なお、対応つけられた数値群の対応を維持したまま数値群を再分散化する場合は、同一の全単射πを用いて、対応つけられた数値群の各数値の断片を置換すればよい。また、本発明の秘密分散システムは、初期情報分散手段、初期乗算手段、確認分散手段、確認乗算手段、改ざん検出手段も備えてもよい。初期情報分散手段は、秘密分散装置R1,...,RNのどれも知らないK個の数値P1,...,PKそれぞれの断片p1n,...,pKnを秘密計算によって求め、秘密分散装置Rnに記録させる。初期乗算手段は、秘密分散装置R1,...,RNで、Sk=Pk×Ak1である数値Skの断片sk1,...,skNを秘密計算によって求め、秘密分散装置R1,...,RNに分散して記録する。確認分散手段は、k=1~Kについて、Qk=Pπkである数値Qkの断片qk1,...,qkNを秘密計算によって生成し、秘密分散装置R1,...,RNに分散して記録させる。確認乗算手段は、秘密分散装置R1,...,RNで、Tk=Qk×Bk1である数値Tkの断片tk1,...,tkNを秘密計算によって求め、秘密分散装置R1,...,RNに分散して記録する。改ざん検出手段は、k=1~Kについて、Tk=Sπkであることを確認する。例えば、3つの秘密分散装置で構成する場合であれば、k番目の対応つけられた数値群のm番目の数値Akm=akαβmakβγmakγαmただし、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかの3つの断片をakγαm,akαβm、akαβm,akβγm、akβγm,akγαmとする。秘密分散装置が、第1の秘密分散装置として選ばれたときには記録する断片をak1m=ak31m,ak12m、第2の秘密分散装置として選ばれたときには記録する断片をak2m=ak12m,ak23m、第3の秘密分散装置として選ばれたときには記録する断片をak3m=ak23m,ak31mとする。そして、各秘密分散装置は、断片置換部、第1乱数生成部、第2乱数生成部、第1計算部、第2計算部、第3計算部、断片更新部を備えればよい。断片置換部は、第1の秘密分散装置または第2の秘密分散装置として選ばれたときは、{1,...,K}→{1,...,K}の全単射πを作成し、πk番目の対応つけられた数値群の各数値の断片をk番目の対応つけられた数値群の各数値の断片にする。第1乱数生成部は、第1の秘密分散装置のときには、移動後のk番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるbk311,...,bk31Mを生成し、第3の秘密分散装置に送信する。第2乱数生成部は、第2の秘密分散装置のときには、k番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるbk231,...,bk23Mを生成し、第3の秘密分散装置に送信する。第1計算部は、第1の秘密分散装置のときには、k番目の対応つけられた数値群の各数値の断片の再分散化のために、m=1~Mについてxkm=bk31m-aπk31mを計算し、第2の秘密分散装置に送信する。第2計算部は、第2の秘密分散装置のときには、k番目の対応つけられた数値群の各数値の断片の再分散化のために、m=1~Mについてykm=bk23m-aπk23mを計算し、第1の秘密分散装置に送信する。第3計算部は、第1の秘密分散装置または第2の秘密分散装置のときには、k番目の対応つけられた数値群の各数値の断片の再分散化のために、m=1~Mについてbk12m=aπk12m-xkm-ykmを計算する。断片更新部は、第1の秘密分散装置のときにはbk31m,bk12mを断片bk1mとし、第2の秘密分散装置のときにはbk12m,bk23mを断片bk2mとし、第3の秘密分散装置のときにはbk23m,bk31mを断片bk3mとする。なお、全ての秘密分散装置の断片置換部で、秘密分散システムの断片置換手段が構成される。また、第1乱数生成部、第2乱数生成部、第1計算部、第2計算部、第3計算部、断片更新部で、秘密分散システムの再分散手段が構成される。本発明の秘密分散システムによれば、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値A11,...,AK1,...,A1M,...,AKMと数値B11,...,BK1,...,B1M,...,BKMとの対応が分からない。本発明を用いることにより、クイックソートなどの比較に基づくソーティングアルゴリズムを、比較回数を増やすことなく秘密計算上で実現できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。課題を解決するための手段では、数値A11,...,AK1,...,A1M,...,AKMを各秘密分散装置が断片を分散して記録するK×M個の数値、数値Ak1,...,AkMを対応付けられたk番目の数値群、aknmをn番目の秘密分散装置が記録する数値Akmの断片として説明した。本実施例では、まず本発明の理解を助けるために、M=1の場合について説明し、その後Mを1に限定しない場合について説明する。また、M=1の場合の説明では、Ak1をAkと、akn1をaknと表現する。[限定シャッフル]図1に実施例1の秘密分散システムの機能構成例を示す。図2に実施例1の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク1000に接続されたN個Nは3以上の整数、nは1以上N以下の整数の秘密分散装置1001,...,100Nと選択手段105で構成される。ここで、A1,...,AKを各秘密分散装置100nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密分散装置100nが記録するk番目の断片とする。なお、数値A1,...,AKが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Akが各々の人の年収を示すような数値群が考えられる。選択手段105は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。本実施例の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置100nは、少なくとも断片置換部110nと再分散部120nと記録部190nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は、N未満の数の秘密分散装置を選択するS105。例えば、N個の断片のうちN’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がN’個以上N未満の秘密分散装置を選べばよい。断片置換手段は、少なくとも断片置換部1101,...,110Nを含んで構成される。そして、選択手段105に選択された秘密分散装置100iただし、iは選択された秘密分散装置を示す番号の断片置換部110i間で{1,...,K}→{1,...,K}の全単射πを作成し、選択された秘密分散装置100iの記録部190iが記録する断片aπkiをk番目の断片にするS110。全単射πは、1~Kを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisherYatesshuffle参考文献1:RichardDurstenfeldAlgorithm235RandompermutationCommunicationsoftheACMarchiveVolume7Issue71964などを用いて作成すればよい。また、全単射πは選択された秘密分散装置100i間で生成してもよいし、選択された秘密分散装置100iのうちの1つの秘密分散装置が生成して、選択された秘密分散装置100i間で共有してもよい。再分散手段は、少なくとも再分散部1201,...,120Nを含んで構成される。再分散手段は、断片置換手段によって置換された数値Aπkに対応する断片aπkik番目に置換されているを用いて再分散化して新しい断片bk1,...,bkNを求め、数値Bkの断片とするS120。つまり、Aπk=Bkの関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Aπk=Bkであることを知らない。なお、各秘密分散装置100nの記録部190nは、断片bknを記録するだけでなく、自身が記録しているk番目の断片である断片bknが数値Bkの断片であるという情報も記録する。また、数値B1,...,BKを新しい数値A1,...,AKとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。本発明の秘密分散システムによれば、限定された秘密分散装置間で断片をシャッフルする。したがって、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値A1,...,AKと数値B1,...,BKとの対応が分からない。つまり、特定の秘密分散装置からは数値A1,...,AKと数値B1,...,BKとの対応が分からない状態にしたいのであれば、その秘密分散装置を断片置換部で選ばないように、選択する秘密分散装置をあらかじめ定めればよい。また、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値A1,...,AKと対応つけることができない数値B1,...,BKを得ることができる。[再分散]上述の限定シャッフルの説明では、再分散については詳しく説明しなかった。ここでは、再分散の方法について説明する。再分散の方法としては、参考文献2AmirHerzbergStanislawJareckiHugoKrawczykandMotiYungProactivesecretsharingorHowtocopewithperpetualleakageInDonCoppersmitheditorCRYPTO1995volume963ofLNCSpages339352Springer1995の33節に示された更新方法と、参考文献3HaiyunLuoandSongwuLuUbiquitousandrobustauthenticationservicesforadhocwirelessnetworksInUCLACSDTR2000302000の61節に示された再作成方法を用いる。選択手段105が選択した秘密計算装置間で参考文献2の更新方法を用いて新しい断片を生成し、その後、参考文献3の再作成方法を用いて選択手段105が選択しなかった秘密計算装置の新しい断片を生成する。参考文献2の更新方法を、本件に適用したアルゴリズムを以下に示す。選択手段105がN’個の秘密分散装置を選択したとする。そして、iとjは選択された秘密分散装置を示す番号1~Nの中から選ばれたN’個の数の中のいずれかであって、j≠iとする。また、値z1,...,zNはあらかじめ決められた値であり、すべての秘密分散装置間で共有されているとする。1すべての秘密分散装置100iは、N’-1個の乱数ui,1,ui,2,...,ui,N’-1を作成する。2すべての秘密分散装置100iは、Ziz:=0ui,1zui,2z2...ui,N’-1zN’-1を定める。3すべての秘密分散装置100iは、選択された他の秘密分散装置100jN’-1個存在するのすべてに対して、それぞれZizjの値を送信する。4すべての秘密分散装置100iは、選択された他の秘密分散装置100jN’-1個存在するから受け取ったすべてのZjziの和をZziとし、新しい断片bkiを置換された断片aπkiを用いて、bki=aπkiZziのように求める。次に、参考文献3の再作成方法を、本件に適用したアルゴリズムを以下に示す。hは選択されなかった秘密分散装置を示す番号1~Nの中から選ばれなかったN-N’個の数のなかのいずれかとする。また、Lijz=z-zj/zi-zjとし、Lizは、すべてのjについてのLijzの積とする。5すべての秘密分散装置100iは、i<jであるjと、選択されなかった秘密分散装置100hのすべての組み合わせに対して、乱数vi,jhを生成する。6すべての秘密分散装置100iは、vi,jhを秘密分散装置100jに送信する。7すべての秘密分散装置100iは、すべての選択されなかった秘密分散装置100hについて、j<iのすべての乱数vi,jhの和をVhとし、i<jのすべての乱数vi,jhの和をVh-とし、値whiを、whi=bkiLizhVh-Vh-のように求め、秘密分散装置100hに値whiを送信する。8すべての秘密分散装置100hは、受信したすべての値whiの和を新しい断片bkhとする。上述のように、1~4の処理で、すべての選択された秘密分散装置が、新しい断片を記録する。5~8の処理で、すべての選択されなかった秘密分散装置が、新しい断片を記録する。なお、3と6の処理を同時に行えば、処理の高速化を図ることができる。具体的には、1、2、5の処理をまず行い、3と6を同時に行い、4、7、8の処理を行えばよい。[ソート]図3に実施例1の秘密分散システムでの数値のソートの処理フローを示す。上述の方法によって初期の数値A1,...,AKと対応つけることができない新しい数値A1,...,AKを得ているS101。ソートも行う場合は、秘密分散装置100nは、比較部210nと交換部220nも備える。比較部2101,...,210Nは、2つの数値を選択し、当該2つの数値の大小を秘密計算によって比較するS210。交換部2201,...,220Nは、それぞれ比較部2101,...,210Nでの比較結果に基づいて、0組または1組または複数組の数値の断片を入れ替えるS220。そして、全ての数値に対するソート処理が終わるまで、ステップS210とS220比較、交換、組合せの変更などの必要な処理を繰り返せばよいS211,S212。ステップS210の比較結果は、全ての秘密分散装置の次の処理に必要な情報なので全ての秘密分散装置が知る情報である。しかし、ステップS101によって全ての秘密分散装置が初期の数値A1,...,AKと対応できなくなった新しい数値A1,...,AKに対して処理しているので、初期の数値A1,...,AKに関する情報は漏れない。さらに、比較結果は、ソートの出力という公開情報から計算可能な情報でもある。そのため、本実施例のプロトコル全体で見ても、比較結果が開示されることは必要以上の情報を漏らしたことにはならない。なお、より具体的には、ソートの部分ステップS210,S220,S211,S212には図4に示すクイックソートのアルゴリズムを適用すればよい。この場合もA[i]とA[j]とを比較する処理はA[i]とA[j]の値を秘匿したままで行い、比較結果は公開される。この方法の場合、比較回数は元のクイックソートと同じであり、平均ONlogN回である。また、この他にも、数値の大小比較の処理と配列の2つの要素を入れ替える処理で構成できるソーティングアルゴリズムにも本実施例は適用できる。このように、本実施例の秘密分散システムを用いれば、比較と要素の入れ替えからなるソーティングアルゴリズムを比較回数を増やすことなく秘密計算で実現できる。[限定シャッフルの変形例]次に、Mを1に限定しない場合について説明する。Mは1以上の整数、mは1以上M以下の整数とする。A1,...,AMはそれぞれK個の要素を持つベクトルであり、Am=とする。また、ベクトルA1,...,AMの各要素は対応付けられているとする。言い換えると、Ak1,...,AkMは対応付けられたk番目の数値群とする。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、aknmを秘密分散装置100nが記録する数値Akmの断片とする。なお、上述の限定シャッフルはM=1の場合に相当するので、以下の説明はより一般的な限定シャッフルである。秘密分散システムの構成は図1と同じであり、秘密分散の処理フローは図2と同じである。秘密分散装置100nは、少なくとも断片置換部110nと再分散部120nと記録部190nを備える。ただし、各構成部とその処理は以下のようになる。記録部190nは断片a1n1,...,aKn1,...,a1nM,...,aKnMなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は、N未満の数の秘密分散装置を選択するS105。例えば、N個の断片のうちN’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がN’個以上N未満の秘密分散装置を選べばよい。この処理は同じである。断片置換手段は、少なくとも断片置換部1101,...,110Nを含んで構成される。そして、選択手段105に選択された秘密分散装置100iただし、iは選択された秘密分散装置を示す番号の断片置換部110i間で{1,...,K}→{1,...,K}の全単射πを作成し、選択された秘密分散装置100iの記録部190iが記録する断片aπki1,...,aπkiMを対応付けられたk番目の数値群の断片にするS110。再分散手段は、少なくとも再分散部1201,...,120Nを含んで構成される。再分散手段は、断片置換手段によって置換された数値群Aπk1,...,AπkMに対応する断片aπki1,...,aπkiMk番目に置換されているを用いて再分散化して新しい断片bk11,...,bkN1,...,bk1M,...,bkNMを求め、数値Bk1,...,BkMの断片とするS120。つまり、Aπkm=Bkmの関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Aπkm=Bkmであることを知らない。なお、各秘密分散装置100nの記録部190nは、断片bknmを記録するだけでなく、自身が記録しているk番目の断片である断片bknmが数値Bkmの断片であるという情報も記録する。また、数値B11,...,BK1,...,B1M,...,BKMを新しい数値A11,...,AK1,...,A1M,...,AKMとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を1つの要素対応付けられた数値群として列方向のランダム置換を行うことができる。[限定シャッフル]実施例2の秘密分散システムの構成も図1に示す。なお、本実施例の秘密分散装置100nは、点線で示された構成部も備えている。図5に実施例2の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク1000に接続されたN個Nは3以上の整数、nは1以上N以下の整数の秘密分散装置1001,...,100Nと選択手段105で構成される。ここで、A1,...,AKを各秘密分散装置100nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密分散装置100nが記録する数値Akの断片とする。本実施例の秘密分散システムは、選択手段105、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置100nは、初期情報分散部130n、初期乗算部140n、断片置換部110n、再分散部120n、確認分散部150n、確認乗算部160n、改ざん検出部170n、記録部190nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は実施例1と同じである。初期情報分散手段は、初期情報分散部1301,...,130Nで構成される。そして、選択手段105に選択された秘密計算装置100iの初期情報分散部130iは、秘密分散装置1001,...,100Nのどれも知らないK個の数値P1,...,PKそれぞれの断片p11,...,pK1,...,p1n,...,pKn,...,p1N,...,pKNを秘密計算によって求め、秘密分散装置100nに断片p1n,...,pKnを記録するS130。具体的には、選択手段105に選択された秘密分散装置から、2つ以上の秘密分散装置を選定する。そして、選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、2つの秘密分散装置100i,100jを選定しただし、i≠j、秘密分散装置100iが生成した数値の断片と、秘密分散装置100jが生成した数値の断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を2つとしたが、2つ以上でもかまわない。初期乗算手段は、初期乗算部1401,...,140Nで構成される。初期乗算部1401,...,140Nは、Sk=Pk×Akである数値Skの断片sk1,...,skNを秘密計算によって求め、秘密分散装置1001,...,100Nに分散して記録するS140。断片置換手段と再分散手段は、実施例1と同じである。確認分散手段は、確認分散部1501,...,150Nで構成される。確認分散部1501,...,150Nは、k=1~Kについて、Qk=Pπkである数値Qkの断片qk1,...,qkNを秘密計算によって生成し、秘密分散装置1001,...,100Nに分散して記録するS150。具体的には、ステップS130で選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップS130で選定された秘密分散装置100iが数値Pπk用に生成した数値の別の断片新しい断片と、ステップS130で選定された秘密分散装置100jが数値Pπk用に生成した数値の別の断片新しい断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Qk=Pπkであり、かつ、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を2つとしたが、ステップS130と同じように2つ以上でもかまわない。確認乗算手段は、確認乗算部1601,...,160Nで構成される。確認乗算部1601,...,160Nは、Tk=Qk×Bkである数値Tkの断片tk1,...,tkNを秘密計算によって求め、秘密分散装置1001,...,100Nに分散して記録するS160。改ざん検出手段は、改ざん検出部1701,...,170Nで構成される。改ざん検出部1701,...,170Nは、k=1~Kについて、Tk=Sπkであることを確認するS170。tkn≠sπknの場合には、改ざんがあったとして異常終了する。また、数値B1,...,BKを新しい数値A1,...,AKとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。実施例2の秘密分散システムによれば、実施例1の秘密分散装置と同じ効果が得られると共に、数値A1,...,AKと数値B1,...,BKとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置100nは、比較部210nと交換部220nも備える。具体的なソートの処理については実施例1と同じである。実施例1、2では、秘密分散装置の数をNNは3以上の整数としていた。実施例3では、秘密分散システムを構成する秘密分散装置の数を3に限定し、より具体的に説明する。[限定シャッフル]図6に実施例3の秘密分散システムの機能構成例を示す。図7に実施例3の再分散部の詳細な構成の例を示す。図8に実施例3の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク1000に接続された3つの秘密分散装置100α,100β,100γと選択手段105で構成される。ここで、K個の数値のk番目を数値Ak=akαβakβγakγαただし、Kは2以上の整数、kは1以上K以下の整数、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかとし、その3つの断片をakγα,akαβ、akαβ,akβγ、akβγ,akγαとする。なお、選択手段105は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。本実施例の秘密分散システムは、選択手段105と断片置換手段と再分散手段を備える。各秘密分散装置100nは、断片置換部110n、再分散部120n、記録部190nを備えているただし、nはα、β、γのいずれか。記録部190nは、数値A1,...,AKの断片などを記録する。選択手段105は、2つの秘密分散装置を選択する。そして、選択手段105に選択された秘密分散装置の一方を第1の秘密分散装置1001、他方を第2の秘密分散装置1002、選択されなかった秘密分散装置を第3の秘密分散装置1003とするS105。ここで、第1の秘密分散装置1001が記録するk番目の断片をak1=ak31,ak12、第2の秘密分散装置1002が記録するk番目の断片をak2=ak12,ak23、第3の秘密分散装置1003が記録するk番目の断片をak3=ak23,ak31とする。断片置換手段は、少なくとも断片置換部110α,110β,110γを含んで構成される。断片置換手段は、第1の秘密分散装置1001または第2の秘密分散装置1002で{1,...,K}→{1,...,K}の全単射πを作成し、第1の秘密分散装置1001が記録する断片aπk1をk番目の断片にし、第2の秘密分散装置1002が記録する断片aπk2をk番目の断片にするS110。実施例1で説明した通り、全単射πは、1~Kを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisherYatesshuffleなどを用いて作成すればよい。再分散手段は、少なくとも再分散部120α,120β,120γを含んで構成される。図7に示すように再分散部120nは、第1乱数生成部121n、第2乱数生成部122n、第1計算部123n、第2計算部124n、第3計算部125n、断片更新部126nを備えている。第1の秘密分散装置1001の第1乱数生成部1211は、k番目の断片の再分散化のために、ランダムな値であるbk31を生成し、第3の秘密分散装置1003に送信するS121。第2の秘密分散装置1002の第2乱数生成部1222は、k番目の断片の再分散化のために、ランダムな値であるbk23を生成し、第3の秘密分散装置1003に送信するS122。第1の秘密分散装置1001の第1計算部1231は、k番目の断片の再分散化のために、xk=bk31-aπk31を計算し、第2の秘密分散装置1002に送信するS123。第2の秘密分散装置1002の第2計算部1242は、k番目の断片の再分散化のために、yk=bk23-aπk23を計算し、第1の秘密分散装置1001に送信するS124。第1の秘密分散装置1001の第3計算部1251と第2の秘密分散装置1002の第3計算部1252は、k番目の断片の再分散化のために、それぞれbk12=aπk12-xk-ykを計算するS125。第1の秘密分散装置1001の断片更新部1261はbk31,bk12を断片bk1とし、第2の秘密分散装置1002の断片更新部1262はbk12,bk23を断片bk2とし、第3の秘密分散装置1003の断片更新部1263はbk23,bk31を断片bk3とするS126。なお、各秘密分散装置100nの記録部190nは、断片bknを記録するだけでなく、自身が記録しているk番目の断片である断片bknが数値Bkの断片であるという情報も記録する。実施例1と同じように、断片bk1,bk2,bk3は、数値Bkの断片である。つまり、ステップS121~S126が、ステップS120に相当する。また、数値B1,...,BKを新しい数値A1,...,AKとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。そして、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値A1,...,AKと対応つけることができない数値B1,...,BKを得ることができる。本実施例では、断片置換手段が選択する秘密分散装置を、{100α,100β},{100β,100γ},{100γ,100α}のように選択すれば、全ての秘密分散装置が選ばれなかったことがある状態にできる。したがって、実施例3の秘密分散システムは、実施例1と同様の効果が得られる。なお、ソートも行う場合は、秘密分散装置100nは、比較部210nと交換部220nも備える。具体的なソートの処理については実施例1と同じである。[限定シャッフルの変形例]Mは1以上の整数、mは1以上M以下の整数とする。A1,...,AMはそれぞれK個の要素を持つベクトルであり、Am=とする。また、ベクトルA1,...,AMの各要素は対応付けられているとする。言い換えると、Ak1,...,AkMは対応付けられたk番目の数値群である。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、数値Akm=akαβmakβγmakγαmただし、kは1以上K以下の整数、mは1以上M以下の整数、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかとし、の3つの断片をakγαm,akαβm、akαβm,akβγm、akβγm,akγαmとする。なお、上述の限定シャッフルはM=1の場合に相当するので、以下の説明はより一般的な限定シャッフルである。秘密分散システムの機能構成例は図6と同じであり、再分散部の詳細な構成例は図7と同じであり、秘密分散の処理フローは図8と同じである。秘密分散システムは、選択手段105と断片置換手段と再分散手段を備える。秘密分散装置100nは、少なくとも断片置換部110nと再分散部120nと記録部190nを備えるただし、nはα、β、γのいずれか。ただし、各構成部とその処理は以下のようになる。記録部190nは断片a1n1,...,aKn1,...,a1nM,...,aKnMなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は、2つの秘密分散装置を選択する。そして、選択手段105に選択された秘密分散装置の一方を第1の秘密分散装置1001、他方を第2の秘密分散装置1002、選択されなかった秘密分散装置を第3の秘密分散装置1003とするS105。ここで、第1の秘密分散装置1001が記録する数値Akmの断片をak1m=ak31m,ak12m、第2の秘密分散装置1002が記録する数値Akmの断片をak2m=ak12m,ak23m、第3の秘密分散装置1003が記録する数値Akmの断片をak3m=ak23m,ak31mとする。断片置換手段は、少なくとも断片置換部110α,110β,110γを含んで構成される。断片置換手段は、第1の秘密分散装置1001または第2の秘密分散装置1002で{1,...,K}→{1,...,K}の全単射πを作成し、第1の秘密分散装置1001が記録する断片aπk11,...,aπk1Mを対応付けられたk番目の数値群の断片にし、第2の秘密分散装置1002が記録する断片aπk21,...,aπk2Mを対応付けられたk番目の数値群の断片にするS110。再分散手段は、少なくとも再分散部120α,120β,120γを含んで構成される。図7に示すように再分散部120nは、第1乱数生成部121n、第2乱数生成部122n、第1計算部123n、第2計算部124n、第3計算部125n、断片更新部126nを備えている。第1の秘密分散装置1001の第1乱数生成部1211は、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk311,...,bk31Mを生成し、第3の秘密分散装置1003に送信するS121。第2の秘密分散装置1002の第2乱数生成部1222は、対応付けられたk番目の数値群の断片の再分散化のために、ランダムな値であるbk231,...,bk23Mを生成し、第3の秘密分散装置1003に送信するS122。第1の秘密分散装置1001の第1計算部1231は、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてxkm=bk31m-aπk31mを計算し、xk1,...,xkMを第2の秘密分散装置1002に送信するS123。第2の秘密分散装置1002の第2計算部1242は、対応付けられたk番目の数値群の断片の再分散化のために、m=1~Mについてykm=bk23m-aπk23mを計算し、yk1,...,ykMを第1の秘密分散装置1001に送信するS124。第1の秘密分散装置1001の第3計算部1251と第2の秘密分散装置1002の第3計算部1252は、対応付けられたk番目の数値群の断片の再分散化のために、それぞれm=1~Mについてbk12m=aπk12m-xkm-ykmを計算するS125。第1の秘密分散装置1001の断片更新部1261はbk31m,bk12mを断片bk1mとし、第2の秘密分散装置1002の断片更新部1262はbk12m,bk23mを断片bk2mとし、第3の秘密分散装置1003の断片更新部1263はbk23m,bk31mを断片bk3mとするS126。なお、各秘密分散装置100nの記録部190nは、断片bknmを記録するだけでなく、自身が記録しているk番目の断片である断片bknmが数値Bkmの断片であるという情報も記録する。実施例1と同じように、断片bk1m,bk2m,bk3mは、数値Bkmの断片である。つまり、ステップS121~S126が、ステップS120に相当する。また、数値B11,...,BK1,...,B1M,...,BKMを新しい数値A11,...,AK1,...,A1M,...,AKMとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を1つの要素対応付けられた数値群として列方向のランダム置換を行うことができる。実施例4でも、秘密分散システムを構成する秘密分散装置の数を3に限定し、より具体的に説明する。また、実施例4では、実施例2と同じように不正検出機能を具備した例を説明する。[限定シャッフル]実施例4の秘密分散システムの構成も図6に示す。なお、本実施例の秘密分散装置100nは、点線で示された構成部も備えている。図9に改ざん検出部の詳細な構造を示す。図10に実施例4の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク1000に接続された3つの秘密分散装置100α,100β,100γと選択手段105で構成される。ここで、K個の数値のk番目を数値Ak=akαβakβγakγαただし、Kは2以上の整数、kは1以上K以下の整数、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかとし、その3つの断片をakγα,akαβ、akαβ,akβγ、akβγ,akγαとする。本実施例の秘密分散システムは、選択手段105、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。秘密分散装置100nは、初期情報分散部130n、初期乗算部140n、断片置換部110n、再分散部120n、確認分散部150n、確認乗算部160n、改ざん検出部170n、記録部190nを備えるただし、nはα、β、γのいずれか。記録部190nは、数値A1,...,AKの断片などを記録する。選択手段105は、2つの秘密分散装置を選択する。そして、選択手段105に選択された秘密分散装置の一方を第1の秘密分散装置1001、他方を第2の秘密分散装置1002、選択されなかった秘密分散装置を第3の秘密分散装置1003とするS105。ここで、第1の秘密分散装置1001が記録するk番目の断片をak1=ak31,ak12、第2の秘密分散装置1002が記録するk番目の断片をak2=ak12,ak23、第3の秘密分散装置1003が記録するk番目の断片をak3=ak23,ak31とする。初期情報分散手段は、初期情報分散部130α,130β,130γで構成される。初期情報分散部130α,130β,130γは、秘密分散装置100α,100β,100γのどれも知らないK個の数値P1,...,PKそれぞれの断片pknを秘密計算によって求め、秘密分散装置100nに記録するS130。例えば、第1の秘密分散装置1001でK個のランダムな値R11,...,R1Kを生成し、第2の秘密分散装置1002でK個のランダムな値R21,...,R2Kを生成する。そして、秘密分散装置1001,1002,1003で、R1kの断片r1k31,r1k12、r1k12,r1k23、r1k23,r1k31と、R2kの断片r2k31,r2k12、r2k12,r2k23、r2k23,r2k31とを秘密分散して記録する。その後、秘密分散装置1001,1002,1003で、Pk=R1kR2kである数値Pkの断片pk31,pk12、pk12,pk23、pk23,pk31を秘密計算によって求め、秘密分散装置1001,1002,1003に分散して記録する。このような処理によって、全ての秘密分散装置100α,100β,100γが知らない数値の断片を分散して記録できる。初期乗算手段は、初期乗算部140α,140β,140γで構成される。初期乗算部140α,140β,140γは、Sk=Pk×Akである数値Skの断片skγα,skαβ、skαβ,skβγ、skβγ,skγαを秘密計算によって求め、秘密分散装置100α,100β,100γに分散して記録するS140。断片置換手段と再分散手段は、実施例3と同じである。断片置換手段と再分散手段によって、秘密分散装置100α,100β,100γに数値Bkの断片として断片bk1、bk2、bk3が記録される。確認分散手段は、確認分散部150α,150β,150γで構成される。確認分散部150α,150β,150γは、k=1~Kについて、Qk=Pπkである数値Qkの断片qkγα,qkαβ、qkαβ,qkβγ、qkβγ,qkγαを秘密計算によって生成し、秘密分散装置100α,100β,100γに分散して記録するS150。例えば、ステップS130で第1の秘密分散装置1001が生成した数値R1πkの別の断片r’1πk31,r’1πk12、r’1πk12,r’1πk23、r’1πk23,r’1πk31と、第2の秘密分散装置1002が生成した数値R2πkの別の断片r’2πk31,r’2πk12、r’2πk12,r’2πk23、r’2πk23,r’2πk31とを秘密分散して記録する。その後、秘密分散装置1001,1002,1003で、Qk=R1πkR2πkである数値Qkの断片qk31,qk12、qk12,qk23、qk23,qk31を別の断片を用いて秘密計算によって求め、秘密分散装置1001,1002,1003に分散して記録する。このような処理によって、Qk=Pπkであり、かつ、全ての秘密分散装置100α,100β,100γが知らない数値の断片を分散して記録できる。確認乗算手段は、確認乗算部160α,160β,160γで構成される。確認乗算部160α,160β,160γは、Tk=Qk×Bkである数値Tkの断片tkγα,tkαβ、tkαβ,tkβγ、tkβγ,tkγαを秘密計算によって求め、秘密分散装置100α,100β,100γに分散して記録するS160。改ざん検出手段は、改ざん検出部170α,170β,170γで構成される。また、図9に示すように、改ざん検出部170nは、第3乱数生成部171n、第4乱数生成部172n、第4計算部173n、第5計算部174n、第1確認部175n、第6計算部176n、第7計算部177n、第2確認部178nを備える。改ざん検出手段は、秘密分散装置100α,100β,100γが第1の秘密分散装置1001、第2の秘密分散装置1002、第3の秘密分散装置1003のいずれの装置として動作するかにしたがって、以下のように処理を行う。第1の秘密分散装置1001の第3乱数生成部1711は、ランダムな値であるukを生成し、第2の秘密分散装置1002に送信するS171。第2の秘密分散装置1002の第4乱数生成部1722は、ランダムな値であるvkを生成し、第1の秘密分散装置1001に送信するS172。第1の秘密分散装置1001の第4計算部1731は、dk=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置1003に送信するS173。第2の秘密分散装置1002の第5計算部1742は、ek=sπk12-tk12-uk-vkを計算し、第3の秘密分散装置1003に送信するS174。第3の秘密分散装置1003の第1確認部1753は、dk=ekであることを確認し、異なっていれば処理を中止するS175。第1の秘密分散装置1001の第6計算部1761は、fk=sπk31-tk31ukを計算し、第3の秘密分散装置1003に送信するS176。第2の秘密分散装置1002の第7計算部1772は、gk=sπk23-tk23vkを計算し、第3の秘密分散装置1003に送信するS177。第3の秘密分散装置1003の第2確認部1783は、fkgkdk=0であることを確認し、異なっていれば処理を中止するS178。また、数値B1,...,BKを新しい数値A1,...,AKとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。実施例4の秘密分散システムによれば、実施例3の秘密分散装置と同じ効果が得られると共に、数値A1,...,AKと数値B1,...,BKとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置100nは、比較部210nと交換部220nも備える。具体的なソートの処理については実施例1と同じである。[秘密計算]上述の説明では、秘密計算については1つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、実施例3、4の秘密分散システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、秘密分散装置100α,100β,100γが分散して記録する数値Aの断片をaγα,aαβ、aαβ,aβγ、aβγ,aγα、数値Bの断片をbγα,bαβ、bαβ,bβγ、bβγ,bγα、数値Cの断片をcγα,cαβ、cαβ,cβγ、cβγ,cγαとする。数値Aの秘密分散1乱数aαβ,aβγを生成する。2aγα=A-aαβ-aβγを計算し、断片をaγα,aαβ、aαβ,aβγ、aβγ,aγαとし、秘密分散装置100α,100β,100γに分散して記録する。数値Aの復元1秘密分散装置100αは秘密分散装置100βにaγαを送信し、秘密分散装置100γにaαβを送信する。秘密分散装置100βは秘密分散装置100γにaαβを送信し、秘密分散装置100αにaβγを送信する。秘密分散装置100γは秘密分散装置100αにaβγを送信し、秘密分散装置100βにaγαを送信する。2秘密分散装置100αは秘密分散装置100βから受信したaβγと秘密分散装置100γから受信したaβγとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密分散装置100βは秘密分散装置100γから受信したaγαと秘密分散装置100αから受信したaγαとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密分散装置100γは秘密分散装置100αから受信したaαβと秘密分散装置100βから受信したaαβとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。C=ABの秘密計算1秘密分散装置100αはcγα,cαβ=aγαbγα,aαβbαβを計算して記録し、秘密分散装置100βはcαβ,cβγ=aαβbαβ,aβγbβγを計算して記録し、秘密分散装置100γはcβγ,cγα=aβγbβγ,aγαbγαを計算して記録する。C=A-Bの秘密計算1秘密分散装置100αはcγα,cαβ=aγα-bγα,aαβ-bαβを計算して記録し、秘密分散装置100βはcαβ,cβγ=aαβ-bαβ,aβγ-bβγを計算して記録し、秘密分散装置100γはcβγ,cγα=aβγ-bβγ,aγα-bγαを計算して記録する。C=ASの秘密計算ただし、Sは既知の定数1秘密分散装置100αはcγα,cαβ=aγαS,aαβを計算して記録し、秘密分散装置100γはcβγ,cγα=aβγ,aγαSを計算して記録する。秘密分散装置100βの処理はない。C=ASの秘密計算ただし、Sは既知の定数1秘密分散装置100αはcγα,cαβ=aγαS,aαβSを計算して記録し、秘密分散装置100βはcαβ,cβγ=aαβS,aβγSを計算して記録し、秘密分散装置100γはcβγ,cγα=aβγS,aγαSを計算して記録する。C=ABの秘密計算1秘密分散装置100αは、乱数r1,r2,cγαを生成し、cαβ=aγαaαβbγαbαβ-r1-r2-cγαを計算する。そして、秘密分散装置100αは、秘密分散装置100βにr1,cαβを、秘密分散装置100γにr2,cγαを送信する。2秘密分散装置100βは、y=aαβbβγaβγbαβr1を計算し、秘密分散装置100γに送信する。3秘密分散装置100γは、z=aβγbγαaγαbβγr2を計算し、秘密分散装置100αに送信する。4秘密分散装置100βと秘密分散装置100γは、それぞれcβγ=yzaβγbβγを計算する。5秘密分散装置100αはcγα,cαβを記録し、秘密分散装置100βはcαβ,cβγを記録し、秘密分散装置100γはcβγ,cγαを記録する。[プログラム、記録媒体]上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"