秘密ソートシステム、秘密ソート装置、秘密ソート方法、秘密ソートプログラム
【課題】比較に基づかないソーティングアルゴリズムを秘密計算上で実現する。
【解決手段】本発明の秘密ソートシステムは、３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。本発明の秘密ソートシステムは、少なくともランダム置換手段、復号手段、ソート手段を備える。ランダム置換手段は、情報［ｃ］と表［Ｘ］が入力され、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める。復号手段は、情報［ｃＲ］を復号し、情報ｃＲを求める。ソート手段は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【解決手段】本発明の秘密ソートシステムは、３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。本発明の秘密ソートシステムは、少なくともランダム置換手段、復号手段、ソート手段を備える。ランダム置換手段は、情報［ｃ］と表［Ｘ］が入力され、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める。復号手段は、情報［ｃＲ］を復号し、情報ｃＲを求める。ソート手段は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密ソートシステム、秘密ソート装置、秘密ソート方法、秘密ソートプログラムに関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、例えば非特許文献１の秘密計算と呼ばれる方法がある。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定，論理積，論理和，排他的論理和）、データ形式変換（整数，二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。非特許文献２では、ソートの前後の値の対応を誰にも知られないように計算することを特徴とし、暗号化された複数のデータに対し、平文から計算される値でソートを行った結果の暗号文を計算する秘密ソート方法が提案されている。非特許文献２では、クイックソートなどの任意の比較ソートを、比較回数を増やすことなく秘密計算上で実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “３パーティ秘匿関数計算上のランダム置換プロトコル”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は暗号化されたままデータ同士の比較を行った結果に応じて振る舞いが決まるアルゴリズムであり、比較に基づくソーティングアルゴリズムにしか適用できない。このため、入力データの個数をｎとすると、計算時間をＯ（ｎ ｌｏｇ ｎ）よりもよくすることはできないという課題がある。本発明は、比較に基づかないソーティングアルゴリズムを秘密計算上で実現することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の秘密ソートシステムは、３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。ここで、Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、ｃは１からＭの異なる値がソート後の順番にしたがって並んだＭ個の要素を有する情報としてもよい。
【０００６】
本発明の秘密ソートシステムは、少なくともランダム置換手段、復号手段、ソート手段を備える。ランダム置換手段は、情報［ｃ］と表［Ｘ］が入力され、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める。復号手段は、情報［ｃＲ］を復号し、情報ｃＲを求める。ソート手段は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【発明の効果】
【０００７】
本発明の秘密ソートシステムによれば、並び替え後の位置の値は正しいままレコード間のランダム置換を行うことができる。その一方で、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるため、ランダム置換によってレコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の秘密ソートシステムの機能構成例を示す図。
【図２】本発明の秘密ソートシステムの処理フローを示す図。
【図３】変形例１の秘密ソートシステムの処理フローを示す図。
【図４】変形例２と変形例３の秘密ソートシステムの処理フローを示す図。
【図５】本発明の秘密ソートシステムに利用できる秘密分散装置１００ｎの機能構成例を示す図。
【図６】ランダム置換の１つ目の処理フロー例を示す図。
【図７】ランダム置換の２つ目の処理フロー例を示す図。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１０】
図１に実施例１の秘密ソートシステムの機能構成例を示す。図２に実施例１の秘密ソートシステムの処理フローを示す。実施例１の秘密ソートシステムは、少なくともネットワーク１０００で接続されたＮ個の秘密ソート装置１０１，…，１０Ｎで構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。なお、Ｍは２以上の整数、Ｎは３以上の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、上付きのＴは転置を示す記号、ｃは異なるＭ個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、ｃは１からＭの異なる値がソート後の順番にしたがって並んだＭ個の要素を有する情報としてもよい。
【００１１】
秘密ソート装置１０ｎは、ソート制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備える。秘密分散装置１００ｎは、ソート制御部３００ｎの指示にしたがって実施例１の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、限定シャッフルなどがある。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、１つの例であり、実施例１が利用できる秘密計算を限定するものではない。記録部１９０ｎは、秘密ソート装置１０ｎの処理に必要な情報を記録する構成部である。図１に示した選択手段１０５は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。
【００１２】
実施例１では、ソート後の順番が秘密分散された状態で与えられた後の処理を説明する。つまり、上述の情報ｃが秘密分散された状態（情報［ｃ］）で与えられ、情報［ｃ］に示された順番にレコードを並び替える。例えば、ｃ＝（４，２，５，１，３）Ｔの場合、１番目のレコードは４番目に移動し、２番目のレコードは２番目のまま、３番目のレコードは５番目に移動し、４番目のレコードは１番目に移動し、５番目のレコードは３番目に移動することを示している。
【００１３】
各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎを備える。そして、秘密ソートシステムのランダム置換手段３１０（図示していない）はランダム置換部３１０１，…，３１０Ｎで構成され、復号手段３２０（図示していない）は復号部３２０１，…，３２０Ｎで構成され、ソート手段３３０（図示していない）はソート部３３０１，…，３３０Ｎで構成される。
【００１４】
ランダム置換手段３１０は、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める（Ｓ３１０）。具体的には、ランダム置換部３１０１，…，３１０Ｎ（ランダム置換手段３１０）が、秘密分散された情報［ｃ］と秘密分散された表［Ｘ］に対して同一の全単射によるランダム置換を秘密分散装置１００１，…，１００Ｎに実行させる。
【００１５】
復号手段３２０は、情報［ｃＲ］を復号し、情報ｃＲを求める（Ｓ３２０）。より具体的には、復号部３２０１，…，３２０Ｎ（復号手段３２０）が、秘密分散された情報［ｃＲ］の復号を秘密分散装置１００１，…，１００Ｎに実行させ、情報ｃＲを得る。
【００１６】
ソート手段３３０は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。より具体的には、ソート部３３０１，…，３３０Ｎ（ソート手段３３０）が、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【００１７】
実施例１の秘密ソートシステムによれば、並び替え後の位置の値は正しいまま、並び替えの前にレコード間をランダム置換する。また、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるので、レコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。つまり、計算の途中では、ｃのみが復号されるが、ｃは異なるＭ個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できるだけの情報（例えば、１からＭの整数をランダムに並べ替えた値）であるため、復号される値からは有意な情報は得られない。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。
【００１８】
［変形例１］
変形例１では、実施例１の定義の他に、ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値とする。そして、表［Ｘ］をレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。
【００１９】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図３に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００２０】
行列生成手段３４０は、ａｍ＝ｙｄかを秘密計算で確認し、ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｍ＝ｙｄかを秘密計算で確認させ、ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。例えば、Ｍ＝５、Ｄ＝３、ｙ１＝０，ｙ２＝１，ｙ３＝２であり、ｘ１（ｋ）＝２，ｘ２（ｋ）＝１，ｘ３（ｋ）＝２，ｘ４（ｋ）＝０，ｘ５（ｋ）＝１の場合、ａ１＝ｙ３，ａ２＝ｙ２，ａ３＝ｙ３，ａ４＝ｙ１，ａ５＝ｙ２なので、
【００２１】
【数１】
【００２２】
となる。この例の場合、行列生成手段３４０は、式（１）の行列Ｈの各要素を秘密分散した行列［Ｈ］を求める。
【００２３】
また、Ｄ＝２，ｙ１＝０，ｙ２＝１の場合であれば、［ａｍ］＝０かどうかは［ａｍ］の否定で得られ、［ａｍ］＝１かどうかは［ａｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｍ＝ｙｄかを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄやｙ１，…，ｙＤの値の選び方によっては、ａｍ＝ｙｄかを秘密計算で確認する必要がない場合もある。
【００２４】
なお、ａｍ＝ｙｄかを秘密計算で確認する場合には、従来技術として蓄積された論理回路の技術を用いれば、実現できる。例えば、２ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。
【００２５】
Ｃ＝１−｛（ａｍＢ［∨］ｙｄＢ）∨・・・∨（ａｍ１［∨］ｙｄ１）｝ （１）
ただし、［∨］は排他的論理和（ＸＯＲ）を示す記号、∨は論理和（ＯＲ）を示す記号、ａｍｂは２ビット展開したときのａｍの下からｂビット目の値、ｙｄｂは２ビット展開したときのｙｄの下からｂビット目の値、Ｂは２ビット展開したときのａｍとｙｄの桁数とする。式（１）では、Ｃ＝１ならばａｍ＝ｙｄ（真）、Ｃ＝０ならばａｍ≠ｙｄ（偽）である。また、式（１）の個々の演算は後述の秘密計算の例に示されているので、式（１）の演算は秘密計算で実行でき、秘密分散された［Ｃ］が求められる。したがって、確認後の分岐も秘密にするのであれば、［Ｃ］を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、所望の演算を後述する秘密計算の方法の組合せで実行できる。
【００２６】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。例えば、式（１）の行列Ｈの場合であれば、
ｈ＝（０，０，０，１，０，０，１，０，０，１，１，０，１，０，０）Ｔ （２）
となる。この例の場合、列ベクトル変換手段３５０は、式（２）の列ベクトルｈの各要素を秘密分散した列ベクトル［ｈ］を求める。
【００２７】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。例えば、式（２）の列ベクトルｈの場合であれば、
ｕ＝（０，０，０，１，１，１，２，２，２，３，４，４，５，５，５）Ｔ （３）
となる。この例の場合、列ベクトル計算手段３６０は、式（３）の列ベクトルｕの各要素を秘密分散した列ベクトル［ｕ］を求める。
【００２８】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。例えば、式（３）の列ベクトルｕの場合であれば、
【００２９】
【数２】
【００３０】
となる。この例の場合、行列変換手段３７０は、式（４）の行列Ｇの各要素を秘密分散した行列［Ｇ］を求める。
【００３１】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。例えば、式（４）の行列Ｇと式（１）の行列Ｈの場合であれば、
【００３２】
【数３】
【００３３】
となる。この例の場合、行列計算手段３８０は、式（５）の行列Ｅの各要素を秘密分散した行列［Ｅ］を求める。
【００３４】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。例えば、式（５）の行列Ｅの場合であれば、
ｃ＝（４，２，５，１，３）Ｔ （６）
となる。この例の場合、ソート情報計算手段３９０は、式（６）の情報ｃの各要素を秘密分散した情報［ｃ］を求める。
【００３５】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。つまり、本変形例の秘密ソートシステムも、ソートに関しては実施例１と同様の効果が得られる。
【００３６】
次にソートに要する計算時間を評価する。各［ａｍ］の計算をＭによらない時間で、Ｈの計算をＯ（Ｍ）時間で、Ｍ個のランダム置換をＯ（Ｍ）時間で、乗算と加算をＭによらない時間でできれば、全体の計算時間はＯ（Ｍ）である。例えば、非特許文献１の秘匿関数計算で非特許文献２のランダム置換を用い、Ｄ＝２とすれば、［ａｍ］＝０かどうかは［ａｍ］の否定で得られ、［ａｍ］＝１かどうかは［ａｍ］の値そのままで得られる。したがって、［Ｈ］は［ａｍ］とその否定で計算でき、ランダム置換も線形時間Ｏ（Ｍ）であるので、全体も線形時間Ｏ（Ｍ）で実現できる。つまり、実施例１の秘密ソートシステムが、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できるので、本変形例のように情報［ｃ］を求めれば、Ｏ（ｎ）の計算時間でソーティングを行う秘密計算上のアルゴリズムを提供できる。
【００３７】
［変形例２］
変形例２では、実施例１の定義の他に、ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値とする。そして、表［Ｘ］をレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。なお、秘密計算によるＤ進数への分解は、参考文献１（Chao Ning, Qiuliang Xu, “Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition”, ASIACRYPT 2010, pp483-500.）などに示されている方法を用いればよい。
【００３８】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図４に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００３９】
まず、ソート制御部３００１，…，３００Ｎは、ｂ＝１に初期設定する（Ｓ３０１）。
【００４０】
行列生成手段３４０は、ａｂｍ＝ｄ−１かを秘密計算で確認し、ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｂｍ＝ｄ−１かを秘密計算で確認させ、ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。本変形例は、変形例１のｙｄを
ｙｄ＝ｄ−１
と設定した場合に相当する。
【００４１】
また、特にＤ＝２であれば、［ａｂｍ］＝０かどうかは［ａｂｍ］の否定で得られ、［ａｂｍ］＝１かどうかは［ａｂｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｍ＝ｄ−１かを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄの値によっては、ａｍ＝ｄ−１かを秘密計算で確認する必要がない場合もある。
【００４２】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。
【００４３】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。
【００４４】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。
【００４５】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。
【００４６】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。
【００４７】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。
【００４８】
次にソート制御部３００１，…，３００Ｎは、繰返しの条件を満たすかを確認する（Ｓ３０２）。具体的には、ｂ＝Ｂかを確認する。ステップＳ３０２がＹｅｓの場合は、処理を終了する。また、ステップＳ３０２がＮｏの場合は、ｂにｂ＋１を代入し（Ｓ３０２）、ソート手段３３０が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］として、ステップＳ３４０に戻る。このようにして、下位の桁から上位の桁にソートの対象を変更しながらＢ桁分のソートを繰り返せば、Ｂ桁のＤ進数の値を対象としたソートを行うことができる。
【００４９】
このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例１と同じ効果が得られる。
【００５０】
［変形例３］
変形例３では、実施例１の定義の他に、Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値とする。そして、表［Ｘ］をレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて、かつＢが大きい方を優先して昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。
【００５１】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図４に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００５２】
まず、ソート制御部３００１，…，３００Ｎは、ｂ＝１に初期設定する（Ｓ３０１）。
【００５３】
行列生成手段３４０は、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認し、ａｂｍ＝ｙｂ（ｄｂ）ならばＨｍｄ＝１、ａｂｍ≠ｙｂ（ｄｂ）ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認させ、ａｂｍ＝ｙｂ（ｄｂ）ならばＨｍｄ＝１、ａｂｍ≠ｙｂ（ｄｂ）ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。
【００５４】
また、Ｄｂ＝２，ｙｂ（１）＝０，ｙｂ（２）＝１の場合であれば、［ａｂｍ］＝０かどうかは［ａｂｍ］の否定で得られ、［ａｂｍ］＝１かどうかは［ａｂｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄｂやｙｂ（１），…，ｙｂ（Ｄｂ）の値の選び方によっては、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認する必要がない場合もある。
【００５５】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。
【００５６】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。
【００５７】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。
【００５８】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。
【００５９】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。
【００６０】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。
【００６１】
次にソート制御部３００１，…，３００Ｎは、繰返しの条件を満たすかを確認する（Ｓ３０２）。具体的には、ｂ＝Ｂかを確認する。ステップＳ３０２がＹｅｓの場合は、処理を終了する。また、ステップＳ３０２がＮｏの場合は、ｂにｂ＋１を代入し（Ｓ３０２）、ソート手段３３０が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］として、ステップＳ３４０に戻る。このようにして、優先順位の低いｋ１番目のデータから優先順位の高いｋＢ番目のデータにソートの対象を変更しながらソートを繰り返せば、ｋ１番目からｋＢ番目のデータの値に基づいて、かつＢが大きい方を優先してソートを行うことができる。
【００６２】
このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例２と同じ効果が得られる。
【００６３】
［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密ソート装置１０１，…，１０Ｎが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、１つの例でありこれに限定されるものではない。本発明の秘密ソートシステムでは他の秘密計算を用いてもよい。
【００６４】
ランダム置換１
図５に本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示した秘密ソートシステムを示す。図６にランダム置換の１つ目の処理フロー例を示す。この例では、秘密ソートシステムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密ソート装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密ソート装置１０ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密ソート装置の内部に配置されてもよいし、単独の装置であってもよい。
【００６５】
秘密ソートシステムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００６６】
選択手段１０５は、Ｎ未満の数の秘密ソート装置１０ｎを選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密ソート装置を選べばよい。
【００６７】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密ソート装置１０ｉ（ただし、ｉは選択された秘密ソート装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密ソート装置１０ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密ソート装置１０ｉ間で生成してもよいし、選択された秘密ソート装置１０ｉのうちの１つの秘密ソート装置が生成して、選択された秘密ソート装置１０ｉ間で共有してもよい。
【００６８】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密ソート装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密ソート装置１０ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密ソート装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００６９】
本発明の秘密ソートシステムによれば、限定された秘密ソート装置間で断片をシャッフルする。したがって、選ばれなかった秘密ソート装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密ソート装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密ソート装置を選択手段１０５で選ばないように、選択する秘密ソート装置をあらかじめ定めればよい。また、選択手段１０５が選ぶ秘密ソート装置を変更しながらこの処理を繰り返し、全ての秘密ソート装置が選ばれなかったことがある状態にすれば、全ての秘密ソート装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。
【００７０】
ランダム置換２
次のランダム置換のための秘密ソートシステムの秘密分散装置１００ｎを詳細に示した機能構成例も図５に示す。図７にランダム置換の２つ目の処理フロー例を示す。この例でも、秘密ソートシステムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密ソート装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密ソート装置１０ｎが記録する数値Ａｋの断片とする。
【００７１】
本発明の秘密ソートシステムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００７２】
選択手段１０５はランダム置換１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密ソート装置１０ｉの初期情報分散部１３０ｉは、秘密ソート装置１０１，…，１０Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、記録部１９０ｎに記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密ソート装置から、２つ以上の秘密ソート装置を選定する。そして、選定された秘密ソート装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密ソート装置１０ｉ，１０ｊを選定し（ただし、ｉ≠ｊ）、秘密ソート装置１０ｉが生成した数値の断片と、秘密ソート装置１０ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密ソート装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、２つ以上でもかまわない。
【００７３】
初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１４０）。
【００７４】
断片置換手段と再分散手段は、ランダム置換１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密ソート装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密ソート装置１０ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密ソート装置１０ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密ソート装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密ソート装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。
【００７５】
確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１６０）。
【００７６】
改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密ソート装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００７７】
［その他の秘密計算］
ここでは、秘密ソートシステムが３個の秘密ソート装置で構成された場合の秘密計算の例を示す。また、秘密ソート装置１０１，１０２，１０３の番号を固定する必要はないので、秘密ソート装置１０α，１０β，１０γと表現することにする。つまり、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれかである。
【００７８】
以下の秘密計算では、秘密ソート装置１０α，１０β，１０γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。なお、以下の説明では、Ｗを２以上のあらかじめ定めた整数とし、計算結果はＷで除した余りである。言い換えると、以下の説明の計算式では“ｍｏｄ Ｗ”を省略している。
【００７９】
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ−ａαβ−ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密ソート装置１０α，１０β，１０γに分散して記録する。
【００８０】
数値Ａの復元
（１）秘密ソート装置１０αは秘密ソート装置１０βにａγαを送信し、秘密ソート装置１０γにａαβを送信する。秘密ソート装置１０βは秘密ソート装置１０γにａαβを送信し、秘密ソート装置１０αにａβγを送信する。秘密ソート装置１０γは秘密ソート装置１０αにａβγを送信し、秘密ソート装置１０βにａγαを送信する。
（２）秘密ソート装置１０αは秘密ソート装置１０βから受信したａβγと秘密ソート装置１０γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密ソート装置１０βは秘密ソート装置１０γから受信したａγαと秘密ソート装置１０αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密ソート装置１０γは秘密ソート装置１０αから受信したａαβと秘密ソート装置１０βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。
【００８１】
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。
【００８２】
Ｃ＝Ａ−Ｂの秘密計算
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα−ｂγα，ａαβ−ｂαβ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβ−ｂαβ，ａβγ−ｂβγ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ−ｂβγ，ａγα−ｂγα）を計算して記録する。
【００８３】
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密ソート装置１０βの処理はない。
【００８４】
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。
【００８５】
Ｃ＝ＡＢの秘密計算
（１）秘密ソート装置１０αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）−ｒ１−ｒ２−ｃγαを計算する。そして、秘密ソート装置１０αは、秘密ソート装置１０βに（ｒ１，ｃαβ）を、秘密ソート装置１０γに（ｒ２，ｃγα）を送信する。
（２）秘密ソート装置１０βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密ソート装置１０γに送信する。
（３）秘密ソート装置１０γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密ソート装置１０αに送信する。
（４）秘密ソート装置１０βと秘密ソート装置１０γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密ソート装置１０αは（ｃγα，ｃαβ）を記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）を記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）を記録する。
【００８６】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
秘密ソート装置１０αは
（ｃγα，ｃαβ）＝（１−ａγα，−ａαβ ｍｏｄ Ｗ）
を計算して記録し、秘密ソート装置１０βは
（ｃαβ，ｃβγ）＝（−ａαβ ｍｏｄ Ｗ，−ａβγ ｍｏｄ Ｗ）
を計算して記録し、秘密ソート装置１０γは
（ｃβγ，ｃγα）＝（−ａβγ ｍｏｄ Ｗ，１−ａγα）
を計算して記録する。
【００８７】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行う。
【００８８】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密ソート装置１０αが断片（ｃγα’，ｃαβ’）を、秘密ソート装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密ソート装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密ソート装置１０αが断片（ｃγα”，ｃαβ”）を、秘密ソート装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密ソート装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密ソート装置１０α，１０β，１０γは、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、秘密ソート装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密ソート装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密ソート装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密ソート装置１０αが断片（ｃγα，ｃαβ）を、秘密ソート装置１０βが断片（ｃαβ，ｃβγ）を、秘密ソート装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００８９】
ビットの排他的論理和（Ｃ＝Ａ［∨］Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密ソート装置１０αが断片（ｃγα’，ｃαβ’）を、秘密ソート装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密ソート装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密ソート装置１０αが断片（ｃγα”，ｃαβ”）を、秘密ソート装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密ソート装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密ソート装置１０α，１０β，１０γは、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、秘密ソート装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密ソート装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密ソート装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密ソート装置１０αが断片（ｃγα，ｃαβ）を、秘密ソート装置１０βが断片（ｃαβ，ｃβγ）を、秘密ソート装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００９０】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００９１】
【数４】
【００９２】
を求めることである。また、秘密ソート装置１０α，１０β，１０γが分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）γα，ａ（ｎ）αβ）、（ａ（ｎ）αβ，ａ（ｎ）βγ）、（ａ（ｎ）βγ，ａ（ｎ）γα）とする。秘密ソート装置１０αは、
【００９３】
【数５】
【００９４】
を計算して記録し、秘密ソート装置１０βは
【００９５】
【数６】
【００９６】
を計算して記録し、秘密ソート装置１０γは
【００９７】
【数７】
【００９８】
を計算して記録する。
【００９９】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、秘密ソート装置１０βが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）を秘密分散し、秘密ソート装置１０α，１０β，１０γが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）の断片（ｂ（ｎ）γα，ｂ（ｎ）αβ）、（ｂ（ｎ）αβ，ｂ（ｎ）βγ）、（ｂ（ｎ）βγ，ｂ（ｎ）γα）を分散して記録する。ｎ＝０からＮ−１について、秘密ソート装置１０γが（ａγα）（ｎ）を秘密分散し、秘密ソート装置１０α，１０β，１０γが（ａγα）（ｎ）の断片（（ａγα）（ｎ）γα，（ａγα）（ｎ）αβ）、（（ａγα）（ｎ）αβ，（ａγα）（ｎ）βγ）、（（ａγα）（ｎ）βγ，（ａγα）（ｎ）γα）を分散して記録する。
（２）ｃγα＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａγα）（ｎ）−２ｂ（ｎ）（ａγα）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａγα）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａγα）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【０１００】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０６】
１０１，…，１０Ｎ 秘密ソート装置 １００１，…，１００Ｎ 秘密分散装置
１０５ 選択手段 １１０１，…，１１０Ｎ 断片置換部
１２０１，…，１２０Ｎ 再分散部 １３０１，…，１３０Ｎ 初期情報分散部
１４０１，…，１４０Ｎ 初期乗算部 １５０１，…，１５０Ｎ 確認分散部
１６０１，…，１６０Ｎ 確認乗算部 １７０１，…，１７０Ｎ 改ざん検出部
１９０１，…，１９０Ｎ 記録部 ３００１，…，３００Ｎ ソート制御部
３１０ ランダム置換手段 ３１０１，…，３１０Ｎ ランダム置換部
３２０ 復号手段 ３２０１，…，３２０Ｎ 復号部
３３０ ソート手段 ３３０１，…，３３０Ｎ ソート部
３４０ 行列生成手段 ３４０１，…，３４０Ｎ 行列生成部
３５０ 列ベクトル変換手段 ３５０１，…，３５０Ｎ 列ベクトル変換部
３６０ 列ベクトル計算手段 ３６０１，…，３６０Ｎ 列ベクトル計算部
３７０ 行列変換手段 ３７０１，…，３７０Ｎ 行列変換部
３８０ 行列計算手段 ３８０１，…，３８０Ｎ 行列計算部
３９０ ソート情報計算手段 ３９０１，…，３９０Ｎ ソート情報計算部
１０００ ネットワーク
【技術分野】
【０００１】
本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密ソートシステム、秘密ソート装置、秘密ソート方法、秘密ソートプログラムに関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、例えば非特許文献１の秘密計算と呼ばれる方法がある。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定，論理積，論理和，排他的論理和）、データ形式変換（整数，二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。非特許文献２では、ソートの前後の値の対応を誰にも知られないように計算することを特徴とし、暗号化された複数のデータに対し、平文から計算される値でソートを行った結果の暗号文を計算する秘密ソート方法が提案されている。非特許文献２では、クイックソートなどの任意の比較ソートを、比較回数を増やすことなく秘密計算上で実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “３パーティ秘匿関数計算上のランダム置換プロトコル”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は暗号化されたままデータ同士の比較を行った結果に応じて振る舞いが決まるアルゴリズムであり、比較に基づくソーティングアルゴリズムにしか適用できない。このため、入力データの個数をｎとすると、計算時間をＯ（ｎ ｌｏｇ ｎ）よりもよくすることはできないという課題がある。本発明は、比較に基づかないソーティングアルゴリズムを秘密計算上で実現することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の秘密ソートシステムは、３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。ここで、Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、ｃは１からＭの異なる値がソート後の順番にしたがって並んだＭ個の要素を有する情報としてもよい。
【０００６】
本発明の秘密ソートシステムは、少なくともランダム置換手段、復号手段、ソート手段を備える。ランダム置換手段は、情報［ｃ］と表［Ｘ］が入力され、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める。復号手段は、情報［ｃＲ］を復号し、情報ｃＲを求める。ソート手段は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【発明の効果】
【０００７】
本発明の秘密ソートシステムによれば、並び替え後の位置の値は正しいままレコード間のランダム置換を行うことができる。その一方で、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるため、ランダム置換によってレコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の秘密ソートシステムの機能構成例を示す図。
【図２】本発明の秘密ソートシステムの処理フローを示す図。
【図３】変形例１の秘密ソートシステムの処理フローを示す図。
【図４】変形例２と変形例３の秘密ソートシステムの処理フローを示す図。
【図５】本発明の秘密ソートシステムに利用できる秘密分散装置１００ｎの機能構成例を示す図。
【図６】ランダム置換の１つ目の処理フロー例を示す図。
【図７】ランダム置換の２つ目の処理フロー例を示す図。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１０】
図１に実施例１の秘密ソートシステムの機能構成例を示す。図２に実施例１の秘密ソートシステムの処理フローを示す。実施例１の秘密ソートシステムは、少なくともネットワーク１０００で接続されたＮ個の秘密ソート装置１０１，…，１０Ｎで構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める。なお、Ｍは２以上の整数、Ｎは３以上の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、上付きのＴは転置を示す記号、ｃは異なるＭ個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とする。例えば、ｃは１からＭの異なる値がソート後の順番にしたがって並んだＭ個の要素を有する情報としてもよい。
【００１１】
秘密ソート装置１０ｎは、ソート制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備える。秘密分散装置１００ｎは、ソート制御部３００ｎの指示にしたがって実施例１の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、限定シャッフルなどがある。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、１つの例であり、実施例１が利用できる秘密計算を限定するものではない。記録部１９０ｎは、秘密ソート装置１０ｎの処理に必要な情報を記録する構成部である。図１に示した選択手段１０５は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。
【００１２】
実施例１では、ソート後の順番が秘密分散された状態で与えられた後の処理を説明する。つまり、上述の情報ｃが秘密分散された状態（情報［ｃ］）で与えられ、情報［ｃ］に示された順番にレコードを並び替える。例えば、ｃ＝（４，２，５，１，３）Ｔの場合、１番目のレコードは４番目に移動し、２番目のレコードは２番目のまま、３番目のレコードは５番目に移動し、４番目のレコードは１番目に移動し、５番目のレコードは３番目に移動することを示している。
【００１３】
各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎを備える。そして、秘密ソートシステムのランダム置換手段３１０（図示していない）はランダム置換部３１０１，…，３１０Ｎで構成され、復号手段３２０（図示していない）は復号部３２０１，…，３２０Ｎで構成され、ソート手段３３０（図示していない）はソート部３３０１，…，３３０Ｎで構成される。
【００１４】
ランダム置換手段３１０は、情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求める（Ｓ３１０）。具体的には、ランダム置換部３１０１，…，３１０Ｎ（ランダム置換手段３１０）が、秘密分散された情報［ｃ］と秘密分散された表［Ｘ］に対して同一の全単射によるランダム置換を秘密分散装置１００１，…，１００Ｎに実行させる。
【００１５】
復号手段３２０は、情報［ｃＲ］を復号し、情報ｃＲを求める（Ｓ３２０）。より具体的には、復号部３２０１，…，３２０Ｎ（復号手段３２０）が、秘密分散された情報［ｃＲ］の復号を秘密分散装置１００１，…，１００Ｎに実行させ、情報ｃＲを得る。
【００１６】
ソート手段３３０は、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。より具体的には、ソート部３３０１，…，３３０Ｎ（ソート手段３３０）が、情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求める。
【００１７】
実施例１の秘密ソートシステムによれば、並び替え後の位置の値は正しいまま、並び替えの前にレコード間をランダム置換する。また、先にレコード間のランダム置換を行うことでランダム置換前後の対応がわからなくなるので、レコードの追跡ができなくなる。したがって、情報を漏らすことなく、並び替え後の位置を復号することができる。つまり、計算の途中では、ｃのみが復号されるが、ｃは異なるＭ個の値を並べたもので、レコード間をランダム置換してもソート後に何番目になるかを一意に決定できるだけの情報（例えば、１からＭの整数をランダムに並べ替えた値）であるため、復号される値からは有意な情報は得られない。よって、その後は復号したソート後の順番に各レコードを移動させるだけでよい。つまり、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できる。
【００１８】
［変形例１］
変形例１では、実施例１の定義の他に、ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値とする。そして、表［Ｘ］をレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。
【００１９】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図３に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００２０】
行列生成手段３４０は、ａｍ＝ｙｄかを秘密計算で確認し、ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｍ＝ｙｄかを秘密計算で確認させ、ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。例えば、Ｍ＝５、Ｄ＝３、ｙ１＝０，ｙ２＝１，ｙ３＝２であり、ｘ１（ｋ）＝２，ｘ２（ｋ）＝１，ｘ３（ｋ）＝２，ｘ４（ｋ）＝０，ｘ５（ｋ）＝１の場合、ａ１＝ｙ３，ａ２＝ｙ２，ａ３＝ｙ３，ａ４＝ｙ１，ａ５＝ｙ２なので、
【００２１】
【数１】
【００２２】
となる。この例の場合、行列生成手段３４０は、式（１）の行列Ｈの各要素を秘密分散した行列［Ｈ］を求める。
【００２３】
また、Ｄ＝２，ｙ１＝０，ｙ２＝１の場合であれば、［ａｍ］＝０かどうかは［ａｍ］の否定で得られ、［ａｍ］＝１かどうかは［ａｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｍ＝ｙｄかを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄやｙ１，…，ｙＤの値の選び方によっては、ａｍ＝ｙｄかを秘密計算で確認する必要がない場合もある。
【００２４】
なお、ａｍ＝ｙｄかを秘密計算で確認する場合には、従来技術として蓄積された論理回路の技術を用いれば、実現できる。例えば、２ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。
【００２５】
Ｃ＝１−｛（ａｍＢ［∨］ｙｄＢ）∨・・・∨（ａｍ１［∨］ｙｄ１）｝ （１）
ただし、［∨］は排他的論理和（ＸＯＲ）を示す記号、∨は論理和（ＯＲ）を示す記号、ａｍｂは２ビット展開したときのａｍの下からｂビット目の値、ｙｄｂは２ビット展開したときのｙｄの下からｂビット目の値、Ｂは２ビット展開したときのａｍとｙｄの桁数とする。式（１）では、Ｃ＝１ならばａｍ＝ｙｄ（真）、Ｃ＝０ならばａｍ≠ｙｄ（偽）である。また、式（１）の個々の演算は後述の秘密計算の例に示されているので、式（１）の演算は秘密計算で実行でき、秘密分散された［Ｃ］が求められる。したがって、確認後の分岐も秘密にするのであれば、［Ｃ］を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、所望の演算を後述する秘密計算の方法の組合せで実行できる。
【００２６】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。例えば、式（１）の行列Ｈの場合であれば、
ｈ＝（０，０，０，１，０，０，１，０，０，１，１，０，１，０，０）Ｔ （２）
となる。この例の場合、列ベクトル変換手段３５０は、式（２）の列ベクトルｈの各要素を秘密分散した列ベクトル［ｈ］を求める。
【００２７】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。例えば、式（２）の列ベクトルｈの場合であれば、
ｕ＝（０，０，０，１，１，１，２，２，２，３，４，４，５，５，５）Ｔ （３）
となる。この例の場合、列ベクトル計算手段３６０は、式（３）の列ベクトルｕの各要素を秘密分散した列ベクトル［ｕ］を求める。
【００２８】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。例えば、式（３）の列ベクトルｕの場合であれば、
【００２９】
【数２】
【００３０】
となる。この例の場合、行列変換手段３７０は、式（４）の行列Ｇの各要素を秘密分散した行列［Ｇ］を求める。
【００３１】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。例えば、式（４）の行列Ｇと式（１）の行列Ｈの場合であれば、
【００３２】
【数３】
【００３３】
となる。この例の場合、行列計算手段３８０は、式（５）の行列Ｅの各要素を秘密分散した行列［Ｅ］を求める。
【００３４】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。例えば、式（５）の行列Ｅの場合であれば、
ｃ＝（４，２，５，１，３）Ｔ （６）
となる。この例の場合、ソート情報計算手段３９０は、式（６）の情報ｃの各要素を秘密分散した情報［ｃ］を求める。
【００３５】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。つまり、本変形例の秘密ソートシステムも、ソートに関しては実施例１と同様の効果が得られる。
【００３６】
次にソートに要する計算時間を評価する。各［ａｍ］の計算をＭによらない時間で、Ｈの計算をＯ（Ｍ）時間で、Ｍ個のランダム置換をＯ（Ｍ）時間で、乗算と加算をＭによらない時間でできれば、全体の計算時間はＯ（Ｍ）である。例えば、非特許文献１の秘匿関数計算で非特許文献２のランダム置換を用い、Ｄ＝２とすれば、［ａｍ］＝０かどうかは［ａｍ］の否定で得られ、［ａｍ］＝１かどうかは［ａｍ］の値そのままで得られる。したがって、［Ｈ］は［ａｍ］とその否定で計算でき、ランダム置換も線形時間Ｏ（Ｍ）であるので、全体も線形時間Ｏ（Ｍ）で実現できる。つまり、実施例１の秘密ソートシステムが、比較に基づかないソーティングアルゴリズムを秘密計算上で実現できるので、本変形例のように情報［ｃ］を求めれば、Ｏ（ｎ）の計算時間でソーティングを行う秘密計算上のアルゴリズムを提供できる。
【００３７】
［変形例２］
変形例２では、実施例１の定義の他に、ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値とする。そして、表［Ｘ］をレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。なお、秘密計算によるＤ進数への分解は、参考文献１（Chao Ning, Qiuliang Xu, “Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition”, ASIACRYPT 2010, pp483-500.）などに示されている方法を用いればよい。
【００３８】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図４に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００３９】
まず、ソート制御部３００１，…，３００Ｎは、ｂ＝１に初期設定する（Ｓ３０１）。
【００４０】
行列生成手段３４０は、ａｂｍ＝ｄ−１かを秘密計算で確認し、ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｂｍ＝ｄ−１かを秘密計算で確認させ、ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。本変形例は、変形例１のｙｄを
ｙｄ＝ｄ−１
と設定した場合に相当する。
【００４１】
また、特にＤ＝２であれば、［ａｂｍ］＝０かどうかは［ａｂｍ］の否定で得られ、［ａｂｍ］＝１かどうかは［ａｂｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｍ＝ｄ−１かを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄの値によっては、ａｍ＝ｄ−１かを秘密計算で確認する必要がない場合もある。
【００４２】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。
【００４３】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。
【００４４】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。
【００４５】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。
【００４６】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。
【００４７】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。
【００４８】
次にソート制御部３００１，…，３００Ｎは、繰返しの条件を満たすかを確認する（Ｓ３０２）。具体的には、ｂ＝Ｂかを確認する。ステップＳ３０２がＹｅｓの場合は、処理を終了する。また、ステップＳ３０２がＮｏの場合は、ｂにｂ＋１を代入し（Ｓ３０２）、ソート手段３３０が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］として、ステップＳ３４０に戻る。このようにして、下位の桁から上位の桁にソートの対象を変更しながらＢ桁分のソートを繰り返せば、Ｂ桁のＤ進数の値を対象としたソートを行うことができる。
【００４９】
このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例１と同じ効果が得られる。
【００５０】
［変形例３］
変形例３では、実施例１の定義の他に、Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値とする。そして、表［Ｘ］をレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて、かつＢが大きい方を優先して昇順となるようにソートするための情報［ｃ］を求める処理を含めて説明する。
【００５１】
本変形例の秘密ソートシステムの構成も図１に示す。本変形例の秘密ソートシステムの処理フローは図４に示す。本変形例では、各秘密ソート装置１０ｎのソート制御部３００ｎは、ランダム置換部３１０ｎ、復号部３２０ｎ、ソート部３３０ｎ、行列生成部３４０ｎ、列ベクトル変換部３５０ｎ、列ベクトル計算部３６０ｎ、行列変換部３７０ｎ、行列計算部３８０ｎ、ソート情報計算部３９０ｎを備える。そして、秘密ソートシステムの行列生成手段３４０（図示していない）は行列生成部３４０１，…，３４０Ｎで構成され、列ベクトル変換手段３５０（図示していない）は列ベクトル変換部３５０１，…，３５０Ｎで構成され、列ベクトル計算手段３６０（図示していない）は列ベクトル計算部３６０１，…，３６０Ｎで構成され、行列変換手段３７０（図示していない）は行列変換部３７０１，…，３７０Ｎで構成され、行列計算手段３８０（図示していない）は行列計算部３８０１，…，３８０Ｎで構成され、ソート情報計算手段３９０（図示していない）はソート情報計算部３９０１，…，３９０Ｎで構成される。
【００５２】
まず、ソート制御部３００１，…，３００Ｎは、ｂ＝１に初期設定する（Ｓ３０１）。
【００５３】
行列生成手段３４０は、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認し、ａｂｍ＝ｙｂ（ｄｂ）ならばＨｍｄ＝１、ａｂｍ≠ｙｂ（ｄｂ）ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する（Ｓ３４０）。より具体的には、行列生成部３４０１，…，３４０Ｎ（行列生成手段３４０）が、秘密分散装置１００１，…，１００Ｎにａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認させ、ａｂｍ＝ｙｂ（ｄｂ）ならばＨｍｄ＝１、ａｂｍ≠ｙｂ（ｄｂ）ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成させる。
【００５４】
また、Ｄｂ＝２，ｙｂ（１）＝０，ｙｂ（２）＝１の場合であれば、［ａｂｍ］＝０かどうかは［ａｂｍ］の否定で得られ、［ａｂｍ］＝１かどうかは［ａｂｍ］の値そのままで得られる。したがって、ステップＳ３４０では、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認する必要はなく、［Ｈｍ１］＝［１−ａｍ］、［Ｈｍ２］＝［ａｍ］とすればよい。このように、Ｄｂやｙｂ（１），…，ｙｂ（Ｄｂ）の値の選び方によっては、ａｂｍ＝ｙｂ（ｄｂ）かを秘密計算で確認する必要がない場合もある。
【００５５】
列ベクトル変換手段３５０は、行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める（Ｓ３５０）。より具体的には、列ベクトル変換部３５０１，…，３５０Ｎ（列ベクトル変換手段３５０）が、秘密分散された状態を維持したまま行列［Ｈ］を列ベクトル［ｈ］に変換する。
【００５６】
列ベクトル計算手段３６０は、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める（Ｓ３６０）。より具体的には、列ベクトル計算部３６０１，…，３６０Ｎ（列ベクトル計算手段３６０）が、秘密分散装置１００１，…，１００Ｎに、ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を秘密計算で求めさせる。
【００５７】
行列変換手段３７０は、列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する（Ｓ３７０）。より具体的には、行列変換部３７０１，…，３７０Ｎ（行列変換手段３７０）が、秘密分散された状態を維持したまま列ベクトル［ｕ］を行列［Ｇ］に変換する。
【００５８】
行列計算手段３８０は、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める（Ｓ３８０）。より具体的には、行列計算部３８０１，…，３８０Ｎが、秘密分散装置１００１，…，１００Ｎに、行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求めさせる。
【００５９】
ソート情報計算手段３９０は、行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］とする。より具体的には、ソート情報計算部３９０１，…，３９０Ｎ（ソート情報計算手段３９０）が、秘密分散装置１００１，…，１００Ｎに、行列［Ｅ］の行ごとの要素の総和を秘密計算で求めさせ、それぞれの総和を要素として行の順番に並べた情報を情報［ｃ］を求めさせる。このようにして求めた情報［ｃ］が実施例１の与えられた情報［ｃ］に相当する。
【００６０】
ランダム置換手段３１０、復号手段３２０、ソート手段３３０は実施例１と同じであり、ステップＳ３１０，Ｓ３２０，Ｓ３３０も実施例１と同じである。
【００６１】
次にソート制御部３００１，…，３００Ｎは、繰返しの条件を満たすかを確認する（Ｓ３０２）。具体的には、ｂ＝Ｂかを確認する。ステップＳ３０２がＹｅｓの場合は、処理を終了する。また、ステップＳ３０２がＮｏの場合は、ｂにｂ＋１を代入し（Ｓ３０２）、ソート手段３３０が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］として、ステップＳ３４０に戻る。このようにして、優先順位の低いｋ１番目のデータから優先順位の高いｋＢ番目のデータにソートの対象を変更しながらソートを繰り返せば、ｋ１番目からｋＢ番目のデータの値に基づいて、かつＢが大きい方を優先してソートを行うことができる。
【００６２】
このような方法でソートが実行されるので、本変形例の秘密ソートシステムによれば、変形例２と同じ効果が得られる。
【００６３】
［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密ソート装置１０１，…，１０Ｎが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、１つの例でありこれに限定されるものではない。本発明の秘密ソートシステムでは他の秘密計算を用いてもよい。
【００６４】
ランダム置換１
図５に本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示した秘密ソートシステムを示す。図６にランダム置換の１つ目の処理フロー例を示す。この例では、秘密ソートシステムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密ソート装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密ソート装置１０ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密ソート装置の内部に配置されてもよいし、単独の装置であってもよい。
【００６５】
秘密ソートシステムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００６６】
選択手段１０５は、Ｎ未満の数の秘密ソート装置１０ｎを選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密ソート装置を選べばよい。
【００６７】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密ソート装置１０ｉ（ただし、ｉは選択された秘密ソート装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密ソート装置１０ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密ソート装置１０ｉ間で生成してもよいし、選択された秘密ソート装置１０ｉのうちの１つの秘密ソート装置が生成して、選択された秘密ソート装置１０ｉ間で共有してもよい。
【００６８】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密ソート装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密ソート装置１０ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密ソート装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００６９】
本発明の秘密ソートシステムによれば、限定された秘密ソート装置間で断片をシャッフルする。したがって、選ばれなかった秘密ソート装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密ソート装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密ソート装置を選択手段１０５で選ばないように、選択する秘密ソート装置をあらかじめ定めればよい。また、選択手段１０５が選ぶ秘密ソート装置を変更しながらこの処理を繰り返し、全ての秘密ソート装置が選ばれなかったことがある状態にすれば、全ての秘密ソート装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。
【００７０】
ランダム置換２
次のランダム置換のための秘密ソートシステムの秘密分散装置１００ｎを詳細に示した機能構成例も図５に示す。図７にランダム置換の２つ目の処理フロー例を示す。この例でも、秘密ソートシステムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密ソート装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密ソート装置１０ｎが記録する数値Ａｋの断片とする。
【００７１】
本発明の秘密ソートシステムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００７２】
選択手段１０５はランダム置換１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密ソート装置１０ｉの初期情報分散部１３０ｉは、秘密ソート装置１０１，…，１０Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、記録部１９０ｎに記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密ソート装置から、２つ以上の秘密ソート装置を選定する。そして、選定された秘密ソート装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密ソート装置１０ｉ，１０ｊを選定し（ただし、ｉ≠ｊ）、秘密ソート装置１０ｉが生成した数値の断片と、秘密ソート装置１０ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密ソート装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、２つ以上でもかまわない。
【００７３】
初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１４０）。
【００７４】
断片置換手段と再分散手段は、ランダム置換１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密ソート装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密ソート装置１０ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密ソート装置１０ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密ソート装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密ソート装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。
【００７５】
確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１６０）。
【００７６】
改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密ソート装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００７７】
［その他の秘密計算］
ここでは、秘密ソートシステムが３個の秘密ソート装置で構成された場合の秘密計算の例を示す。また、秘密ソート装置１０１，１０２，１０３の番号を固定する必要はないので、秘密ソート装置１０α，１０β，１０γと表現することにする。つまり、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれかである。
【００７８】
以下の秘密計算では、秘密ソート装置１０α，１０β，１０γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。なお、以下の説明では、Ｗを２以上のあらかじめ定めた整数とし、計算結果はＷで除した余りである。言い換えると、以下の説明の計算式では“ｍｏｄ Ｗ”を省略している。
【００７９】
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ−ａαβ−ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密ソート装置１０α，１０β，１０γに分散して記録する。
【００８０】
数値Ａの復元
（１）秘密ソート装置１０αは秘密ソート装置１０βにａγαを送信し、秘密ソート装置１０γにａαβを送信する。秘密ソート装置１０βは秘密ソート装置１０γにａαβを送信し、秘密ソート装置１０αにａβγを送信する。秘密ソート装置１０γは秘密ソート装置１０αにａβγを送信し、秘密ソート装置１０βにａγαを送信する。
（２）秘密ソート装置１０αは秘密ソート装置１０βから受信したａβγと秘密ソート装置１０γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密ソート装置１０βは秘密ソート装置１０γから受信したａγαと秘密ソート装置１０αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密ソート装置１０γは秘密ソート装置１０αから受信したａαβと秘密ソート装置１０βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。
【００８１】
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。
【００８２】
Ｃ＝Ａ−Ｂの秘密計算
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα−ｂγα，ａαβ−ｂαβ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβ−ｂαβ，ａβγ−ｂβγ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ−ｂβγ，ａγα−ｂγα）を計算して記録する。
【００８３】
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密ソート装置１０βの処理はない。
【００８４】
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密ソート装置１０αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。
【００８５】
Ｃ＝ＡＢの秘密計算
（１）秘密ソート装置１０αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）−ｒ１−ｒ２−ｃγαを計算する。そして、秘密ソート装置１０αは、秘密ソート装置１０βに（ｒ１，ｃαβ）を、秘密ソート装置１０γに（ｒ２，ｃγα）を送信する。
（２）秘密ソート装置１０βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密ソート装置１０γに送信する。
（３）秘密ソート装置１０γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密ソート装置１０αに送信する。
（４）秘密ソート装置１０βと秘密ソート装置１０γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密ソート装置１０αは（ｃγα，ｃαβ）を記録し、秘密ソート装置１０βは（ｃαβ，ｃβγ）を記録し、秘密ソート装置１０γは（ｃβγ，ｃγα）を記録する。
【００８６】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
秘密ソート装置１０αは
（ｃγα，ｃαβ）＝（１−ａγα，−ａαβ ｍｏｄ Ｗ）
を計算して記録し、秘密ソート装置１０βは
（ｃαβ，ｃβγ）＝（−ａαβ ｍｏｄ Ｗ，−ａβγ ｍｏｄ Ｗ）
を計算して記録し、秘密ソート装置１０γは
（ｃβγ，ｃγα）＝（−ａβγ ｍｏｄ Ｗ，１−ａγα）
を計算して記録する。
【００８７】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行う。
【００８８】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密ソート装置１０αが断片（ｃγα’，ｃαβ’）を、秘密ソート装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密ソート装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密ソート装置１０αが断片（ｃγα”，ｃαβ”）を、秘密ソート装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密ソート装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密ソート装置１０α，１０β，１０γは、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、秘密ソート装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密ソート装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密ソート装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密ソート装置１０αが断片（ｃγα，ｃαβ）を、秘密ソート装置１０βが断片（ｃαβ，ｃβγ）を、秘密ソート装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００８９】
ビットの排他的論理和（Ｃ＝Ａ［∨］Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密ソート装置１０αが断片（ｃγα’，ｃαβ’）を、秘密ソート装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密ソート装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密ソート装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密ソート装置１０αが断片（ｃγα”，ｃαβ”）を、秘密ソート装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密ソート装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密ソート装置１０α，１０β，１０γは、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、秘密ソート装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密ソート装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密ソート装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密ソート装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密ソート装置１０αが断片（ｃγα，ｃαβ）を、秘密ソート装置１０βが断片（ｃαβ，ｃβγ）を、秘密ソート装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００９０】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００９１】
【数４】
【００９２】
を求めることである。また、秘密ソート装置１０α，１０β，１０γが分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）γα，ａ（ｎ）αβ）、（ａ（ｎ）αβ，ａ（ｎ）βγ）、（ａ（ｎ）βγ，ａ（ｎ）γα）とする。秘密ソート装置１０αは、
【００９３】
【数５】
【００９４】
を計算して記録し、秘密ソート装置１０βは
【００９５】
【数６】
【００９６】
を計算して記録し、秘密ソート装置１０γは
【００９７】
【数７】
【００９８】
を計算して記録する。
【００９９】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、秘密ソート装置１０βが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）を秘密分散し、秘密ソート装置１０α，１０β，１０γが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）の断片（ｂ（ｎ）γα，ｂ（ｎ）αβ）、（ｂ（ｎ）αβ，ｂ（ｎ）βγ）、（ｂ（ｎ）βγ，ｂ（ｎ）γα）を分散して記録する。ｎ＝０からＮ−１について、秘密ソート装置１０γが（ａγα）（ｎ）を秘密分散し、秘密ソート装置１０α，１０β，１０γが（ａγα）（ｎ）の断片（（ａγα）（ｎ）γα，（ａγα）（ｎ）αβ）、（（ａγα）（ｎ）αβ，（ａγα）（ｎ）βγ）、（（ａγα）（ｎ）βγ，（ａγα）（ｎ）γα）を分散して記録する。
（２）ｃγα＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａγα）（ｎ）−２ｂ（ｎ）（ａγα）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａγα）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａγα）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【０１００】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０６】
１０１，…，１０Ｎ 秘密ソート装置 １００１，…，１００Ｎ 秘密分散装置
１０５ 選択手段 １１０１，…，１１０Ｎ 断片置換部
１２０１，…，１２０Ｎ 再分散部 １３０１，…，１３０Ｎ 初期情報分散部
１４０１，…，１４０Ｎ 初期乗算部 １５０１，…，１５０Ｎ 確認分散部
１６０１，…，１６０Ｎ 確認乗算部 １７０１，…，１７０Ｎ 改ざん検出部
１９０１，…，１９０Ｎ 記録部 ３００１，…，３００Ｎ ソート制御部
３１０ ランダム置換手段 ３１０１，…，３１０Ｎ ランダム置換部
３２０ 復号手段 ３２０１，…，３２０Ｎ 復号部
３３０ ソート手段 ３３０１，…，３３０Ｎ ソート部
３４０ 行列生成手段 ３４０１，…，３４０Ｎ 行列生成部
３５０ 列ベクトル変換手段 ３５０１，…，３５０Ｎ 列ベクトル変換部
３６０ 列ベクトル計算手段 ３６０１，…，３６０Ｎ 列ベクトル計算部
３７０ 行列変換手段 ３７０１，…，３７０Ｎ 行列変換部
３８０ 行列計算手段 ３８０１，…，３８０Ｎ 行列計算部
３９０ ソート情報計算手段 ３９０１，…，３９０Ｎ ソート情報計算部
１０００ ネットワーク
【特許請求の範囲】
【請求項１】
３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソートシステムであって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるランダム置換手段と、
情報［ｃＲ］を復号し、情報ｃＲを求める復号手段と、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるソート手段と
を備える秘密ソートシステム。
【請求項２】
請求項１記載の秘密ソートシステムであって、
ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備える秘密ソートシステム。
【請求項３】
請求項１記載の秘密ソートシステムであって、
ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備え、
前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソートシステム。
【請求項４】
請求項１記載の秘密ソートシステムであって、
Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値、表［Ｘ］はＢが大きい方を優先してレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を１、ａｂｍ≠ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を０とするＭ行Ｄｂ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤｂの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄｂ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄｂ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備え、
前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソートシステム。
【請求項５】
Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める３個以上の秘密ソート装置で構成される秘密ソートシステムの中の秘密ソート装置であって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるためのランダム置換部と、
情報［ｃＲ］を復号し、情報ｃＲを求めるための復号部と、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるためのソート部と
を備える秘密ソート装置。
【請求項６】
３個以上の秘密ソート装置を用いて、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソート方法であって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間のランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるランダム置換ステップと、
情報［ｃＲ］を復号し、情報ｃＲを求める復号ステップと、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるソートステップと
を有する秘密ソート方法。
【請求項７】
請求項６記載の秘密ソート方法であって、
ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有する秘密ソート方法。
【請求項８】
請求項６記載の秘密ソート方法であって、
ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成ステップと、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有し、
前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソート方法。
【請求項９】
請求項６記載の秘密ソート方法であって、
Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値、表［Ｘ］はＢが大きい方を優先してレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を１、ａｂｍ≠ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を０とするＭ行Ｄｂ列の行列［Ｈ］を生成する行列生成ステップと、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤｂの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄｂ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄｂ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有し、
前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソート方法。
【請求項１０】
請求項１から４のいずれかに記載の秘密ソートシステムの各秘密ソート装置としてコンピュータを機能させるための秘密ソートプログラム。
【請求項１】
３個以上の秘密ソート装置で構成され、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソートシステムであって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるランダム置換手段と、
情報［ｃＲ］を復号し、情報ｃＲを求める復号手段と、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるソート手段と
を備える秘密ソートシステム。
【請求項２】
請求項１記載の秘密ソートシステムであって、
ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備える秘密ソートシステム。
【請求項３】
請求項１記載の秘密ソートシステムであって、
ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備え、
前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソートシステム。
【請求項４】
請求項１記載の秘密ソートシステムであって、
Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値、表［Ｘ］はＢが大きい方を優先してレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を１、ａｂｍ≠ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を０とするＭ行Ｄｂ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤｂの列ベクトル［ｈ］を求める列ベクトル変換手段と、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算手段と、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄｂ列の行列［Ｇ］を生成する行列変換手段と、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄｂ列の行列［Ｅ］を、秘密計算で求める行列計算手段と、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算手段と、
を備え、
前記行列生成手段、前記列ベクトル変換手段、前記列ベクトル計算手段、前記行列変換手段、前記行列計算手段、前記ソート情報計算手段、前記ランダム置換手段、前記復号手段、前記ソート手段の処理を、前記ソート手段が求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソートシステム。
【請求項５】
Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める３個以上の秘密ソート装置で構成される秘密ソートシステムの中の秘密ソート装置であって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるためのランダム置換部と、
情報［ｃＲ］を復号し、情報ｃＲを求めるための復号部と、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるためのソート部と
を備える秘密ソート装置。
【請求項６】
３個以上の秘密ソート装置を用いて、Ｍ個のレコードからなる表Ｘの各要素が秘密分散された表［Ｘ］から、表Ｘのレコードを並び替えた表に対応する秘密分散された表を求める秘密ソート方法であって、
Ｍは２以上の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、ｃは異なるＭ個の値を並べたものでレコード間をランダム置換してもソート後に何番目になるかを一意に決定できる情報とし、
情報［ｃ］のＭ個の要素と表［Ｘ］のＭ個のレコードとの対応を維持したまま秘密計算でレコード間のランダム置換し、ランダム置換された情報［ｃＲ］と表［ＸＲ］を求めるランダム置換ステップと、
情報［ｃＲ］を復号し、情報ｃＲを求める復号ステップと、
情報ｃＲが示す順番に表［ＸＲ］の各レコードを並べなおし、表［ＸＳ］を求めるソートステップと
を有する秘密ソート方法。
【請求項７】
請求項６記載の秘密ソート方法であって、
ｋ、Ｄは整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙ１，…，ｙＤはソートしたい順序ｙ１＜…＜ｙＤが定義されたＤ種類の値、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありｙ１，…，ｙＤのいずれかの値、ａｍはｘｍ（ｋ）の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｍ＝ｙｄならばＨｍｄ＝１、ａｍ≠ｙｄならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成手段と、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有する秘密ソート方法。
【請求項８】
請求項６記載の秘密ソート方法であって、
ｋ、Ｂ、Ｄは整数、ｂは１以上Ｂ以下の整数、ｄは１以上Ｄ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｘｍ（ｋ）はレコードｘｍのｋ番目のデータでありＢ桁のＤ進数の値、ａｂｍはｘｍ（ｋ）の下位からｂ桁目の値、表［Ｘ］はレコードｘｍのｋ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｄ−１ならばＨｍｄ＝１、ａｂｍ≠ｄ−１ならばＨｍｄ＝０であるＨｍｄをｍ行ｄ列の要素とするＭ行Ｄ列の行列［Ｈ］を生成する行列生成ステップと、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有し、
前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソート方法。
【請求項９】
請求項６記載の秘密ソート方法であって、
Ｂは整数、ｋ１，…，ｋＢとＤ１，…，ＤＢは整数、ｂは１以上Ｂ以下の整数、ｄｂは１以上Ｄｂ以下の整数、ｍは１以上Ｍ以下の整数、ｘ１，…，ｘＭは表Ｘのレコード、ｙｂ（１），…，ｙｂ（Ｄｂ）はソートしたい順序ｙｂ（１）＜…＜ｙｂ（Ｄｂ）が定義されたＤｂ種類の値、ｘｍ（ｋｂ）はレコードｘｍのｋｂ番目のデータでありｙｂ（１），…，ｙｂ（Ｄｂ）のいずれかの値、ａｂｍはｘｍ（ｋｂ）の値、表［Ｘ］はＢが大きい方を優先してレコードｘｍのｋ１番目からｋＢ番目のデータの値に基づいて昇順となるようにソートされるとし、
さらに、
ａｂｍ＝ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を１、ａｂｍ≠ｙｂ（ｄｂ）ならばｍ行ｄｂ列の要素を０とするＭ行Ｄｂ列の行列［Ｈ］を生成する行列生成ステップと、
行列［Ｈ］の各列を左の列から順に上から下に縦につなげて要素数ＭＤｂの列ベクトル［ｈ］を求める列ベクトル変換ステップと、
ｉ番目の要素が、列ベクトル［ｈ］の１番目の要素からｉ番目の要素までの和である列ベクトル［ｕ］を、秘密計算で求める列ベクトル計算ステップと、
列ベクトル［ｕ］をＭ要素ごとに分割してＤ個の列ベクトルを左から順に並べたＭ行Ｄｂ列の行列［Ｇ］を生成する行列変換ステップと、
行列［Ｇ］と行列［Ｈ］の要素ごとの積を要素とするＭ行Ｄｂ列の行列［Ｅ］を、秘密計算で求める行列計算ステップと、
行列［Ｅ］の行ごとの要素の総和を秘密計算で求め、前記総和を要素として行の順番に並べた情報を前記情報［ｃ］とするソート情報計算ステップと、
を有し、
前記行列生成ステップ、前記列ベクトル変換ステップ、前記列ベクトル計算ステップ、前記行列変換ステップ、前記行列計算ステップ、前記ソート情報計算ステップ、前記ランダム置換ステップ、前記復号ステップ、前記ソートステップを、前記ソートステップが求めた表［ＸＳ］を次のソートの対象の表［Ｘ］としながら、ｂ＝１からｂ＝Ｂまで繰り返す
ことを特徴とする秘密ソート方法。
【請求項１０】
請求項１から４のいずれかに記載の秘密ソートシステムの各秘密ソート装置としてコンピュータを機能させるための秘密ソートプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−１５４９９０（Ｐ２０１２−１５４９９０Ａ）
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願番号】特願２０１１−１１７５３（Ｐ２０１１−１１７５３）
【出願日】平成２３年１月２４日（２０１１．１．２４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願日】平成２３年１月２４日（２０１１．１．２４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]