"3個以上の秘密ソート装置で構成され、M個のレコードからなる表Xの各要素が秘密分散された表[X]から、表Xのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソートシステムであって、Mは2以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、cは異なるM個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、情報[c]のM個の要素と表[X]のM個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報[cR]と表[XR]を求めるランダム置換手段と、情報[cR]を復号し、情報cRを求める復号手段と、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求めるソート手段とを備える秘密ソートシステム。請求項1記載の秘密ソートシステムであって、k、Dは整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、y1,...,yDはソートしたい順序y1<...<yDが定義されたD種類の値、xmkはレコードxmのk番目のデータでありy1,...,yDのいずれかの値、amはxmkの値、表[X]はレコードxmのk番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、am=ydならばHmd=1、am≠ydならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成する行列生成手段と、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求める列ベクトル変換手段と、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算手段と、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成する行列変換手段と、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求める行列計算手段と、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算手段と、を備える秘密ソートシステム。請求項1記載の秘密ソートシステムであって、k、B、Dは整数、bは1以上B以下の整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、xmkはレコードxmのk番目のデータでありB桁のD進数の値、abmはxmkの下位からb桁目の値、表[X]はレコードxmのk番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、abm=d-1ならばHmd=1、abm≠d-1ならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成する行列生成手段と、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求める列ベクトル変換手段と、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算手段と、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成する行列変換手段と、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求める行列計算手段と、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算手段と、を備え、前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表[XS]を次のソートの対象の表[X]としながら、b=1からb=Bまで繰り返すことを特徴とする秘密ソートシステム。請求項1記載の秘密ソートシステムであって、Bは整数、k1,...,kBとD1,...,DBは整数、bは1以上B以下の整数、dbは1以上Db以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、yb1,...,ybDbはソートしたい順序yb1<...<ybDbが定義されたDb種類の値、xmkbはレコードxmのkb番目のデータでありyb1,...,ybDbのいずれかの値、abmはxmkbの値、表[X]はBが大きい方を優先してレコードxmのk1番目からkB番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、abm=ybdbならばm行db列の要素を1、abm≠ybdbならばm行db列の要素を0とするM行Db列の行列[H]を生成する行列生成手段と、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDbの列ベクトル[h]を求める列ベクトル変換手段と、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算手段と、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行Db列の行列[G]を生成する行列変換手段と、行列[G]と行列[H]の要素ごとの積を要素とするM行Db列の行列[E]を、秘密計算で求める行列計算手段と、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算手段と、を備え、前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表[XS]を次のソートの対象の表[X]としながら、b=1からb=Bまで繰り返すことを特徴とする秘密ソートシステム。M個のレコードからなる表Xの各要素が秘密分散された表[X]から、表Xのレコードを並び替えた表に対応する秘密分散された表を求める3個以上の秘密ソート装置で構成される秘密ソートシステムの中の秘密ソート装置であって、Mは2以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、cは異なるM個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、情報[c]のM個の要素と表[X]のM個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報[cR]と表[XR]を求めるためのランダム置換部と、情報[cR]を復号し、情報cRを求めるための復号部と、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求めるためのソート部とを備える秘密ソート装置。3個以上の秘密ソート装置を用いて、M個のレコードからなる表Xの各要素が秘密分散された表[X]から、表Xのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソート方法であって、Mは2以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、cは異なるM個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、情報[c]のM個の要素と表[X]のM個のレコードとの対応を維持したまま秘密計算でレコード間のランダム置換し、ランダム置換された情報[cR]と表[XR]を求めるランダム置換ステップと、情報[cR]を復号し、情報cRを求める復号ステップと、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求めるソートステップとを有する秘密ソート方法。請求項6記載の秘密ソート方法であって、k、Dは整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、y1,...,yDはソートしたい順序y1<...<yDが定義されたD種類の値、xmkはレコードxmのk番目のデータでありy1,...,yDのいずれかの値、amはxmkの値、表[X]はレコードxmのk番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、am=ydならばHmd=1、am≠ydならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成する行列生成手段と、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求める列ベクトル変換ステップと、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算ステップと、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成する行列変換ステップと、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求める行列計算ステップと、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算ステップと、を有する秘密ソート方法。請求項6記載の秘密ソート方法であって、k、B、Dは整数、bは1以上B以下の整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、xmkはレコードxmのk番目のデータでありB桁のD進数の値、abmはxmkの下位からb桁目の値、表[X]はレコードxmのk番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、abm=d-1ならばHmd=1、abm≠d-1ならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成する行列生成ステップと、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求める列ベクトル変換ステップと、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算ステップと、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成する行列変換ステップと、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求める行列計算ステップと、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算ステップと、を有し、前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表[XS]を次のソートの対象の表[X]としながら、b=1からb=Bまで繰り返すことを特徴とする秘密ソート方法。請求項6記載の秘密ソート方法であって、Bは整数、k1,...,kBとD1,...,DBは整数、bは1以上B以下の整数、dbは1以上Db以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、yb1,...,ybDbはソートしたい順序yb1<...<ybDbが定義されたDb種類の値、xmkbはレコードxmのkb番目のデータでありyb1,...,ybDbのいずれかの値、abmはxmkbの値、表[X]はBが大きい方を優先してレコードxmのk1番目からkB番目のデータの値に基づいて昇順となるようにソートされるとし、さらに、abm=ybdbならばm行db列の要素を1、abm≠ybdbならばm行db列の要素を0とするM行Db列の行列[H]を生成する行列生成ステップと、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDbの列ベクトル[h]を求める列ベクトル変換ステップと、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求める列ベクトル計算ステップと、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行Db列の行列[G]を生成する行列変換ステップと、行列[G]と行列[H]の要素ごとの積を要素とするM行Db列の行列[E]を、秘密計算で求める行列計算ステップと、行列[E]の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報[c]とするソート情報計算ステップと、を有し、前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表[XS]を次のソートの対象の表[X]としながら、b=1からb=Bまで繰り返すことを特徴とする秘密ソート方法。請求項1から4のいずれかに記載の秘密ソートシステムの各秘密ソート装置としてコンピュータを機能させるための秘密ソートプログラム。しかしながら、従来技術は暗号化されたままデータ同士の比較を行った結果に応じて振る舞いが決まるアルゴリズムであり、比較に基づくソーティングアルゴリズムにしか適用できない。このため、入力データの個数をnとすると、計算時間をOnlognよりもよくすることはできないという課題がある。本発明は、比較に基づかないソーティングアルゴリズムを秘密計算上で実現することを目的とする。本発明の秘密ソートシステムは、3個以上の秘密ソート装置で構成され、M個のレコードからなる表Xの各要素が秘密分散された表[X]から、表Xのレコードを並び替えた表に対応する秘密分散された表を求める。ここで、Mは2以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、cは異なるM個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、cは1からMの異なる値がソート後の順番にしたがって並んだM個の要素を有する情報としてもよい。本発明の秘密ソートシステムは、少なくともランダム置換手段、復号手段、ソート手段を備える。ランダム置換手段は、情報[c]と表[X]が入力され、情報[c]のM個の要素と表[X]のM個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報[cR]と表[XR]を求める。復号手段は、情報[cR]を復号し、情報cRを求める。ソート手段は、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求める。本発明の秘密ソートシステムによれば、並び替え後の位置の値は正しいままレコード間のランダム置換を行うことができる。その一方で、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるため、ランダム置換によってレコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。図1に実施例1の秘密ソートシステムの機能構成例を示す。図2に実施例1の秘密ソートシステムの処理フローを示す。実施例1の秘密ソートシステムは、少なくともネットワーク1000で接続されたN個の秘密ソート装置101,...,10Nで構成され、M個のレコードからなる表Xの各要素が秘密分散された表[X]から、表Xのレコードを並び替えた表に対応する秘密分散された表を求める。なお、Mは2以上の整数、Nは3以上の整数、mは1以上M以下の整数、nは1以上N以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、上付きのTは転置を示す記号、cは異なるM個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、cは1からMの異なる値がソート後の順番にしたがって並んだM個の要素を有する情報としてもよい。秘密ソート装置10nは、ソート制御部300n、秘密分散装置100n、記録部190nを備える。秘密分散装置100nは、ソート制御部300nの指示にしたがって実施例1の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、限定シャッフルなどがある。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、1つの例であり、実施例1が利用できる秘密計算を限定するものではない。記録部190nは、秘密ソート装置10nの処理に必要な情報を記録する構成部である。図1に示した選択手段105は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。実施例1では、ソート後の順番が秘密分散された状態で与えられた後の処理を説明する。つまり、上述の情報cが秘密分散された状態情報[c]で与えられ、情報[c]に示された順番にレコードを並び替える。例えば、c=4,2,5,1,3Tの場合、1番目のレコードは4番目に移動し、2番目のレコードは2番目のまま、3番目のレコードは5番目に移動し、4番目のレコードは1番目に移動し、5番目のレコードは3番目に移動することを示している。各秘密ソート装置10nのソート制御部300nは、ランダム置換部310n、復号部320n、ソート部330nを備える。そして、秘密ソートシステムのランダム置換手段310図示していないはランダム置換部3101,...,310Nで構成され、復号手段320図示していないは復号部3201,...,320Nで構成され、ソート手段330図示していないはソート部3301,...,330Nで構成される。ランダム置換手段310は、情報[c]のM個の要素と表[X]のM個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報[cR]と表[XR]を求めるS310。具体的には、ランダム置換部3101,...,310Nランダム置換手段310が、秘密分散された情報[c]と秘密分散された表[X]に対して同一の全単射によるランダム置換を秘密分散装置1001,...,100Nに実行させる。復号手段320は、情報[cR]を復号し、情報cRを求めるS320。より具体的には、復号部3201,...,320N復号手段320が、秘密分散された情報[cR]の復号を秘密分散装置1001,...,100Nに実行させ、情報cRを得る。ソート手段330は、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求める。より具体的には、ソート部3301,...,330Nソート手段330が、情報cRが示す順番に表[XR]の各レコードを並べなおし、表[XS]を求める。実施例1の秘密ソートシステムによれば、並び替え後の位置の値は正しいまま、並び替えの前にレコード間をランダム置換する。また、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるので、レコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。つまり、計算の途中では、cのみが復号されるが、cは異なるM個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できるだけの情報例えば、1からMの整数をランダムに並べ替えた値であるため、復号される値からは有意な情報は得られない。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。[変形例1]変形例1では、実施例1の定義の他に、k、Dは整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、y1,...,yDはソートしたい順序y1<...<yDが定義されたD種類の値、xmkはレコードxmのk番目のデータでありy1,...,yDのいずれかの値、amはxmkの値とする。そして、表[X]をレコードxmのk番目のデータの値に基づいて昇順となるようにソートするための情報[c]を求める処理を含めて説明する。本変形例の秘密ソートシステムの構成も図1に示す。本変形例の秘密ソートシステムの処理フローは図3に示す。本変形例では、各秘密ソート装置10nのソート制御部300nは、ランダム置換部310n、復号部320n、ソート部330n、行列生成部340n、列ベクトル変換部350n、列ベクトル計算部360n、行列変換部370n、行列計算部380n、ソート情報計算部390nを備える。そして、秘密ソートシステムの行列生成手段340図示していないは行列生成部3401,...,340Nで構成され、列ベクトル変換手段350図示していないは列ベクトル変換部3501,...,350Nで構成され、列ベクトル計算手段360図示していないは列ベクトル計算部3601,...,360Nで構成され、行列変換手段370図示していないは行列変換部3701,...,370Nで構成され、行列計算手段380図示していないは行列計算部3801,...,380Nで構成され、ソート情報計算手段390図示していないはソート情報計算部3901,...,390Nで構成される。行列生成手段340は、am=ydかを秘密計算で確認し、am=ydならばHmd=1、am≠ydならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成するS340。より具体的には、行列生成部3401,...,340N行列生成手段340が、秘密分散装置1001,...,100Nにam=ydかを秘密計算で確認させ、am=ydならばHmd=1、am≠ydならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成させる。例えば、M=5、D=3、y1=0,y2=1,y3=2であり、x1k=2,x2k=1,x3k=2,x4k=0,x5k=1の場合、a1=y3,a2=y2,a3=y3,a4=y1,a5=y2なので、となる。この例の場合、行列生成手段340は、式1の行列Hの各要素を秘密分散した行列[H]を求める。また、D=2,y1=0,y2=1の場合であれば、[am]=0かどうかは[am]の否定で得られ、[am]=1かどうかは[am]の値そのままで得られる。したがって、ステップS340では、am=ydかを秘密計算で確認する必要はなく、[Hm1]=[1-am]、[Hm2]=[am]とすればよい。このように、Dやy1,...,yDの値の選び方によっては、am=ydかを秘密計算で確認する必要がない場合もある。なお、am=ydかを秘密計算で確認する場合には、従来技術として蓄積された論理回路の技術を用いれば、実現できる。例えば、2ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。C=1-{amB[∨]ydB∨∨am1[∨]yd1}1ただし、[∨]は排他的論理和XORを示す記号、∨は論理和ORを示す記号、ambは2ビット展開したときのamの下からbビット目の値、ydbは2ビット展開したときのydの下からbビット目の値、Bは2ビット展開したときのamとydの桁数とする。式1では、C=1ならばam=yd真、C=0ならばam≠yd偽である。また、式1の個々の演算は後述の秘密計算の例に示されているので、式1の演算は秘密計算で実行でき、秘密分散された[C]が求められる。したがって、確認後の分岐も秘密にするのであれば、[C]を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、所望の演算を後述する秘密計算の方法の組合せで実行できる。列ベクトル変換手段350は、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求めるS350。より具体的には、列ベクトル変換部3501,...,350N列ベクトル変換手段350が、秘密分散された状態を維持したまま行列[H]を列ベクトル[h]に変換する。例えば、式1の行列Hの場合であれば、h=0,0,0,1,0,0,1,0,0,1,1,0,1,0,0T2となる。この例の場合、列ベクトル変換手段350は、式2の列ベクトルhの各要素を秘密分散した列ベクトル[h]を求める。列ベクトル計算手段360は、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求めるS360。より具体的には、列ベクトル計算部3601,...,360N列ベクトル計算手段360が、秘密分散装置1001,...,100Nに、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を秘密計算で求めさせる。例えば、式2の列ベクトルhの場合であれば、u=0,0,0,1,1,1,2,2,2,3,4,4,5,5,5T3となる。この例の場合、列ベクトル計算手段360は、式3の列ベクトルuの各要素を秘密分散した列ベクトル[u]を求める。行列変換手段370は、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成するS370。より具体的には、行列変換部3701,...,370N行列変換手段370が、秘密分散された状態を維持したまま列ベクトル[u]を行列[G]に変換する。例えば、式3の列ベクトルuの場合であれば、となる。この例の場合、行列変換手段370は、式4の行列Gの各要素を秘密分散した行列[G]を求める。行列計算手段380は、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めるS380。より具体的には、行列計算部3801,...,380Nが、秘密分散装置1001,...,100Nに、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めさせる。例えば、式4の行列Gと式1の行列Hの場合であれば、となる。この例の場合、行列計算手段380は、式5の行列Eの各要素を秘密分散した行列[E]を求める。ソート情報計算手段390は、行列[E]の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報[c]とする。より具体的には、ソート情報計算部3901,...,390Nソート情報計算手段390が、秘密分散装置1001,...,100Nに、行列[E]の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報[c]を求めさせる。このようにして求めた情報[c]が実施例1の与えられた情報[c]に相当する。例えば、式5の行列Eの場合であれば、c=4,2,5,1,3T6となる。この例の場合、ソート情報計算手段390は、式6の情報cの各要素を秘密分散した情報[c]を求める。ランダム置換手段310、復号手段320、ソート手段330は実施例1と同じであり、ステップS310,S320,S330も実施例1と同じである。つまり、本変形例の秘密ソートシステムも、ソートに関しては実施例1と同様の効果が得られる。次にソートに要する計算時間を評価する。各[am]の計算をMによらない時間で、Hの計算をOM時間で、M個のランダム置換をOM時間で、乗算と加算をMによらない時間でできれば、全体の計算時間はOMである。例えば、非特許文献1の秘匿関数計算で非特許文献2のランダム置換を用い、D=2とすれば、[am]=0かどうかは[am]の否定で得られ、[am]=1かどうかは[am]の値そのままで得られる。したがって、[H]は[am]とその否定で計算でき、ランダム置換も線形時間OMであるので、全体も線形時間OMで実現できる。つまり、実施例1の秘密ソートシステムが、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できるので、本変形例のように情報[c]を求めれば、Onの計算時間でソーティングを行う秘密計算上のアルゴリズムを提供できる。[変形例2]変形例2では、実施例1の定義の他に、k、B、Dは整数、bは1以上B以下の整数、dは1以上D以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、xmkはレコードxmのk番目のデータでありB桁のD進数の値、abmはxmkの下位からb桁目の値とする。そして、表[X]をレコードxmのk番目のデータの値に基づいて昇順となるようにソートするための情報[c]を求める処理を含めて説明する。なお、秘密計算によるD進数への分解は、参考文献1ChaoNingQiuliangXuMultipartyComputationforModuloReductionwithoutBitDecompositionandaGeneralizationtoBitDecompositionASIACRYPT2010pp483500などに示されている方法を用いればよい。本変形例の秘密ソートシステムの構成も図1に示す。本変形例の秘密ソートシステムの処理フローは図4に示す。本変形例では、各秘密ソート装置10nのソート制御部300nは、ランダム置換部310n、復号部320n、ソート部330n、行列生成部340n、列ベクトル変換部350n、列ベクトル計算部360n、行列変換部370n、行列計算部380n、ソート情報計算部390nを備える。そして、秘密ソートシステムの行列生成手段340図示していないは行列生成部3401,...,340Nで構成され、列ベクトル変換手段350図示していないは列ベクトル変換部3501,...,350Nで構成され、列ベクトル計算手段360図示していないは列ベクトル計算部3601,...,360Nで構成され、行列変換手段370図示していないは行列変換部3701,...,370Nで構成され、行列計算手段380図示していないは行列計算部3801,...,380Nで構成され、ソート情報計算手段390図示していないはソート情報計算部3901,...,390Nで構成される。まず、ソート制御部3001,...,300Nは、b=1に初期設定するS301。行列生成手段340は、abm=d-1かを秘密計算で確認し、abm=d-1ならばHmd=1、abm≠d-1ならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成するS340。より具体的には、行列生成部3401,...,340N行列生成手段340が、秘密分散装置1001,...,100Nにabm=d-1かを秘密計算で確認させ、abm=d-1ならばHmd=1、abm≠d-1ならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成させる。本変形例は、変形例1のydをyd=d-1と設定した場合に相当する。また、特にD=2であれば、[abm]=0かどうかは[abm]の否定で得られ、[abm]=1かどうかは[abm]の値そのままで得られる。したがって、ステップS340では、am=d-1かを秘密計算で確認する必要はなく、[Hm1]=[1-am]、[Hm2]=[am]とすればよい。このように、Dの値によっては、am=d-1かを秘密計算で確認する必要がない場合もある。列ベクトル変換手段350は、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求めるS350。より具体的には、列ベクトル変換部3501,...,350N列ベクトル変換手段350が、秘密分散された状態を維持したまま行列[H]を列ベクトル[h]に変換する。列ベクトル計算手段360は、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求めるS360。より具体的には、列ベクトル計算部3601,...,360N列ベクトル計算手段360が、秘密分散装置1001,...,100Nに、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を秘密計算で求めさせる。行列変換手段370は、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成するS370。より具体的には、行列変換部3701,...,370N行列変換手段370が、秘密分散された状態を維持したまま列ベクトル[u]を行列[G]に変換する。行列計算手段380は、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めるS380。より具体的には、行列計算部3801,...,380Nが、秘密分散装置1001,...,100Nに、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めさせる。ソート情報計算手段390は、行列[E]の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報[c]とする。より具体的には、ソート情報計算部3901,...,390Nソート情報計算手段390が、秘密分散装置1001,...,100Nに、行列[E]の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報[c]を求めさせる。このようにして求めた情報[c]が実施例1の与えられた情報[c]に相当する。ランダム置換手段310、復号手段320、ソート手段330は実施例1と同じであり、ステップS310,S320,S330も実施例1と同じである。次にソート制御部3001,...,300Nは、繰返しの条件を満たすかを確認するS302。具体的には、b=Bかを確認する。ステップS302がYesの場合は、処理を終了する。また、ステップS302がNoの場合は、bにb1を代入しS302、ソート手段330が求めた表[XS]を次のソートの対象の表[X]として、ステップS340に戻る。このようにして、下位の桁から上位の桁にソートの対象を変更しながらB桁分のソートを繰り返せば、B桁のD進数の値を対象としたソートを行うことができる。このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例1と同じ効果が得られる。[変形例3]変形例3では、実施例1の定義の他に、Bは整数、k1,...,kBとD1,...,DBは整数、bは1以上B以下の整数、dbは1以上Db以下の整数、mは1以上M以下の整数、x1,...,xMは表Xのレコード、yb1,...,ybDbはソートしたい順序yb1<...<ybDbが定義されたDb種類の値、xmkbはレコードxmのkb番目のデータでありyb1,...,ybDbのいずれかの値、abmはxmkbの値とする。そして、表[X]をレコードxmのk1番目からkB番目のデータの値に基づいて、かつBが大きい方を優先して昇順となるようにソートするための情報[c]を求める処理を含めて説明する。本変形例の秘密ソートシステムの構成も図1に示す。本変形例の秘密ソートシステムの処理フローは図4に示す。本変形例では、各秘密ソート装置10nのソート制御部300nは、ランダム置換部310n、復号部320n、ソート部330n、行列生成部340n、列ベクトル変換部350n、列ベクトル計算部360n、行列変換部370n、行列計算部380n、ソート情報計算部390nを備える。そして、秘密ソートシステムの行列生成手段340図示していないは行列生成部3401,...,340Nで構成され、列ベクトル変換手段350図示していないは列ベクトル変換部3501,...,350Nで構成され、列ベクトル計算手段360図示していないは列ベクトル計算部3601,...,360Nで構成され、行列変換手段370図示していないは行列変換部3701,...,370Nで構成され、行列計算手段380図示していないは行列計算部3801,...,380Nで構成され、ソート情報計算手段390図示していないはソート情報計算部3901,...,390Nで構成される。まず、ソート制御部3001,...,300Nは、b=1に初期設定するS301。行列生成手段340は、abm=ybdbかを秘密計算で確認し、abm=ybdbならばHmd=1、abm≠ybdbならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成するS340。より具体的には、行列生成部3401,...,340N行列生成手段340が、秘密分散装置1001,...,100Nにabm=ybdbかを秘密計算で確認させ、abm=ybdbならばHmd=1、abm≠ybdbならばHmd=0であるHmdをm行d列の要素とするM行D列の行列[H]を生成させる。また、Db=2,yb1=0,yb2=1の場合であれば、[abm]=0かどうかは[abm]の否定で得られ、[abm]=1かどうかは[abm]の値そのままで得られる。したがって、ステップS340では、abm=ybdbかを秘密計算で確認する必要はなく、[Hm1]=[1-am]、[Hm2]=[am]とすればよい。このように、Dbやyb1,...,ybDbの値の選び方によっては、abm=ybdbかを秘密計算で確認する必要がない場合もある。列ベクトル変換手段350は、行列[H]の各列を左の列から順に上から下に縦につなげて要素数MDの列ベクトル[h]を求めるS350。より具体的には、列ベクトル変換部3501,...,350N列ベクトル変換手段350が、秘密分散された状態を維持したまま行列[H]を列ベクトル[h]に変換する。列ベクトル計算手段360は、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を、秘密計算で求めるS360。より具体的には、列ベクトル計算部3601,...,360N列ベクトル計算手段360が、秘密分散装置1001,...,100Nに、i番目の要素が、列ベクトル[h]の1番目の要素からi番目の要素までの和である列ベクトル[u]を秘密計算で求めさせる。行列変換手段370は、列ベクトル[u]をM要素ごとに分割してD個の列ベクトルを左から順に並べたM行D列の行列[G]を生成するS370。より具体的には、行列変換部3701,...,370N行列変換手段370が、秘密分散された状態を維持したまま列ベクトル[u]を行列[G]に変換する。行列計算手段380は、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めるS380。より具体的には、行列計算部3801,...,380Nが、秘密分散装置1001,...,100Nに、行列[G]と行列[H]の要素ごとの積を要素とするM行D列の行列[E]を、秘密計算で求めさせる。ソート情報計算手段390は、行列[E]の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報[c]とする。より具体的には、ソート情報計算部3901,...,390Nソート情報計算手段390が、秘密分散装置1001,...,100Nに、行列[E]の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報[c]を求めさせる。このようにして求めた情報[c]が実施例1の与えられた情報[c]に相当する。ランダム置換手段310、復号手段320、ソート手段330は実施例1と同じであり、ステップS310,S320,S330も実施例1と同じである。次にソート制御部3001,...,300Nは、繰返しの条件を満たすかを確認するS302。具体的には、b=Bかを確認する。ステップS302がYesの場合は、処理を終了する。また、ステップS302がNoの場合は、bにb1を代入しS302、ソート手段330が求めた表[XS]を次のソートの対象の表[X]として、ステップS340に戻る。このようにして、優先順位の低いk1番目のデータから優先順位の高いkB番目のデータにソートの対象を変更しながらソートを繰り返せば、k1番目からkB番目のデータの値に基づいて、かつBが大きい方を優先してソートを行うことができる。このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例2と同じ効果が得られる。[秘密計算]上述の説明では、秘密計算については1つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密ソート装置101,...,10Nが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、1つの例でありこれに限定されるものではない。本発明の秘密ソートシステムでは他の秘密計算を用いてもよい。ランダム置換1図5に本発明に利用できる秘密分散装置100nの機能構成例を詳しく示した秘密ソートシステムを示す。図6にランダム置換の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を詳細に示した機能構成例も図5に示す。図7にランダム置換の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型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"