説明

秘密マッチングシステム、秘密マッチング装置、秘密マッチング方法、秘密マッチングプログラム

【課題】各レコードが対応している2つ以上の表の中でソートに必要な要素を含む表だけで秘密計算によるソートを行った場合でも、ソートが終わった後にすべての表のレコード同士を結びつける。
【解決手段】本発明の秘密マッチングシステムは、3個以上の秘密マッチング装置で構成され、それぞれM個のレコードからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する。本発明の秘密マッチングシステムは、あらかじめ対応するレコード同士に目印となるデータをそれぞれ持たせておく。そして、ソートなどの処理が終わった後で、この目印を使うことで対応するレコード同士を結びつける。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密マッチングシステム、秘密マッチング装置、秘密マッチング方法、秘密マッチングプログラムに関する。
【背景技術】
【0002】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、例えば非特許文献1の秘密計算と呼ばれる方法がある。非特許文献1の方法では、3つの秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算(否定,論理積,論理和,排他的論理和)、データ形式変換(整数,二進数)の結果を3つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。非特許文献2では、ソートの前後の値の対応を誰にも知られないように計算することを特徴とし、暗号化された複数のデータに対し、平文から計算される値でソートを行った結果の暗号文を計算する秘密ソート方法が提案されている。非特許文献2では、クイックソートなどの任意の比較ソートを、比較回数を増やすことなく秘密計算上で実現している。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能3パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献2】濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “3パーティ秘匿関数計算上のランダム置換プロトコル”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【0004】
通常、複数のレコードを有する表のレコードのソートを行う場合、レコードに含まれる要素は、ソートの計算に直接使われる要素(値)とソートの計算に直接使われない要素(値)の2種類に分けられる。例えば、各レコードが(年齢,性別,体重,年収)の4つ要素の組であり、体重に関して昇順にソートしたい場合、各レコードのうち年齢,性別,年収の要素はソートの計算には直接使われない。しかしながら、従来技術では、ソートなどでレコードの並び替えを行う場合に、ソートの計算に直接使われない要素(値)も含めて並び替えが行われており、計算効率が悪かった。また、秘密計算上のソートなどの処理では、情報を隠すためにソートの前後の対応を誰にも分からないように並び替えを行う必要がある。このため、ソートに必要のない要素をソートに必要な要素から切り離してしまうと、ソートが終わった後にもともと同じレコードであった要素同士を結びつけることができなかった。
【0005】
本発明は、各レコードが対応している2つ以上の表の中でソートに必要な要素を含む表だけで秘密計算によるソートを行った場合でも、ソートが終わった後にすべての表のレコード同士を結びつける技術を提供することを目的とする。
【課題を解決するための手段】
【0006】
本発明の秘密マッチングシステムは、3個以上の秘密マッチング装置で構成され、それぞれM個のレコードx1j,…,xMjからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する。ここで、Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[h]に対応するベクトル、[XjS]は前記所定の処理後の表[X]に対応する表とする。なお、上記のように所定の処理では、何個かの表に対しては何の処理も行わない場合もある。何の処理も行わなかった場合は、[XjS]=[X]である。
【0007】
本発明の秘密マッチングシステムは、対応用ベクトル生成手段、対応用ランダム置換手段、対応用ベクトル復号手段、対応用並び替え手段を備える。対応用ベクトル生成手段は、M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求める。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける。対応用ランダム置換手段は、j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める。対応用ベクトル復号手段は、ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求める。対応用並び替え手段は、レコードの順番を維持する表[XiR]以外の表[XjR](ただし、j=1,…,Jかつj≠i)のレコードをhjR=hiRとなるように並び替える。
【発明の効果】
【0008】
本発明の秘密マッチングシステムによれば、ソートなどを行う場合にデータ本体を動かすのではなくポインタを動かせばよいという、通常の計算機上ではよく使われるテクニックを秘密計算で実現できる。秘密計算上でソートを行う場合には、情報を隠す必要があるため、ソートの前後のデータ間の対応を誰にもわからないように処理がなされる。そのため、単純に表のレコードを分割して2つ以上の表を作ってしまうと、ソート後に対応するレコード同士のマッチングを行うことができなかった。本発明の秘密マッチングシステムでは、あらかじめ対応するレコード同士に目印となるデータをそれぞれ持たせておく。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。このように、本発明の秘密マッチングシステムによれば、ソートに必要な部分だけでソートを行い、ソートが終わった後でその他の部分を移動させることができるようになるので、計算効率を改善できる。
【図面の簡単な説明】
【0009】
【図1】実施例1の秘密マッチングシステムの機能構成例を示す図。
【図2】実施例1の秘密マッチングシステムの処理フローを示す図。
【図3】実施例2の秘密マッチングシステムの機能構成例を示す図。
【図4】実施例2の秘密マッチングシステムの処理フローを示す図。
【図5】実施例3の秘密マッチングシステムの機能構成例を示す図。
【図6】実施例3の秘密マッチングシステムの処理フローを示す図。
【図7】本発明に利用できる秘密分散装置100の機能構成例を詳しく示した秘密マッチングシステムを示す図。
【図8】ランダム置換の1つ目の処理フロー例を示す図。
【図9】ランダム置換の2つ目の処理フロー例を示す図。
【発明を実施するための形態】
【0010】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例1】
【0011】
図1に実施例1の秘密マッチングシステムの機能構成例を示す。図2に実施例1の秘密マッチングシステムの処理フローを示す。実施例1の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置10,…,10で構成される。そして、実施例1の秘密マッチングシステムは、それぞれM個のレコードx1j,…,xMjからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する。ここで、Mは2以上の整数、Nは3以上の整数、Jは2以上の整数、nは1以上N以下の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は所定の処理後のベクトル[h]に対応するベクトル、[XjS]は所定の処理後の表[X]に対応する表とする。なお、上記のように所定の処理では、何個かの表に対しては何の処理も行わない場合もある。何の処理も行わなかった場合は、[XjS]=[X]である。
【0012】
秘密マッチング装置10は、マッチング制御部300、秘密分散装置100、記録部190を備える。秘密分散装置100は、マッチング制御部300の指示にしたがって実施例1の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、ランダム置換などがある。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、1つの例であり、本発明が利用できる秘密計算を限定するものではない。記録部190は、秘密マッチング装置10の処理に必要な情報を記録する構成部である。図1に示した選択手段105は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。
【0013】
各秘密マッチング装置10のマッチング制御部300は、対応用ベクトル生成部310、対応用ランダム置換部320、対応用ベクトル復号部330、対応用並び替え部340を備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310(図示していない)は対応用ベクトル生成部310,…,310で構成され、対応用ランダム置換手段320(図示していない)は対応用ランダム置換部320,…,320で構成され、対応用ベクトル復号手段330(図示していない)は対応用ベクトル復号部330,…,330で構成され、対応用並び替え手段340(図示していない)は対応用並び替え部340,…,340で構成される。
【0014】
対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求める。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、所定の処理を施しても対応が維持されるように対応付ける(S310)。より具体的には、対応用ベクトル生成部310,…,310(対応用ベクトル生成手段310)は、M個の異なる値を要素に持つベクトルhを生成し、秘密分散装置100,…,100にベクトルhの各要素を秘密分散させてベクトル[h]を求めさせ、ベクトル[h]をランダム置換させてベクトル[h]を求めさせる。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに対応付ける。
【0015】
次に、ソートのようなレコードの順番が変わる可能性がある所定の処理を、表[X],…,[X]一部または全部に対して実行し、処理後の表[X1S],…,[XJS]を得る(S315)。したがって、表[X1S],…,[XJS]では、もともと対応していたレコード同士が異なる順番となっている可能性がある。
【0016】
なお、ステップS315の所定の処理は、後述の秘密計算の四則演算や秘密計算の論理演算を組み合わせればよい。例えば、x=yかを秘密計算で確認する場合には、従来技術として蓄積された論理回路の技術を用いれば、実現できる。例えば、xとyを2ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。
【0017】
C=1−{(x[∨]y)∨・・・∨(x[∨]y)} (1)
ただし、[∨]は排他的論理和(XOR)を示す記号、∨は論理和(OR)を示す記号、xは2ビット展開したときのxの下からbビット目の値、yは2ビット展開したときのyの下からbビット目の値、Bは2ビット展開したときのxとyの桁数とする。式(1)では、C=1ならばx=y(真)、C=0ならばx≠y(偽)である。また、式(1)の個々の演算は後述の秘密計算の例に示されているので、式(1)の演算は秘密計算で実行でき、秘密分散された[C]が求められる。したがって、確認後の分岐も秘密にするのであれば、[C]を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、所望の演算を後述する秘密計算の方法の組合せで実行できる。
【0018】
対応用ランダム置換手段320は、j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める(S320)。より具体的には、対応用ランダム置換部320,…,320(対応用ランダム置換手段320)は、j=1〜Jについて、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置100,…,100に実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。
【0019】
対応用ベクトル復号手段330は、ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求める(S330)。より具体的には、対応用ベクトル復号部330,…,330(対応用ベクトル復号手段330)は、秘密分散装置100,…,100にベクトル[h1R],…,[hJR]を復号させ、ベクトルh1R,…,hJRを求める。
【0020】
対応用並び替え手段340は、すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替える(S340)。より具体的には、対応用並び替え部340,…,340(対応用並び替え手段340)は、レコードの順番を維持する表[XiR]を特定する。そして、表[XiR]以外の表[XjR](ただし、j=1,…,Jかつj≠i)のレコードをhjR=hiRとなるように並び替えればよい。
【0021】
本実施例の秘密マッチングシステムでは、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[h]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。このように、本実施例の秘密マッチングシステムによれば、ソートに必要な部分だけでソートを行い、ソートが終わった後でその他の部分を移動させることができるようになるので、計算効率を改善できる。
【実施例2】
【0022】
図3に実施例2の秘密マッチングシステムの機能構成例を示す。図4に実施例2の秘密マッチングシステムの処理フローを示す。実施例2の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置20,…,20で構成される。そして、実施例2の秘密マッチングシステムは、M個のレコードを持つ表[X]の各レコードの一部または全部の要素を用いてソートを行う。また、表[X]に対しては何も行わない。ここで、Mは2以上の整数、Nは3以上の整数、J=2、nは1以上N以下の整数、jは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号とする。
【0023】
秘密マッチング装置20は、マッチング制御部400、秘密分散装置100、記録部190を備える。秘密分散装置100は、マッチング制御部400の指示にしたがって実施例2の処理に必要な個々の秘密計算を行う。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではないので、秘密計算については、例を後述することとし、本実施例での説明は省略する。
【0024】
各秘密マッチング装置20のマッチング制御部400は、対応用ベクトル生成部310、対応用ランダム置換部320、対応用ベクトル復号部330、対応用並び替え部340、表分割部405、ベクトル結合部450、表結合部460、表ランダム置換部470、ソート用ベクトル復号部480、ソート部490を備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310(図示していない)は対応用ベクトル生成部310,…,310で構成され、対応用ランダム置換手段320(図示していない)は対応用ランダム置換部320,…,320で構成され、対応用ベクトル復号手段330(図示していない)は対応用ベクトル復号部330,…,330で構成され、対応用並び替え手段340(図示していない)は対応用並び替え部340,…,340で構成され、表分割手段405(図示していない)は表分割部405,…,405で構成され、ベクトル結合手段450(図示していない)はベクトル結合部450,…,450で構成され、表結合手段460(図示していない)は表結合部460,…,460で構成され、表ランダム置換手段470(図示していない)は表ランダム置換部470,…,470で構成され、ソート用ベクトル復号手段480(図示していない)はソート用ベクトル復号部480,…,480で構成され、ソート手段490(図示していない)はソート部490,…,490で構成される。
【0025】
表分割手段405は、表[X]を、表[X]と表[X]に、表[X]が少なくとも所定の処理に用いる要素を含むように分割する(S405)。より具体的には、表分割部405,…,405(表分割手段405)は、秘密分散装置100,…,100に、表[X]を、それぞれM個のレコードx1j,…,xMjからなりレコード同士が対応付けられている表[X]と表[X]に分割させる。
【0026】
対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求める。そして、j=1,2について、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、所定の処理を施しても対応が維持されるように対応付ける(S310)。より具体的には、対応用ベクトル生成部310,…,310(対応用ベクトル生成手段310)は、M個の異なる値を要素に持つベクトルhを生成し、秘密分散装置100,…,100にベクトルhの各要素を秘密分散させてベクトル[h]を求めさせ、ベクトル[h]をランダム置換させてベクトル[h]を求めさせる。そして、j=1,2について、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに対応付ける。
【0027】
次に、レコードの順番が変わる可能性がある所定の処理を、表[X]に対して実行し、処理後の表[X1S]と表[X2S]を得る(S315)。なお、表[X]はソートには関係ない要素のみからなる表なので、ソートは実行されない。したがって、表[X1S]と表[X2S]のレコードの順番は異なる可能性がある。
【0028】
ベクトル結合手段450は、異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付ける(S450)。より具体的には、ベクトル結合部450,…,450(ベクトル結合手段450)は、異なる値を持つM個の要素からなるベクトルcを作成し、秘密分散装置100,…,100に各要素を秘密分散してベクトル[c]を求めさせる。そして、所定の処理(例えば、表[X]は特定の要素に基づいてソートし、表[X]に対しては何もしないという処理)の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付けさせる。なお、ベクトルcの各要素は、表の各レコードの順番を示すための値であり、例えば1からMの値を用いればよい。しかし、1からMの値に限定する必要はない。また、表[X]に対しては何も行っていないので、[X2S]=[X]である。
【0029】
対応用ランダム置換手段320は、j=1,2について、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める(S320)。より具体的には、対応用ランダム置換部320,…,320(対応用ランダム置換手段320)は、j=1,2について、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置100,…,100に実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。
【0030】
対応用ベクトル復号手段330は、ベクトル[h1R],[h2R]を復号し、ベクトルh1R,h2Rを求める(S330)。より具体的には、対応用ベクトル復号部330,…,330(対応用ベクトル復号手段330)は、秘密分散装置100,…,100にベクトル[h1R],[h2R]を復号させ、ベクトルh1R,h2Rを求める。
【0031】
対応用並び替え手段340は、表[X2R]のレコードをh2R=h1Rとなるように並び替える(S340)。より具体的には、対応用並び替え部340,…,340(対応用並び替え手段340)は、表[X1R]以外の表[X2R]のレコードをh2R=h1Rとなるように並び替える。
【0032】
表結合手段460は、表[X1R],[X2R]を結合して表[X]を得る(S460)。より具体的には、表結合部460,…,460(表結合手段460)は、表[X1R],[X2R]へのベクトル[h1R],[h2R]の対応付けを解除し、表[X1R],[X2R]を結合して表[X]を得る。
【0033】
表ランダム置換手段470は、表[X]のレコード間を秘密計算でランダム置換し、表[XRR]を求める(S470)。より具体的には、表ランダム置換部470,…,470(表ランダム置換手段470)は、秘密分散装置100,…,100に表[X]のレコード間を秘密計算でランダム置換させ、表[XRR]を求めさせる。
【0034】
ソート用ベクトル復号手段480は、表[X1S]に対応付けされたベクトル[c]の表ランダム置換手段470の処理後のベクトル[cRR]を復号し、ベクトルcRRを求める(S480)。より具体的には、表[X1S]に対応付けされたベクトル[c]は、表ランダム置換手段470の処理によってランダム置換されベクトル[cRR]となっている。ソート用ベクトル復号部480,…,480(ソート用ベクトル復号手段480)は、このベクトル[cRR]と表[XRR]との対応付けを解除して、秘密分散装置100,…,100にベクトル[cRR]を復号させ、ベクトルcRRを求める。
【0035】
ソート手段490は、ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動する(S490)。例えば、ベクトルcが1からMまで順番に並んだベクトルであれば、ソート手段(S490)は、ベクトルcRRの各要素に示された順番に、表[XRR]の各レコードを移動すればよい(S490)。
【0036】
本実施例の秘密マッチングシステムも、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[h]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。また、所定の処理(ソートのようにレコードの順番が変わる可能性のある処理)の前に、所定の処理に必要な要素を含む表[X]と所定の処理に必要ない要素からなる表[X]に表[X]を分割した上で、表[X]に対してのみ所定の処理を行い、所定の処理が終わった後で表[X]を結合し、所定の処理後の順番にレコードの順番を戻すので、計算効率を改善できる。
【実施例3】
【0037】
図5に実施例3の秘密マッチングシステムの機能構成例を示す。図6に実施例3の秘密マッチングシステムの処理フローを示す。実施例3の秘密マッチングシステムは、ネットワーク1000を介して接続されたN個の秘密マッチング装置30,…,30で構成される。そして、実施例3の秘密マッチングシステムでは、所定の処理がB個の処理F,…,Fからなる。処理FはM個のレコードを持つ表[X],…,[X]の一部または全部用いる処理である。また、所定の処理は、処理Fごとに定められた処理であり、処理に用いる表も処理Fごとに決められる。ここで、Mは2以上の整数、Nは3以上の整数、Jは2以上の整数、nは1以上N以下の整数、iとjは1以上J以下の整数、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b(1),…,b(D)は1以上D以下の異なる整数、D’は1以上の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号とする。
【0038】
秘密マッチング装置30は、マッチング制御部500、秘密分散装置100、記録部190を備える。秘密分散装置100は、マッチング制御部500の指示にしたがって実施例3の処理に必要な個々の秘密計算を行う。ただし、本発明は、これらの秘密計算を利用して効率よくソートを行うものであり、秘密計算自体に特徴がある発明ではないので、秘密計算については、例を後述することとし、本実施例での説明は省略する。
【0039】
各秘密マッチング装置30のマッチング制御部500は、対応用ベクトル生成部310、対応用ランダム置換部320、対応用ベクトル復号部330、対応用並び替え部340、表分割部505、処理用ランダム置換部520、処理用ベクトル復号部530、処理用並び替え部540、処理用ベクトル対応部550、処理部560、処理用繰返部570を備える。そして、秘密マッチングシステムの対応用ベクトル生成手段310(図示していない)は対応用ベクトル生成部310,…,310で構成され、対応用ランダム置換手段320(図示していない)は対応用ランダム置換部320,…,320で構成され、対応用ベクトル復号手段330(図示していない)は対応用ベクトル復号部330,…,330で構成され、対応用並び替え手段340(図示していない)は対応用並び替え部340,…,340で構成され、表分割手段505(図示していない)は表分割部505,…,505で構成され、処理用ランダム置換手段520(図示していない)は処理用ランダム置換部520,…,520で構成され、処理用ベクトル復号手段530(図示していない)は処理用ベクトル復号部530,…,530で構成され、処理用並び替え手段540(図示していない)は処理用並び替え部540,…,540で構成され、処理用ベクトル対応手段550(図示していない)は処理用ベクトル対応部550,…,550で構成され、処理手段560(図示していない)は処理部560,…,560で構成され、処理用繰返手段570(図示していない)は処理用繰返部570,…,570で構成される。
【0040】
表分割手段505は、表[X]をJ個に分割して前記の表[X],…,[X]を求める(S505)。より具体的には、表分割部505,…,505(表分割手段505)は、表[X]を、それぞれM個のレコードx1j,…,xMjからなりレコード同士が対応付けられているJ個の表[X],…,[X]に分割する。これらの表[X],…,[X]が実施例1の表[X],…,[X]と同じである。なお、表分割手段505は、ベクトルc=(1,2,…,M)(ただし、ここでのTは転置を示す)の各要素を秘密分散することで生成した表[c]をJ個の表[X],…,[X]の中に含めてもよい。このように、J個の表とは表[X]に含まれた要素以外を含んでもよい。
【0041】
対応用ベクトル生成手段310は、M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求める。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、所定の処理を施しても対応が維持されるように対応付ける(S310)。より具体的には、対応用ベクトル生成部310,…,310(対応用ベクトル生成手段310)は、M個の異なる値を要素に持つベクトルhを生成し、秘密分散装置100,…,100にベクトルhの各要素を秘密分散させてベクトル[h]を求めさせ、ベクトル[h]をランダム置換させてベクトル[h]を求めさせる。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに対応付ける。
【0042】
処理用繰返手段570(処理用繰返部570,…,570)は、bに1を代入し、繰返し処理の初期化を行う(S571)。
【0043】
処理用ランダム置換手段520は、処理Fに必要な要素を有する表[Xb(1)],…,[Xb(D)]を選び、b(d)=b(1),…,b(D)について、表[Xb(d)]とベクトル[hb(d)]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[Xb(d)R]とベクトル[hb(d)R]とを求める(S520)。より具体的には、処理用ランダム置換部520,…,520(処理用ランダム置換手段520)は、処理Fに必要な要素を有する表[Xb(1)],…,[Xb(D)]を表[X],…,[X]の中から選ぶ。ここで、Dはbごとに決まる1以上J以下の整数である。例えば、処理Fのときには2つの表を選び、処理Fのときには3つの表を選ぶのであれば、b=1のときはD=2、b=2のときはD=3となる。また、b(1),…,b(D)は、1〜Jのいずれかの数であり、b(1)<…<b(D)のように順番に並んでいる必要はない。例えば、ソートの処理などで優先度の高い方をb(D)とし、優先度が低い方をb(1)としてもよい。そして、処理用ランダム置換部520,…,520(処理用ランダム置換手段520)は、b(d)=b(1),…,b(D)について、表[Xb(d)]の各レコードとベクトル[hb(d)]の各要素に対して同一の全単射によるランダム置換を秘密分散装置100,…,100に実行させ、ランダム置換された表[Xb(d)R]とベクトル[hb(d)R]とを求める。なお、“表[Xb(d)]の各レコードとベクトル[hb(d)]の各要素に対して同一の全単射”とは、同じd同士の表[Xb(d)]の各レコードとベクトル[hb(d)]の各要素に対して同一の全単射であればよく、dが異なる場合は同一の全単射である必要はない。
【0044】
処理用ベクトル復号手段530は、ベクトル[hb(1)R],…,[hb(D)R]を復号し、ベクトルhb(1)R,…,hb(D)Rを求める(S530)。より具体的には、処理用ベクトル復号部530,…,530(処理用ベクトル復号手段530)は、秘密分散装置100,…,100にベクトル[hb(1)R],…,[hb(D)R]を復号させ、ベクトルhb(1)R,…,hb(D)Rを求める。
【0045】
処理用並び替え手段540は、すべてのb(i)とb(d)の組合せ(ただし、ここでのiは1,…,Dのいずれか)に対してhb(i)R=hb(d)Rとなるように表[Xb(d)R]のレコードを並び替え、表[Xb(1)T],…,[Xb(D)T]を得る(S540)。より具体的には、処理用並び替え部540,…,540(処理用並び替え手段540)は、レコードの順番を維持する表[Xb(i)R]を、表[Xb(1)R],…,[Xb(D)R]の中から特定する。そして、表[Xb(i)R]以外の表[Xb(d)R](b(d)≠b(i))のレコードをhb(i)R=hb(d)Rとなるように並び替え、表[Xb(1)T],…,[Xb(D)T]を得る。
【0046】
処理用ベクトル対応手段550は、ベクトルhb(i)Rの各要素を秘密分散したベクトル[hb(i)R]の各要素を表[Xb(1)T],…,[Xb(D)T]の各レコードに、処理Fを施しても対応が維持されるように対応付ける(S550)。より具体的には、処理用ベクトル対応部550,…,550(処理用ベクトル対応手段550)は、秘密分散装置100,…,100にベクトルhb(i)Rの各要素を秘密分散させてベクトル[hb(i)R]をもとめる。そして、ベクトル[hb(i)R]の各要素を表[Xb(1)T],…,[Xb(D)T]の各レコードに、処理Fを施しても対応が維持されるように対応付ける。
【0047】
処理手段560は、ベクトル[hb(i)R]が対応付けられた表[Xb(1)T],…,[Xb(D)T]に対して処理Fを行って、処理F後のベクトル[hb(i)F]が対応付けられた処理F後の表[Xb(1)F],…,[Xb(D’)F]を求める。そして、処理F前のJ個の表の中から0個以上、処理F後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理F後のベクトル[hjbS]と表[X1bS],…,[XJbS]を求める(S560)。例えば、D’=Dであり、処理F後の表[Xb(1)F],…,[Xb(D’)F]を、対応する処理F前の表[Xb(1)],…,[Xb(D)]に置き換えるのであれば、J’=Jとなるので、表の数Jは同じままである。また、処理F後の表[Xb(1)F],…,[Xb(D’)F]を単に加えてもよく、この場合はJ’=J+D’であり、表の数JはD’だけ増える。より具体的には、処理部560,…,560(処理手段560)は、ベクトル[hb(i)R]の対応付けを維持したまま表[Xb(1)T],…,[Xb(D)T]に対して処理Fを行って、処理F後のベクトル[hb(i)F]が対応付けられた処理F後の表[Xb(1)F],…,[Xb(D’)F]を求める。そして、処理F前のJ個の表の中から0個以上、処理F後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理F後のベクトル[hjbS]と表[X1bS],…,[XJbS]とする。
【0048】
処理用繰返手段570(処理用繰返部570,…,570)は、b=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],…,[XJbS]を表[X1S],…,[XJS]としてステップS320に進む。Noの場合はベクトル[hjbS]をベクトル[h]、表[X1bS],…,[XJbS]を表[X],…,[X]とし、ステップS573に進む(S572)。ステップS573では、処理用繰返手段570(処理用繰返部570,…,570)は、bにb+1を代入し、ステップS520に戻る。
【0049】
対応用ランダム置換手段320は、j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める(S320)。より具体的には、対応用ランダム置換部320,…,320(対応用ランダム置換手段320)は、j=1〜Jについて、表[XjS]の各レコードとベクトル[hjS]の各要素に対して同一の全単射によるランダム置換を秘密分散装置100,…,100に実行させ、ランダム置換された表[XjR]とベクトル[hjR]とを求める。
【0050】
対応用ベクトル復号手段330は、ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求める(S330)。より具体的には、対応用ベクトル復号部330,…,330(対応用ベクトル復号手段330)は、秘密分散装置100,…,100にベクトル[h1R],…,[hJR]を復号させ、ベクトルh1R,…,hJRを求める。
【0051】
対応用並び替え手段340は、レコードの順番を維持する表[XiR]以外の表[XjR](ただし、j=1,…,Jかつj≠i)のレコードをhjR=hiRとなるように並び替える(S340)。より具体的には、対応用並び替え部340,…,340(対応用並び替え手段340)は、表[XiR](ソートの対象となる要素を含んだ表)を特定する。そして、表[XiR]以外の表[XjR](ただし、j=1,…,Jかつj≠i)のレコードをhjR=hiRとなるように並び替える。
【0052】
実施例3の具体例について説明する。例えば表[X]のM個のレコードは要素としてそれぞれ属性値[v]、キー[km1],…,[kmB]を有しているとする。そして、キー[km1],…,[kmB]の順にソートを行う場合を説明する。つまり、処理Fはキー[k1b],…,[kMb]に基づいたソートを行う処理である。
【0053】
表分割手段505は、表[X]を要素[v],[km1],…,[kmB]ごとに分割して表[v],[k],…,[k]を求める。また、ベクトルc=(1,2,…,M)(ただし、ここでのTは転置を示す)の各要素を秘密分散したベクトル[c]を表[c]とする(S505)。この場合は、J=B+2であり、表[v]が表[X]、表[k]が表[X]、…、表[k]が表[XJ−1]、表[c]が表[X]に相当する。
【0054】
対応用ベクトル生成手段310は、ベクトルh=(1,2,…,M)(ただし、ここでのTは転置を示す)の各要素を秘密分散したベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求める。そして、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[v],[k],…,[k],[c]の各レコードに、所定の処理を施しても対応が維持されるように対応付ける(S310)。
【0055】
処理用繰返手段570(処理用繰返部570,…,570)は、bに1を代入し、繰返し処理の初期化を行う(S571)。
【0056】
処理用ランダム置換手段520は、処理Fに必要な要素を有する表として表[v],[k],[cb−1]を選択する。つまり、D=3であり、表[v]が表[Xb(1)]、表[k]が表[Xb(2)]、表[cb−1]が表[Xb(3)]に相当する。処理用ランダム置換手段520は、表[v]とベクトル[hb(1)]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[k]とベクトル[hb(2)]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[cb−1]とベクトル[hb(3)]との対応を維持したまま秘密計算でレコード間をランダム置換する。そして、ランダム置換された表[v],[kbR],[cb−1R]とベクトル[hb(1)R],[hb(2)R],[hb(3)R]とを求める(S520)。
【0057】
処理用ベクトル復号手段530は、ベクトル[hb(1)R],[hb(2)R],[hb(3)R]を復号し、ベクトルhb(1)R,hb(2)R,hb(3)Rを求める(S530)。
【0058】
処理用並び替え手段540は、すべてのb(i)とb(d)の組合せ(ただし、ここでのiは1,…,Dのいずれか)に対してhb(i)R=hb(d)Rとなるように表[v],[kbR],[cb−1R]のレコードを並び替え、表[v],[kbT],[cb−1T]を得る(S540)。
【0059】
処理用ベクトル対応手段550は、ベクトルhb(i)Rの各要素を秘密分散したベクトル[hb(i)R]の各要素を表[v],[kbT],[cb−1T]の各レコードに、処理Fを施しても対応が維持されるように対応付ける(S550)。
【0060】
処理手段560は、ベクトル[hb(i)R]が対応付けられた表[v],[kbT],[cb−1T]に対して処理Fを行う。例えばFは、表[cb−1T]を復号して表cb−1Tを求める。そして、表cb−1Tに従って並べ替え、表[kbT]に従って表[v]をソートして表[vNEW]を求める。また、ベクトルc=(1,2,…,M)(ただし、ここでのTは転置を示す)の各要素を秘密分散して、表[c]を求める。つまり、処理F後のD’個の表は、表[vNEW]と表[c]であり、D’=2である。そして、表[kb+1],…,[k],[vNEW],[c]を抽出し、J’個のベクトルとする。つまり、J’=B−b+2である。そして、J’を新しいJに更新し、表[vNEW]を新しい表[v]とし、処理F後のベクトル[hjbS]と表[kb+1],…,[k],[v],[c]を求める(S560)。
【0061】
処理用繰返手段570は、b=Bかを確認し、Yesの場合はベクトル[hjBS]をベクトル[hjS]としてステップS320に進む。Noの場合はベクトル[hjbS]をベクトル[h]とし、ステップS573に進む(S572)。ステップS573では、処理用繰返手段570(処理用繰返部570,…,570)は、bにb+1を代入し、ステップS520に戻る。
【0062】
対応用ランダム置換手段320は、表[v]とベクトル[h1S]との対応を維持したまま秘密計算でレコード間をランダム置換し、表[c]とベクトル[h2S]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[v],[cBR]とベクトル[h1R],[h2R]とを求める(S320)。
【0063】
対応用ベクトル復号手段330は、ベクトル[h1R],[h2R]を復号し、ベクトルh1R,h2Rを求める(S330)。
【0064】
対応用並び替え手段340は、表[c]を復号してc=(1,2,…,M)(ただし、ここでのTは転置を示す)、かつh1R=h2Rとなるように、表cと表[v]のレコードを並び替え、表[v]を求める(S340)。表[v]が所望の表である。
【0065】
本実施例の秘密マッチングシステムも、あらかじめ対応するレコード同士に目印となるデータとしてベクトル[h]をそれぞれのレコードに対応付けている。そして、ソートなどの処理が終わった後で、この目印を使うことで本来ならば途中で対応がわからなくなってしまう場合にも対応するレコード同士を結びつけることができる。また、表[X]を分割して表[X],…,[X]を求め、所定の処理の前に必要な要素を含む表[Xb(1)],…,[Xb(D)]を選定した上で、表[Xb(1)],…,[Xb(D)]に対してのみ所定の処理を行い、所定の処理が終わった後で他の表の中に戻すので、計算効率を改善できる。
【0066】
[秘密計算]
上述の説明では、秘密計算については1つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密マッチング装置10,…,10(20,…,20または30,…,30)が実行するランダム置換とその他の秘密計算について説明する。なお、以下の説明では秘密マッチング装置10について説明するが、秘密マッチング装置20,30についても同じである。また、以下の秘密計算に関する説明は、1つの例でありこれに限定されるものではない。本発明の秘密マッチングシステムでは他の秘密計算を用いてもよい。
【0067】
ランダム置換1
図7に本発明に利用できる秘密分散装置100の機能構成例を詳しく示した秘密マッチングシステムを示す。図8にランダム置換の1つ目の処理フロー例を示す。この例では、秘密マッチングシステムは選択手段105も備える。ここで、A,…,Aを各秘密マッチング装置10が断片を分散して記録するK個の数値(Kは2以上の整数)、数値Aをk番目の数値(kは1以上K以下の整数)、aknを秘密マッチング装置10が記録するk番目の断片とする。なお、数値A,…,Aが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Aが各々の人の年収を示すような数値群が考えられる。選択手段105は、いずれかの秘密マッチング装置の内部に配置されてもよいし、単独の装置であってもよい。
【0068】
秘密マッチングシステムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置100は、少なくとも断片置換部110と再分散部120と記録部190を備える。記録部190は断片a1n,…,aKnなどを記録する。また、記録部190は、自身が記録している断片aknが数値Aの何番目の断片なのかに関する情報も記録する。
【0069】
選択手段105は、N未満の数の秘密マッチング装置10を選択する(S105)。例えば、N個の断片のうちN’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がN’個以上N未満の秘密マッチング装置を選べばよい。
【0070】
断片置換手段は、少なくとも断片置換部110,…,110を含んで構成される。そして、選択手段105に選択された秘密マッチング装置10(ただし、iは選択された秘密マッチング装置を示す番号)の断片置換部110間で{1,…,K}→{1,…,K}の全単射πを作成し、選択された秘密マッチング装置10の記録部190が記録する断片aπ(k)iをk番目の断片にする(S110)。全単射πは、1〜Kを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle(参考文献1:Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.)などを用いて作成すればよい。また、全単射πは選択された秘密マッチング装置10間で生成してもよいし、選択された秘密マッチング装置10のうちの1つの秘密マッチング装置が生成して、選択された秘密マッチング装置10間で共有してもよい。
【0071】
再分散手段は、少なくとも再分散部120,…,120を含んで構成される。再分散手段は、断片置換手段によって置換された数値Aπ(k)に対応する断片aπ(k)i(k番目に置換されている)を用いて再分散化して新しい断片bk1,…,bkNを求め、数値Bの断片とする(S120)。つまり、Aπ(k)=Bの関係が成り立つが、選ばれなかった秘密マッチング装置は全単射πを知らないので、Aπ(k)=Bであることを知らない。なお、各秘密マッチング装置10の記録部190は、断片bknを記録するだけでなく、自身が記録しているk番目の断片である断片bknが数値Bの断片であるという情報も記録する。また、数値B,…,Bを新しい数値A,…,Aとし、選択手段で選択する秘密マッチング装置の組み合わせを変更すれば、この処理を繰り返すことができる(S111,S112)。
【0072】
本発明の秘密マッチングシステムによれば、限定された秘密マッチング装置間で断片をシャッフルする。したがって、選ばれなかった秘密マッチング装置は、全単射πを知らないので、数値A,…,Aと数値B,…,Bとの対応が分からない。つまり、特定の秘密マッチング装置からは数値A,…,Aと数値B,…,Bとの対応が分からない状態にしたいのであれば、その秘密マッチング装置を選択手段105で選ばないように、選択する秘密マッチング装置をあらかじめ定めればよい。また、選択手段105が選ぶ秘密マッチング装置を変更しながらこの処理を繰り返し、全ての秘密マッチング装置が選ばれなかったことがある状態にすれば、全ての秘密マッチング装置が数値A,…,Aと対応付けることができない数値B,…,Bを得ることができる。
【0073】
ランダム置換2
次のランダム置換のための秘密マッチングシステムの秘密分散装置100を詳細に示した機能構成例も図7に示す。図9にランダム置換の2つ目の処理フロー例を示す。この例でも、秘密マッチングシステムは選択手段105も備える。ここで、A,…,Aを各秘密マッチング装置10が断片を分散して記録するK個の数値(Kは2以上の整数)、数値Aをk番目の数値(kは1以上K以下の整数)、aknを秘密マッチング装置10が記録する数値Aの断片とする。
【0074】
本発明の秘密マッチングシステムは、選択手段105、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置100は、初期情報分散部130、初期乗算部140、断片置換部110、再分散部120、確認分散部150、確認乗算部160、改ざん検出部170を備える。記録部190は断片a1n,…,aKnなどを記録する。また、記録部190は、自身が記録している断片aknが数値Aの何番目の断片なのかに関する情報も記録する。
【0075】
選択手段105はランダム置換1と同じである。初期情報分散手段は、初期情報分散部130,…,130で構成される。そして、選択手段105に選択された秘密マッチング装置10の初期情報分散部130は、秘密マッチング装置10,…,10のどれも知らないK個の数値P,…,Pそれぞれの断片p1n,…,pKnを秘密計算によって求め、記録部190に記録する(S130)。具体的には、選択手段105に選択された秘密マッチング装置から、2つ以上の秘密マッチング装置を選定する。そして、選定された秘密マッチング装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、2つの秘密マッチング装置10,10を選定し(ただし、i≠j)、秘密マッチング装置10が生成した数値の断片と、秘密マッチング装置10が生成した数値の断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密マッチング装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を2つとしたが、2つ以上でもかまわない。
【0076】
初期乗算手段は、初期乗算部140,…,140で構成される。初期乗算部140,…,140は、S=P×Aである数値Sの断片sk1,…,skNを秘密計算によって求め、記録部190,…,190に分散して記録する(S140)。
【0077】
断片置換手段と再分散手段は、ランダム置換1と同じである。確認分散手段は、確認分散部150,…,150で構成される。確認分散部150,…,150は、k=1〜Kについて、Q=Pπ(k)である数値Qの断片qk1,…,qkNを秘密計算によって生成し、記録部190,…,190に分散して記録する(S150)。具体的には、ステップS130で選定された秘密マッチング装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップS130で選定された秘密マッチング装置10が数値Pπ(k)用に生成した数値の別の断片(新しい断片)と、ステップS130で選定された秘密マッチング装置10が数値Pπ(k)用に生成した数値の別の断片(新しい断片)を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Q=Pπ(k)であり、かつ、全ての秘密マッチング装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密マッチング装置を2つとしたが、ステップS130と同じように2つ以上でもかまわない。
【0078】
確認乗算手段は、確認乗算部160,…,160で構成される。確認乗算部160,…,160は、T=Q×Bである数値Tの断片tk1,…,tkNを秘密計算によって求め、記録部190,…,190に分散して記録する(S160)。
【0079】
改ざん検出手段は、改ざん検出部170,…,170で構成される。改ざん検出部170,…,170は、k=1〜Kについて、T=Sπ(k)であることを確認する(S170)。tkn≠sπ(k)nの場合には、改ざんがあったとして異常終了する。また、数値B,…,Bを新しい数値A,…,Aとし、選択手段で選択する秘密マッチング装置の組み合わせを変更すれば、この処理を繰り返すことができる(S111,S112)。
【0080】
[その他の秘密計算]
ここでは、秘密マッチングシステムが3個の秘密マッチング装置で構成された場合の秘密計算の例を示す。また、秘密マッチング装置10,10,10の番号を固定する必要はないので、秘密マッチング装置10α,10β,10γと表現することにする。つまり、(α,β,γ)は、(1,2,3)、(2,3,1)、(3,1,2)のいずれかである。
【0081】
以下の秘密計算では、秘密マッチング装置10α,10β,10γが分散して記録する数値Aの断片を(aγα,aαβ)、(aαβ,aβγ)、(aβγ,aγα)、数値Bの断片を(bγα,bαβ)、(bαβ,bβγ)、(bβγ,bγα)、数値Cの断片を(cγα,cαβ)、(cαβ,cβγ)、(cβγ,cγα)とする。なお、以下の説明では、Wを2以上のあらかじめ定めた整数とし、計算結果はWで除した余りである。言い換えると、以下の説明の計算式では“mod W”を省略している。
【0082】
数値Aの秘密分散
(1)乱数aαβ,aβγを生成する。
(2)aγα=A−aαβ−aβγを計算し、断片を(aγα,aαβ)、(aαβ,aβγ)、(aβγ,aγα)とし、秘密マッチング装置10α,10β,10γに分散して記録する。
【0083】
数値Aの復元
(1)秘密マッチング装置10αは秘密マッチング装置10βにaγαを送信し、秘密マッチング装置10γにaαβを送信する。秘密マッチング装置10βは秘密マッチング装置10γにaαβを送信し、秘密マッチング装置10αにaβγを送信する。秘密マッチング装置10γは秘密マッチング装置10αにaβγを送信し、秘密マッチング装置10βにaγαを送信する。
(2)秘密マッチング装置10αは秘密マッチング装置10βから受信したaβγと秘密マッチング装置10γから受信したaβγとが一致していれば、aαβ+aβγ+aγαを計算して数値Aを復元する。秘密マッチング装置10βは秘密マッチング装置10γから受信したaγαと秘密マッチング装置10αから受信したaγαとが一致していれば、aαβ+aβγ+aγαを計算して数値Aを復元する。秘密マッチング装置10γは秘密マッチング装置10αから受信したaαβと秘密マッチング装置10βから受信したaαβとが一致していれば、aαβ+aβγ+aγαを計算して数値Aを復元する。
【0084】
C=A+Bの秘密計算
(1)秘密マッチング装置10αは(cγα,cαβ)=(aγα+bγα,aαβ+bαβ)を計算して記録し、秘密マッチング装置10βは(cαβ,cβγ)=(aαβ+bαβ,aβγ+bβγ)を計算して記録し、秘密マッチング装置10γは(cβγ,cγα)=(aβγ+bβγ,aγα+bγα)を計算して記録する。
【0085】
C=A−Bの秘密計算
(1)秘密マッチング装置10αは(cγα,cαβ)=(aγα−bγα,aαβ−bαβ)を計算して記録し、秘密マッチング装置10βは(cαβ,cβγ)=(aαβ−bαβ,aβγ−bβγ)を計算して記録し、秘密マッチング装置10γは(cβγ,cγα)=(aβγ−bβγ,aγα−bγα)を計算して記録する。
【0086】
C=A+Sの秘密計算(ただし、Sは既知の定数)
(1)秘密マッチング装置10αは(cγα,cαβ)=(aγα+S,aαβ)を計算して記録し、秘密マッチング装置10γは(cβγ,cγα)=(aβγ,aγα+S)を計算して記録する。秘密マッチング装置10βの処理はない。
【0087】
C=ASの秘密計算(ただし、Sは既知の定数)
(1)秘密マッチング装置10αは(cγα,cαβ)=(aγαS,aαβS)を計算して記録し、秘密マッチング装置10βは(cαβ,cβγ)=(aαβS,aβγS)を計算して記録し、秘密マッチング装置10γは(cβγ,cγα)=(aβγS,aγαS)を計算して記録する。
【0088】
C=ABの秘密計算
(1)秘密マッチング装置10αは、乱数r,r,cγαを生成し、cαβ=(aγα+aαβ)(bγα+bαβ)−r−r−cγαを計算する。そして、秘密マッチング装置10αは、秘密マッチング装置10βに(r,cαβ)を、秘密マッチング装置10γに(r,cγα)を送信する。
(2)秘密マッチング装置10βは、y=aαββγ+aβγαβ+rを計算し、秘密マッチング装置10γに送信する。
(3)秘密マッチング装置10γは、z=aβγγα+aγαβγ+rを計算し、秘密マッチング装置10αに送信する。
(4)秘密マッチング装置10βと秘密マッチング装置10γは、それぞれcβγ=y+z+aβγβγを計算する。
(5)秘密マッチング装置10αは(cγα,cαβ)を記録し、秘密マッチング装置10βは(cαβ,cβγ)を記録し、秘密マッチング装置10γは(cβγ,cγα)を記録する。
【0089】
ビットAの否定(C=1−A)の秘密計算
秘密マッチング装置10α
(cγα,cαβ)=(1−aγα,−aαβ mod W)
を計算して記録し、秘密マッチング装置10β
(cαβ,cβγ)=(−aαβ mod W,−aβγ mod W)
を計算して記録し、秘密マッチング装置10γ
(cβγ,cγα)=(−aβγ mod W,1−aγα
を計算して記録する。
【0090】
ビットの論理積(C=A∧B=AB)の秘密計算
秘密マッチング装置10α,10β,10γは、整数の乗算(C=AB mod W)の秘密計算と同じ処理を行う。
【0091】
ビットの論理和(C=A∨B=A+B−AB)の秘密計算
(1)秘密マッチング装置10α,10β,10γは、整数の加算(C=A+B mod W)の秘密計算と同じ処理を行い、C’=A+Bの結果として、秘密マッチング装置10αが断片(cγα’,cαβ’)を、秘密マッチング装置10βが断片(cαβ’,cβγ’)を、秘密マッチング装置10γが断片(cβγ’,cγα’)を記録する。また、秘密マッチング装置10α,10β,10γは、整数の乗算(C=AB mod W)の秘密計算と同じ処理を行い、C”=ABの結果として、秘密マッチング装置10αが断片(cγα”,cαβ”)を、秘密マッチング装置10βが断片(cαβ”,cβγ”)を、秘密マッチング装置10γが断片(cβγ”,cγα”)を記録する。
(2)秘密マッチング装置10α,10β,10γは、S=−1として整数の乗算(C=AS mod W)の秘密計算(ただし、Sは既知の定数)と同じ処理を行い、C’’’=−C”の結果として、秘密マッチング装置10αが断片(cγα’’’,cαβ’’’)を、秘密マッチング装置10βが断片(cαβ’’’,cβγ’’’)を、秘密マッチング装置10γが断片(cβγ’’’,cγα’’’)を記録する。
(3)秘密マッチング装置10α,10β,10γは、整数の加算(C=A+B mod W)の秘密計算と同じ処理を行い、C=C’+C’’’の結果として、秘密マッチング装置10αが断片(cγα,cαβ)を、秘密マッチング装置10βが断片(cαβ,cβγ)を、秘密マッチング装置10γが断片(cβγ,cγα)を記録する。
【0092】
ビットの排他的論理和(C=A[∨]B=A+B−2AB)の秘密計算
(1)秘密マッチング装置10α,10β,10γは、整数の加算(C=A+B mod W)の秘密計算と同じ処理を行い、C’=A+Bの結果として、秘密マッチング装置10αが断片(cγα’,cαβ’)を、秘密マッチング装置10βが断片(cαβ’,cβγ’)を、秘密マッチング装置10γが断片(cβγ’,cγα’)を記録する。また、秘密マッチング装置10α,10β,10γは、整数の乗算(C=AB mod W)の秘密計算と同じ処理を行い、C”=ABの結果として、秘密マッチング装置10αが断片(cγα”,cαβ”)を、秘密マッチング装置10βが断片(cαβ”,cβγ”)を、秘密マッチング装置10γが断片(cβγ”,cγα”)を記録する。
(2)秘密マッチング装置10α,10β,10γは、S=−2として整数の乗算(C=AS mod W)の秘密計算(ただし、Sは既知の定数)の秘密計算と同じ処理を行い、C’’’=−2C”の結果として、秘密マッチング装置10αが断片(cγα’’’,cαβ’’’)を、秘密マッチング装置10βが断片(cαβ’’’,cβγ’’’)を、秘密マッチング装置10γが断片(cβγ’’’,cγα’’’)を記録する。
(3)秘密マッチング装置10α,10β,10γは、整数の加算(C=A+B mod W)の秘密計算と同じ処理を行い、C=C’+C’’’の結果として、秘密マッチング装置10αが断片(cγα,cαβ)を、秘密マッチング装置10βが断片(cαβ,cβγ)を、秘密マッチング装置10γが断片(cβγ,cγα)を記録する。
【0093】
ビットA(n),n=0,…,N−1の整数変換の秘密計算
ビットA(n)の整数変換とは、
【0094】
【数1】

【0095】
を求めることである。また、秘密マッチング装置10α,10β,10γが分散して記録するビットA(n)の断片を(a(n)γα,a(n)αβ)、(a(n)αβ,a(n)βγ)、(a(n)βγ,a(n)γα)とする。秘密マッチング装置10αは、
【0096】
【数2】

【0097】
を計算して記録し、秘密マッチング装置10β
【0098】
【数3】

【0099】
を計算して記録し、秘密マッチング装置10γ
【0100】
【数4】

【0101】
を計算して記録する。
【0102】
Nビットの整数Aの二進数変換の秘密計算
x(n)は、xの下位n+1番目のビットを示すものとする。
(1)n=0からN−1について、秘密マッチング装置10βが(aαβ+aβγ mod W)(n)を秘密分散し、秘密マッチング装置10α,10β,10γが(aαβ+aβγ mod W)(n)の断片(b(n)γα,b(n)αβ)、(b(n)αβ,b(n)βγ)、(b(n)βγ,b(n)γα)を分散して記録する。n=0からN−1について、秘密マッチング装置10γが(aγα)(n)を秘密分散し、秘密マッチング装置10α,10β,10γが(aγα)(n)の断片((aγα)(n)γα,(aγα)(n)αβ)、((aγα)(n)αβ,(aγα)(n)βγ)、((aγα)(n)βγ,(aγα)(n)γα)を分散して記録する。
(2)cγα=0とし、n=0からN−1について(2−1)から(2−3)の処理を繰返し実行する。
(2−1)d=b(n)+(aγα)(n)−2b(n)(aγα)(n)
の秘密計算を実行し、dの断片を分散して記録する。
(2−2)a(n)=d+c−2d
の秘密計算を実行し、a(n)の断片を分散して記録する。
(2−3)n<N−1であれば、
n+1=b(n)(aγα)(n)+d−b(n)(aγα)(n)d
の秘密計算を実行し、cn+1の断片を分散して記録する。
【0103】
[プログラム、記録媒体]
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0104】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【0105】
10,…,10,20,…,20,30,…,30 秘密マッチング装置
100,…,100 秘密分散装置 105 選択手段
110,…,110 断片置換部 120,…,120 再分散部
130,…,130 初期情報分散部 140,…,140 初期乗算部
150,…,150 確認分散部 160,…,160 確認乗算部
170,…,170 改ざん検出部 190,…,190 記録部
300,…,300,400,…,400,500,…,500 マッチング制御部
310 対応用ベクトル生成手段 310,…,310 対応用ベクトル生成部
320 対応用ランダム置換手段 320,…,320 対応用ランダム置換部
330 対応用ベクトル復号手段 330,…,330 対応用ベクトル復号部
340 対応用並び替え手段 340,…,340 対応用並び替え部
405,505 表分割手段
405,…,405,505,…,505 表分割部
450 ベクトル結合手段 450,…,450 ベクトル結合部
460 表結合手段 460,…,460 表結合部
470 表ランダム置換手段 470,…,470 表ランダム置換部
480 ソート用ベクトル復号手段
480,…,480 ソート用ベクトル復号部
490 ソート手段 490,…,490 ソート部
520 処理用ランダム置換手段 520,…,520 処理用ランダム置換部
530 処理用ベクトル復号手段 530,…,530 処理用ベクトル復号部
540 処理用並び替え手段 540,…,540 処理用並び替え部
550 処理用ベクトル対応手段 550,…,550 処理用ベクトル対応部
560 処理手段 560,…,560 処理部
570 処理用繰返手段 570,…,570 処理用繰返部
1000 ネットワーク


【特許請求の範囲】
【請求項1】
3個以上の秘密マッチング装置で構成され、それぞれM個のレコードからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する秘密マッチングシステムであって、
Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[h]に対応するベクトル、[XjS]は前記所定の処理後の表[X]に対応する表とし、
M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求め、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける対応用ベクトル生成手段と、
j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める対応用ランダム置換手段と、
ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求める対応用ベクトル復号手段と、
すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替える対応用並び替え手段と、
を備える秘密マッチングシステム。
【請求項2】
請求項1記載の秘密マッチングシステムであって、
J=2であり、前記所定の処理は、M個のレコードを持つ表[X]の各レコードの一部または全部の要素を用いたソートを含み、表[X]に対しては何も行わないものであり、
さらに、
表[X]を、前記の表[X]と前記の表[X]に、表[X]が少なくとも前記所定の処理に用いる要素を含むように分割する表分割手段と、
異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、前記所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコード対応が維持されるように対応付けするベクトル結合手段と、
前記対応用並び替え手段の処理後の表[X1R],[X2R]を結合して表[X]とする表結合手段と、
表[X]のレコード間を秘密計算でランダム置換し、表[XRR]を求める表ランダム置換手段と、
前記表[X1S]に対応付けされた前記ベクトル[c]の表ランダム置換手段の処理後のベクトル[cRR]を復号し、ベクトルcRRを求めるソート用ベクトル復号手段と、
ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動するソート手段と、
を備える秘密マッチングシステム。
【請求項3】
請求項1記載の秘密マッチングシステムであって、
前記所定の処理はB個の処理F,…,Fからなり、処理FはM個のレコードを持つ表[X],…,[X]の一部または全部を用いる処理Fごとに定められた処理、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b(1),…,b(D)は1以上D以下の異なる整数、D’は1以上の整数とし、
さらに、
表[X]をJ個に分割して前記の表[X],…,[X]を求める表分割手段と、
処理Fに必要な要素を有する表[Xb(1)],…,[Xb(D)]を選び、b(d)=b(1),…,b(D)について、表[Xb(d)]とベクトル[hb(d)]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[Xb(d)R]とベクトル[hb(d)R]とを求める処理用ランダム置換手段と、
ベクトル[hb(1)R],…,[hb(D)R]を復号し、ベクトルhb(1)R,…,hb(D)Rを求める処理用ベクトル復号手段と、
すべてのb(i)とb(d)の組合せ(ただし、ここでのiは1,…,Dのいずれか)に対してhb(i)R=hb(d)Rとなるように表[Xb(d)R]のレコードを並び替え、表[Xb(1)T],…,[Xb(D)T]を得る処理用並び替え手段と、
ベクトルhb(i)Rの各要素を秘密分散したベクトル[hb(i)R]の各要素を表[Xb(1)T],…,[Xb(D)T]の各レコードに、処理Fを施しても対応が維持されるように対応付ける処理用ベクトル対応手段と、
ベクトル[hb(i)R]が対応付けられた表[Xb(1)T],…,[Xb(D)T]に対して処理Fを行って、処理F後のベクトル[hb(i)F]が対応付けられた処理F後の表[Xb(1)F],…,[Xb(D’)F]を求め、処理F前のJ個の表の中から0個以上、処理F後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理F後のベクトル[hjbS]と表[X1bS],…,[XJbS]を求める処理手段と、
b=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],…,[XJbS]を表[X1S],…,[XJS]とし、Noの場合はベクトル[hjbS]をベクトル[h]、表[X1bS],…,[XJbS]を表[X],…,[X]とし、b=1からBについて、前記処理用ランダム置換手段、前記処理用ベクトル復号手段、前記処理用並び替え手段、前記処理用ベクトル対応手段、前記処理手段の処理を繰り返す処理用繰返手段と、
を備える秘密マッチングシステム。
【請求項4】
M個のレコードからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する3個以上の秘密マッチング装置で構成される秘密マッチングシステムの中の秘密マッチング装置であって、
Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[h]に対応するベクトル、[XjS]は前記所定の処理後の表[X]に対応する表とし、
M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求め、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付けるための対応用ベクトル生成部と、
j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求めるための対応用ランダム置換部と、
ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求めるための対応用ベクトル復号部と、
すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替えるための対応用並び替え部と、
を備える秘密マッチング装置。
【請求項5】
3個以上の秘密マッチング装置を用いて、それぞれM個のレコードからなりレコード同士が対応付けられているJ個の表[X],…,[X]に対して所定の処理が施された後の表[X1S],…,[XJS]から、対応付けられているレコードが同じ順番となるように表X1S,…,XJSのレコードを並び替えた表に対応する秘密分散された表を計算する秘密マッチング方法であって、
Mは2以上の整数、Jは2以上の整数、iとjは1以上J以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、前記所定の処理は少なくとも1個以上の表に対するレコードの並び替えのための処理を含むもの、[hjS]は前記所定の処理後のベクトル[h]に対応するベクトル、[XjS]は前記所定の処理後の表[X]に対応する表とし、
M個の異なる値を要素に持つベクトルhを生成し、ベクトルhの各要素を秘密分散してベクトル[h]を求め、ベクトル[h]をランダム置換してベクトル[h]を求め、j=1〜Jについて、ベクトル[h]と同一のベクトル[h]の各要素を表[X]の各レコードに、前記所定の処理を施しても対応が維持されるように対応付ける対応用ベクトル生成ステップと、
j=1〜Jについて、表[XjS]とベクトル[hjS]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[XjR]とベクトル[hjR]とを求める対応用ランダム置換ステップと、
ベクトル[h1R],…,[hJR]を復号し、ベクトルh1R,…,hJRを求める対応用ベクトル復号ステップと、
すべてのjとiの組合せに対してhjR=hiRとなるように表[XjR]のレコードを並び替える対応用並び替えステップと、
を有する秘密マッチング方法。
【請求項6】
請求項5記載の秘密マッチング方法であって、
J=2であり、前記所定の処理は、M個のレコードを持つ表[X]の各レコードの一部または全部の要素を用いたソートを含み、表[X]に対しては何も行わないものであり、
表[X]を、前記の表[X]と前記の表[X]に、表[X]が少なくとも前記所定の処理に用いる要素を含むように分割する表分割ステップと、
異なる値を持つM個の要素からなるベクトルcを作成し、各要素を秘密分散してベクトル[c]を求め、前記の表[X]に対する前記所定の処理の後に、ベクトル[c]の各要素を表[X1S]の各レコードに対応が維持されるように対応付けするベクトル結合ステップと、
前記対応用並び替えステップ後の表[X1R],[X2R]を結合して表[X]とする表結合ステップと、
表[X]のレコード間を秘密計算でランダム置換し、表[XRR]を求める表ランダム置換ステップと、
前記表[X1S]に対応付けされた前記ベクトル[c]の表ランダム置換手段の処理後のベクトル[cRR]を復号し、ベクトルcRRを求めるソート用ベクトル復号ステップと、
ベクトルcRRの各要素がベクトルcの各要素と一致するように、表[XRR]の各レコードを移動するソートステップと、
を有する秘密マッチング方法。
【請求項7】
請求項5記載の秘密マッチング方法であって、
前記所定の処理はB個の処理F,…,Fからなり、処理FはM個のレコードを持つ表[X],…,[X]の一部または全部を用いる処理Fごとに定められた処理、Bは1以上の整数、bは1以上B以下の整数、Dは1以上J以下の整数、dは1以上D以下の整数、b(1),…,b(D)は1以上D以下の異なる整数、D’は1以上の整数とし、
表[X]をJ個に分割して前記の表[X],…,[X]を求める表分割ステップと、
処理Fに必要な要素を有する表[Xb(1)],…,[Xb(D)]を選び、b(d)=b(1),…,b(D)について、表[Xb(d)]とベクトル[hb(d)]との対応を維持したまま秘密計算でレコード間をランダム置換し、ランダム置換された表[Xb(d)R]とベクトル[hb(d)R]とを求める処理用ランダム置換ステップと、
ベクトル[hb(1)R],…,[hb(D)R]を復号し、ベクトルhb(1)R,…,hb(D)Rを求める処理用ベクトル復号ステップと、
すべてのb(i)とb(d)の組合せ(ただし、ここでのiは1,…,Dのいずれか)に対してhb(i)R=hb(d)Rとなるように表[Xb(d)R]のレコードを並び替え、表[Xb(1)T],…,[Xb(D)T]を得る処理用並び替えステップと、
ベクトルhb(i)Rの各要素を秘密分散したベクトル[hb(i)R]の各要素を表[Xb(1)T],…,[Xb(D)T]の各レコードに、処理Fを施しても対応が維持されるように対応付ける処理用ベクトル対応ステップと、
ベクトル[hb(i)R]が対応付けられた表[Xb(1)T],…,[Xb(D)T]に対して処理Fを行って、処理F後のベクトル[hb(i)F]が対応付けられた処理F後の表[Xb(1)F],…,[Xb(D’)F]を求め、処理F前のJ個の表の中から0個以上、処理F後のD’個の表の中から1個以上となるように、あらかじめ定めたJ’個のベクトルと表を抽出し、J’を新しいJに更新し、処理F後のベクトル[hjbS]と表[X1bS],…,[XJbS]を求める処理ステップと、
を有し
b=Bかを確認し、Yesの場合はベクトル[hjbS]をベクトル[hjS]、表[X1bS],…,[XJbS]を表[X1S],…,[XJS]とし、Noの場合はベクトル[hjbS]をベクトル[h]、表[X1bS],…,[XJbS]を表[X],…,[X]とし、b=1からBについて、前記処理用ランダム置換ステップ、前記処理用ベクトル復号ステップ、前記処理用並び替えステップ、前記処理用ベクトル対応ステップ、前記処理ステップの処理を繰り返す秘密マッチング方法。
【請求項8】
請求項1から3のいずれかに記載の秘密マッチングシステムの各秘密マッチング装置としてコンピュータを機能させるための秘密マッチングプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate