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