(57)【特許請求の範囲】
【請求項１】
Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置に対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であり、
ｎ＝１，２，…，Ｎとして、Ｓｎについての複数の条件から重複する条件を除いたＳｎについての重複除去後条件を求める重複除去後条件生成部と、
ｎ＝１，２，…，Ｎとして、Ｓｎについての各重複除去後条件を満たすレコードを抽出するレコード抽出部と、各上記抽出されたレコードの識別子を上記関数ｆｎに入力した場合の出力値を計算し、また 他の計算装置により計算された出力値を上記関数ｆｎに入力した場合の出力値を計算する関数値計算部と、を含む第ｎ計算装置と、
全ての上記関数ｆ１，ｆ２，…，ｆＮの演算が施された演算結果である照合タグを上記第１，２，…，Ｎ計算装置から受け取り、各上記組を構成する条件と同じ重複除去後条件を満たすレコードに対する照合タグを参照することにより、その各組を構成する全ての条件に共通する照合タグの数又はその各組を構成する全ての条件に対する照合タグのユニーク数をカウントするカウント部と、
を含むマッチングシステム。
【請求項２】
請求項１に記載のマッチングシステムにおいて、
上記第１，２，…，Ｎ計算装置の少なくとも１つは、各重複除去後条件に対応する出力値が複数ある場合には、これらの出力値を並び替えて他の計算装置に送信する並替部を更に含む、
マッチングシステム。
【請求項３】
請求項１又は２に記載のマッチングシステムにおいて、
上記関数値計算部は、各上記抽出されたレコードの識別子のハッシュ値を上記関数ｆｎに入力した場合の出力値を計算する、
マッチングシステム。
【請求項４】
Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置に対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であり、
ｎ＝１，２，…，Ｎとして、Ｓｎについての複数の条件から重複する条件を除いたものをＳｎについての重複除去後条件として、Ｓｎについての各重複除去後条件を満たすレコードを抽出するレコード抽出部と、各上記抽出されたレコードの識別子を上記関数ｆｎに入力した場合の出力値を計算し、また他の計算装置により計算された出力値を上記関数ｆｎに入力した場合の出力値を計算する関数値計算部と、を含むマッチングシステムの計算装置。
【請求項５】
請求項４に記載の計算装置において、
ｎ＝１，２，…，Ｎとして、Ｓｎについての重複除去後条件を生成する重複除去後条件生成部を更に含む、
計算装置。
【請求項６】
請求項４又は５に記載の計算装置において、
上記計算装置は、各重複除去後条件に対応する出力値が複数ある場合には、これらの出力値を並び替えて他の計算装置に送信する並替部を更に含む、
計算装置。
【請求項７】
Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置に対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であり、
ｎ＝１，２，…，Ｎとして、Ｓｎについての複数の条件から重複する条件を除いたＳｎについての重複除去後条件を求める重複除去後条件生成部と、
全ての関数ｆ１，ｆ２，…，ｆＮの演算が施された演算結果である最終出力値を受け取り、各上記組を構成する条件と同じ重複除去後条件を満たすレコードに対する最終出力値を参照することにより、その各組を構成する全ての条件に共通する最終出力値の数又はその各組を構成する全ての条件に対する最終出力値のユニーク数をカウントするカウント部と、
を含むマッチングシステムのクライアント装置。
【請求項８】
Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置に対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であり、
クライアント装置の重複除去後条件生成部が、ｎ＝１，２，…，Ｎとして、Ｓｎについての複数の条件から重複する条件を除いたＳｎについての重複除去後条件を求める重複除去後条件生成ステップと、
ｎ＝１，２，…，Ｎとして、上記クライアント装置とは異なる第ｎ計算装置が、Ｓｎについての各重複除去後条件を満たすレコードを抽出するレコード抽出ステップと、各上記抽出されたレコードの識別子を上記関数ｆｎに入力した場合の出力値を計算し、また他の計算装置により計算された出力値を上記関数ｆｎに入力した場合の出力値を計算する関数値計算ステップとを行う第ｎ計算ステップと、
上記クライアント装置のカウント部が、上記第ｎ計算ステップで生成された全ての上記関数ｆ１，ｆ２，…，ｆＮの演算が施された演算結果である照合タグを上記第１，２，…，Ｎ計算装置から受け取り、各上記組を構成する条件と同じ重複除去後条件を満たすレコードに対する照合タグを参照することにより、その各組を構成する全ての条件に共通する照合タグの数又はその各組を構成する全ての条件に対する照合タグのユニーク数をカウントするカウントステップと、
を含むマッチング方法。
【請求項９】
請求項４から６の何れかに記載の計算装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項７のクライアント装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号技術、特に複数のデータ集合について非開示のまま集計を行う技術に関する。
【背景技術】
【０００２】
非特許文献１に、複数のデータ集合について非開示のまま集計を行う技術が記載されている。以下、非特許文献１に記載された技術を簡単に説明する。
【０００３】
２個の計算装置Ｐ１，Ｐ２がそれぞれデータ集合Ｓ１及びＳ２を保持している。データ集合Ｓ１に対する条件をＣ１、データ集合Ｓ２に対する条件をＣ２とする。データ集合Ｓ１を構成するレコードの中で条件Ｃ１を満たすものの集合をＴ１とし、データ集合Ｓ２を構成するレコードの中で条件Ｃ２を満たすものの集合をＴ２とする。非特許文献１は、集合Ｔ１を計算装置Ｐ２を含む外部に非開示にし、集合Ｔ２を計算装置Ｔ１を含む外部に非開示して、条件Ｃ１及び条件Ｃ２の組を満たす要素の数、すなわちＴ１かつＴ２の集合の要素数｜Ｔ１∩Ｔ２｜を求める問題を扱っている。
【０００４】
関数ｆＫ１及びｆＫ２を衝突困難かつ可換な鍵付き一方向性ハッシュ関数とする。すなわち、任意の入力ｘ，ｙ及び任意の鍵Ｋ１，Ｋ２に対して無視できる確率を除き、ｘ＝ｙ⇔ｆＫ１（ｆＫ２（ｘ））＝ｆＫ２（ｆＫ１（ｙ））が成り立ち、ｆＫ１（ｘ）からＫ１及びｘを求めることは困難であり、またｆＫ２（ｙ）からＫ２及びｙを求めることは困難であるとする。
【０００５】
第１計算装置Ｐ１は、全てのｔｉ∈Ｔ１についてｆＫ１（ｔｉ）を計算して辞書順で第２計算装置Ｐ２に送信する。また、第１計算装置Ｐ１は、全てのｔ’ｊ∈Ｔ２についてｆＫ２（ｔ’ｊ）を計算して辞書順で第１計算装置Ｐ１に送信する。
【０００６】
第１計算装置Ｐ１は、第２計算装置Ｐ２から受信したｆＫ２（ｔ’ｊ）を用いてｆＫ１（ｆＫ２（ｔ’ｊ））を計算して、辞書順でクライアント装置に送信する。第２計算装置Ｐ２は、第１計算装置Ｐ１から受信したｆＫ１（ｔｉ）を用いてｆＫ２（ｆＫ１（ｔｉ））を計算して、辞書順でクライアント装置に送信する。
【０００７】
ここで、ｆＫ１（ｆＫ２（ｔ’ｊ））及びｆＫ２（ｆＫ１（ｔｉ））を「照合タグ」と呼ぶことにする。より詳細には、ｆＫ１（ｆＫ２（ｔ’ｊ））を条件Ｃ２に対応する照合タグ、ｆＫ２（ｆＫ１（ｔｉ））を条件Ｃ１に対応する照合タグと呼ぶことにする。
【０００８】
クライアント装置は、第１計算装置Ｐ１から受信した照合タグｆＫ１（ｆＫ２（ｔ’ｊ））と第２計算装置Ｐ２から受信した照合タグｆＫ２（ｆＫ１（ｔｉ））とで同じ値を持つものの数、すなわちｆＫ１（ｆＫ２（ｔ’ｊ））＝ｆＫ２（ｆＫ１（ｔｉ））となる（ｉ，ｊ）の組の数を計算する。この（ｉ，ｊ）の組の数が、無視できる確率を除いて｜Ｔ１∩Ｔ２｜となる。
【０００９】
このように、第１計算装置Ｐ１はｔｉを関数ｆＫ１で暗号化した後にこれらの暗号化を外部に送信し、第２計算装置Ｐ２はｔ’ｊを関数ｆＫ２で暗号化した後にこれらの暗号化を外部に送信する。このため、ｔｉ及びｔ’ｊを外部に秘匿にすることができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】R.Agrawal, A.V.Evfimievski, and R.Srikant, “Information Sharing Across Private Databases”, ACM SIGMOD 2003, pp.86-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１に記載された技術では、条件の組が複数あり、あるデータ集合に対する条件が重複している場合においても、計算装置Ｐ１，Ｐ２はその重複する照合タグを生成してクライアント装置に送信していた。このため、照合タグを重複して生成して送信する点において効率が良くないという問題があった。
【００１２】
例えば、第一の条件の組がＣ１∧Ｃ２であり、第二の条件の組がＣ１∧Ｃ３であるとする。条件Ｃ３は、データ集合Ｓ２に対する条件である。この例では、条件Ｃ１が、第一の条件の組及び第二の条件の組において重複している。このとき、計算装置Ｐ１，Ｐ２は、まず第一の条件の組を満たす要素の数を求めるためにＣ１に対応する照合タグ及びＣ２に対応する照合タグを生成しクライアント装置に送信する。次に、計算装置Ｐ１，Ｐ２は、第二の条件の組を満たす要素の数を求めるためにＣ１に対応する照合タグ及びＣ３に対応する照合タグを生成しクライアント装置に送信していた。このように、条件Ｃ１についての照合タグを重複して生成して送信する点において効率が良くないという問題があった。
【００１３】
この発明は、従来よりも効率が良いマッチングシステム、方法、計算装置、クライアント装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
この発明のマッチングシステムは、Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置に対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であり、ｎ＝１，２，…，Ｎとして、Ｓｎについての複数の条件から重複する条件を除いたＳｎについての重複除去後条件を求める。ｎ＝１，２，…，Ｎとして、Ｓｎについての各重複除去後条件を満たすレコードを抽出する。各上記抽出されたレコードの識別子を上記関数ｆｎに入力した場合の出力値を計算し、また他の計算装置により計算された出力値を上記関数ｆｎに入力した場合の出力値を計算する。全ての上記関数ｆ１，ｆ２，…，ｆＮの演算が施された演算結果である照合タグを受け取り、各上記組を構成する条件と同じ重複除去後条件を満たすレコードに対する照合タグを参照することにより、その各組を構成する全ての条件に共通する照合タグの数又はその各組を構成する全ての条件に対する照合タグのユニーク数をカウントする。
【発明の効果】
【００１５】
重複する条件についての照合タグの生成及び送信を一回しか行わないことにより、従来よりも効率良くマッチングを行うことができる。
【図面の簡単な説明】
【００１６】
【図１】マッチングシステムの構成を説明するためのブロック図。
【図２】第ｎ計算装置の構成を説明するためのブロック図。
【図３】データ集合Ｓｎを説明するためのフローチャート。
【図４】Ｎ＝２の具体例を説明するための図。
【図５】Ｎ＝２の具体例を説明するための図。
【図６】データ集合Ｓｎを説明するためのフローチャート。
【発明を実施するための形態】
【００１７】
以下、図面を参照してこの発明の一実施形態を説明する。
マッチングシステムは、図１に示すように、クライアント装置Ｃ、第１計算装置Ｐ１，第２計算装置Ｐ２，…，第Ｎ計算装置ＰＮを例えば含む。クライアント装置Ｃは、重複除去後条件生成部１及びカウント部２を例えば含む。ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎは、図２に示すように、記憶部Ｐｎ１，レコード抽出部Ｐｎ２，関数値計算部Ｐｎ３を例えば含む。
【００１８】
Ｎは２以上の整数であり、ｎ＝１，２，…，Ｎとして、Ｓｎは第ｎ計算装置Ｐｎに対応するデータ集合であり、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数あり、関数ｆ１，ｆ２，…，ｆＮは衝突困難な一方向性関数であり互いに可換であるとする。
【００１９】
ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎは、データ集合Ｓｎを管理する。データ集合Ｓｎは、例えば第ｎ計算装置Ｐｎの記憶部Ｐｎ１に記憶されている。データ集合Ｓｎは、図３に例示するように、複数のレコードｔ＿（ｎ，１），ｔ＿（ｎ，２），…，ｔ＿（ｎ，３），…，ｔ＿（ｎ，ＮＮ）から構成される。ＮＮは、データ集合Ｓｎを構成するレコードの総数である。
【００２０】
レコードｔ＿（ｎ，Ｎｎ）は、そのレコードを示す識別子ｉｄ＿｛ｎ，Ｎｎ｝と、少なくとも１つの属性値ａ＿｛ｎ，Ｎｎ，１｝，ａ＿｛ｎ，Ｎｎ，２｝，…，ａ＿｛ｎ，Ｎｎ，ｋ｝，…，ａ＿｛ｎ，Ｎｎ，ｋｎ｝とから構成される。ｋｎは、レコードを構成する属性値の総数である。識別子ｉｄ＿｛ｎ，Ｎｎ｝は、“12345678”や“ABCDEFG”等の、対象を一意に表す数値や文字列である。対象とは、例えば人間である。同一の対象には、異なる複数のデータ集合において同じ識別子が割り振られているものとする。属性値ａ＿｛ｎ，Ｎｎ，ｋ｝は、属性Ａ＿｛ｎ，ｋ｝の値である。例えば、属性Ａ＿｛１，１｝が性別を表す属性である場合には、Ａ＿｛１，１｝＝｛“男性”，“女性”｝となり、Ａ＿｛１，１｝の属性値ａ＿｛１，Ｎｎ，１｝は“男性”と“女性”の何れかとなる。また、属性Ａ＿｛１，１｝が性別を表す属性であり、属性Ａ＿｛１，２｝が年齢を表す属性であり、Ａ＿｛１，３｝が既婚か未婚かを表す属性である場合には、例えばレコードｔ＿（１，Ｎｎ）＝（ｉｄ＿｛１，Ｎｎ｝，ａ＿｛１，Ｎｎ，１｝，ａ＿｛１，Ｎｎ，２｝，ａ＿｛１，Ｎｎ，３｝）＝（“12345678”，“男性”，“35歳”，“既婚”）となる。
【００２１】
重複除去後条件生成部１には、Ｓ１，Ｓ２，…，ＳＮについての条件から構成される条件の組が複数入力される。ｎ＝１，２，…，Ｎとして、重複除去後条件生成部１は、Ｓｎについての複数の条件から重複する条件を除いたＳｎについての重複除去後条件を求める（ステップＳ１）。ｎ＝１，２，…，Ｎとして、Ｓｎについての重複除去後条件は、第ｎ計算装置Ｐｎに送信される。
【００２２】
Ｎ＝２であり、第１計算装置Ｐ１及び第２計算装置Ｐ２でクロス集計を行う場合を例に挙げて説明をする。例えば、図４に示すように、第一の条件の組がＣ１∧Ｃ２であり、第二の条件の組がＣ１∧Ｃ３であり、第三の条件の組がＣ４∧Ｃ３であり、第四の条件の組がＣ５∧Ｃ６であるとする。この場合、Ｓ１についての条件はＣ１，Ｃ１，Ｃ４，Ｃ５の４個であり、Ｃ１の部分で重複している。したがって、重複除去後条件生成部１は、重複する条件Ｃ１を１つ除いて、条件Ｃ１，Ｃ４，Ｃ５を重複除去後条件として出力する。ＳＮｎについてのＬＮｎ個の重複除去後条件をｄ＿｛Ｎｎ，１｝，ｄ＿｛Ｎｎ，２｝，…，ｄ＿｛Ｎｎ，ＬＮｎ｝と表記すると、図４に示すように、重複除去後条件ｄ＿｛１，１｝＝Ｃ１であり、重複除去後条件ｄ＿｛１，２｝＝Ｃ４であり、重複除去後条件ｄ＿｛１，３｝＝Ｃ５である。
【００２３】
また、Ｓ２についての条件はＣ２，Ｃ３，Ｃ３，Ｃ６の４個であり、Ｃ３の部分で重複している。したがって、重複除去後条件生成部１は、重複する条件Ｃ３を１つ除いて、条件Ｃ２，Ｃ３，Ｃ６を重複除去後条件として出力する。すなわち、重複除去後条件ｄ＿｛２，１｝＝Ｃ２であり、重複除去後条件ｄ＿｛２，２｝＝Ｃ３であり、重複除去後条件ｄ＿｛２，３｝＝Ｃ６である。
【００２４】
ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎのレコード抽出部Ｐｎ２は、記憶部Ｐｎ１を参照して、Ｓｎについての各重複除去後条件を満たすレコードを抽出する（ステップＳ２）。抽出されたレコードは、関数値計算部Ｐｎ３に送られる。
【００２５】
上記の具体例だと、図４に示すように、第１計算装置Ｐ１は、Ｓ１を構成するレコードの中で、３つの重複除去後条件ｄ＿｛１，１｝，ｄ＿｛１，２｝，ｄ＿｛１，３｝のそれぞれを満たすレコードを抽出する。例えば、重複除去後条件ｄ＿｛１，１｝＝Ｃ１を満たすレコードの識別子がｉｄ＿｛１，１｝，ｉｄ＿｛１，５｝であり、重複除去後条件ｄ＿｛１，２｝＝Ｃ４を満たすレコードの識別子がｉｄ＿｛１，２｝，ｉｄ＿｛１，６｝，ｉｄ＿｛１，７｝であり、重複除去後条件ｄ＿｛１，３｝＝Ｃ５を満たすレコードの識別子がｉｄ＿｛１，３｝，ｉｄ＿｛１，４｝であるとする。重複除去後条件ｄ＿｛Ｎｎ，Ｌ｝を満たすレコードの識別子から構成されるグループをＧ＿｛Ｎｎ，Ｌ｝と表記すると、Ｇ＿｛１，１｝＝（ｉｄ＿｛１，１｝，ｉｄ＿｛１，５｝）であり、Ｇ＿｛１，２｝＝（ｉｄ＿｛１，２｝，ｉｄ＿｛１，６｝，ｉｄ＿｛１，７｝）であり、Ｇ＿｛１，３｝＝（ｉｄ＿｛１，３｝，ｉｄ＿｛１，４｝）である。
【００２６】
また、第２計算装置Ｐ２は、３つの重複除去後条件ｄ＿｛２，１｝，ｄ＿｛２，２｝，ｄ＿｛２，３｝のそれぞれを満たすレコードを抽出する。例えば、重複除去後条件ｄ＿｛２，１｝＝Ｃ２を満たすレコードの識別子がｉｄ＿｛２，２｝，ｉｄ＿｛２，５｝，ｉｄ＿｛２，６｝であり、重複除去後条件ｄ＿｛２，２｝＝Ｃ３を満たすレコードの識別子がｉｄ＿｛２，１｝，ｉｄ＿｛２，７｝であり、重複除去後条件ｄ＿｛２，３｝＝Ｃ６を満たすレコードの識別子がｉｄ＿｛２，３｝，ｉｄ＿｛２，４｝であるとする。すなわち、Ｇ＿｛２，１｝＝（ｉｄ＿｛２，２｝，ｉｄ＿｛２，５｝，ｉｄ＿｛２，６｝）であり、Ｇ＿｛２，２｝＝（ｉｄ＿｛２，１｝，ｉｄ＿｛２，７｝）であり、Ｇ＿｛２，３｝＝（ｉｄ＿｛２，３｝，ｉｄ＿｛２，４｝）であるとする。
【００２７】
ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎの関数値計算部Ｐｎ３は、まず各抽出されたレコードの識別子を関数ｆｎに入力した場合の出力値を計算する（ステップＳ３）。計算された出力値は、第ｎ計算装置Ｐｎ以外の他の計算装置に送信される。例えば、第ｎ＋１計算装置Ｐｎ＋１に送信される。ｎ＝Ｎの場合には、第１計算装置Ｐ１に送信される。
【００２８】
関数ｆ１，ｆ２，…，ｆＮは、上記したように衝突困難な一方向性関数であり互いに可換な関数である。すなわち、ｎ１及びｎ２を１≦ｎ１＜ｎ２≦Ｎを満たす整数として、任意の入力・に対して、例えばｆｎ１（ｆｎ２（・））＝ｆｎ２（ｆｎ１（・））であるとする。ｇを生成元とした位数ｑの巡回群をＧとして、ｎ＝１，２，…，Ｎとして、Ｋｎを１以上ｑ以下のランダムな整数であるとする。このとき、関数ｆｎはｆｎ（・）＝（・）Ｋｎ∈Ｇと例えば定義される。このようなべき乗の関数を用いる場合には、ｎ＝１，２，…，Ｎとして、第ｎ計算装置ＰｎはＫｎを生成する乱数生成部Ｐｎ５を有していても良い。
【００２９】
上記の具体例だと、図５に示すように、第１計算装置Ｐ１は、３つのグループＧ＿｛１，１｝，Ｇ＿｛１，２｝，Ｇ＿｛１，３｝のそれぞれを構成する各識別子を関数ｆ１に入力した場合の出力値を計算する。すなわち、ｆ１（ｉｄ＿｛１，１｝），ｆ１（ｉｄ＿｛１，５｝），ｆ１（ｉｄ＿｛１，２｝），ｆ１（ｉｄ＿｛１，６｝），ｆ１（ｉｄ＿｛１，７｝），ｆ１（ｉｄ＿｛１，３｝），ｆ１（ｉｄ＿｛１，４｝）を計算する。計算された出力値は、第２計算装置Ｐ２に送信される。
【００３０】
また、第２計算装置Ｐ２は、３つのグループＧ＿｛２，１｝，Ｇ＿｛２，２｝，Ｇ＿｛２，３｝のそれぞれを構成する各識別子を関数２に入力した場合の出力値を計算する。すなわち、ｆ２（ｉｄ＿｛２，２｝），ｆ２（ｉｄ＿｛２，５｝），ｆ２（ｉｄ＿｛２，６｝），ｆ２（ｉｄ＿｛２，１｝），ｆ２（ｉｄ＿｛２，７｝），ｆ２（ｉｄ＿｛２，３｝），ｆ２（ｉｄ＿｛２，４｝）を計算する。計算された出力値は、第１計算装置Ｐ１に送信される。
【００３１】
次に、ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎの関数値計算部Ｐｎ３は、他の計算装置により計算された出力値を関数ｆｎに入力した場合の出力値を計算する（ステップＳ４）。計算された出力値は、まだ関数ｆｎ’の処理が施されていない第ｎ’計算装置Ｐｎ’に送信される。例えば、第ｎ＋１計算装置Ｐｎ＋１に送信される。ｎ＝Ｎの場合には、第１計算装置Ｐ１に送信される。ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎの関数値計算部Ｐｎ３は、各識別子に全ての関数ｆ１，ｆ２，…，ｆＮの演算が施されるまでこの処理を行う。識別子に全ての関数ｆ１，ｆ２，…，ｆＮの演算が施された演算結果を「照合タグ」と呼ぶ。照合タグは、カウント部２に送信される。関数ｆ１，ｆ２，…，ｆＮが可換であることを考慮すると、ある識別子ｉｄに対応する照合タグの値は、ｆ１（ｆ２（…（ｆＮ（ｉｄ））））と等しい。
【００３２】
上記の具体例だと、図５に示すように、第１計算装置Ｐ１は、第２計算装置Ｐ２から受信した出力値ｆ２（ｉｄ＿｛２，２｝），ｆ２（ｉｄ＿｛２，５｝），ｆ２（ｉｄ＿｛２，６｝），ｆ２（ｉｄ＿｛２，１｝），ｆ２（ｉｄ＿｛２，７｝），ｆ２（ｉｄ＿｛２，３｝），ｆ２（ｉｄ＿｛２，４｝）のそれぞれを関数ｆ１に入力した場合の出力値ｆ１（ｆ２（ｉｄ＿｛２，２｝）），ｆ１（ｆ２（ｉｄ＿｛２，５｝）），ｆ１（ｆ２（ｉｄ＿｛２，６｝）），ｆ１（ｆ２（ｉｄ＿｛２，１｝）），ｆ１（ｆ２（ｉｄ＿｛２，７｝）），ｆ１（ｆ２（ｉｄ＿｛２，３｝）），ｆ１（ｆ２（ｉｄ＿｛２，４｝））を計算する。この例では、Ｎ＝２であるため、これらの出力値のそれぞれが照合タグとなる。
【００３３】
また、第２計算装置Ｐ２は、第１計算装置Ｐ１から受信した出力値ｆ１（ｉｄ＿｛１，１｝），ｆ１（ｉｄ＿｛１，５｝），ｆ１（ｉｄ＿｛１，２｝），ｆ１（ｉｄ＿｛１，６｝），ｆ１（ｉｄ＿｛１，７｝），ｆ１（ｉｄ＿｛１，３｝），ｆ１（ｉｄ＿｛１，４｝）のそれぞれを関数ｆ２に入力した場合の出力値ｆ２（ｆ１（ｉｄ＿｛１，１｝）），ｆ２（ｆ１（ｉｄ＿｛１，５｝）），ｆ２（ｆ１（ｉｄ＿｛１，２｝）），ｆ２（ｆ１（ｉｄ＿｛１，６｝）），ｆ２（ｆ１（ｉｄ＿｛１，７｝）），ｆ２（ｆ１（ｉｄ＿｛１，３｝）），ｆ２（ｆ１（ｉｄ＿｛１，４｝））を計算する。この例では、Ｎ＝２であるため、これらの出力値のそれぞれが照合タグとなる。
【００３４】
グループＧ＿｛ｎ，Ｌ｝から生成された照合タグの集合をＷ＿｛ｎ，Ｌ｝とすると、図５に示すように、Ｗ＿｛１，１｝＝（ｆ２（ｆ１（ｉｄ＿｛１，１｝）），ｆ２（ｆ１（ｉｄ＿｛１，５｝））），Ｗ＿｛１，２｝＝（ｆ２（ｆ１（ｉｄ＿｛１，２｝）），ｆ２（ｆ１（ｉｄ＿｛１，６｝）），ｆ２（ｆ１（ｉｄ＿｛１，７｝））），Ｗ＿｛１，３｝＝（ｆ２（ｆ１（ｉｄ＿｛１，３｝）），ｆ２（ｆ１（ｉｄ＿｛１，４｝））），Ｗ＿｛２，１｝＝（ｆ１（ｆ２（ｉｄ＿｛２，２｝）），ｆ１（ｆ２（ｉｄ＿｛２，５｝）），ｆ１（ｆ２（ｉｄ＿｛２，６｝））），Ｗ＿｛２，２｝＝（ｆ１（ｆ２（ｉｄ＿｛２，１｝）），ｆ１（ｆ２（ｉｄ＿｛２，７｝））），Ｗ＿｛２，３｝＝（ｆ１（ｆ２（ｉｄ＿｛２，３｝）），ｆ１（ｆ２（ｉｄ＿｛２，４｝）））となる。
【００３５】
クライアント装置Ｃのカウント部２は、第１，２，…，Ｎ計算装置Ｐ１，Ｐ２，…，ＰＮから照合タグを受け取り、各条件の組を構成する条件と同じ重複除去後条件を満たすレコードに対する照合タグを参照することにより、その各組を構成する全ての条件に共通する照合タグの数をカウントする（ステップＳ５）。
【００３６】
上記の具体例だと、第一の条件の組Ｃ１∧Ｃ２を構成する条件はＣ１及びＣ２である。したがって、図５に例示するように、カウント部２は、Ｃ１に対応する照合タグの集合Ｗ＿｛１，１｝と、Ｃ２に対応する照合タグの集合Ｗ＿（２，１）とを参照して、２つの集合Ｗ＿｛１，１｝，Ｗ＿（２，１）に共通する照合タグの数をカウントする。すなわち、２つの集合Ｗ＿｛１，１｝，Ｗ＿（２，１）の積集合の要素の数｜Ｗ＿｛１，１｝∩Ｗ＿（２，１）｜をカウントする。条件と照合タグの対応関係については、図４及び図５を参照のこと。関数ｆ１及びｆ２が可換であり、同じ対象には異なる複数のデータ集合Ｓｎにおいて同じ識別子が割り当てられていることを考慮すると、この例だと、Ｗ＿｛１，１｝の照合タグｆ２（ｆ１（ｉｄ＿｛１，５｝））と、Ｗ＿（２，１）の照合タグｆ１（ｆ２（ｉｄ＿｛２，５｝））とが一致する。したがって、第一の条件の組Ｃ１∧Ｃ２に対応するカウント数は１となる。他の条件の組についても同様にカウントを行う。
【００３７】
このように、重複する条件についての照合タグの生成及び送信を一回しか行わないことにより、従来よりも効率良くマッチングを行うことができる。
【００３８】
［変形例等］
上記の例では、ｎ＝１，２，…，Ｎとして、関数値計算部Ｐｎ３は、識別子を関数ｆｎに入力した場合の出力値を計算したが、Ｈを衝突困難な一方向性ハッシュ関数として、識別子のハッシュ値Ｈ（識別子）を関数ｆｎに入力した場合の出力値を計算してもよい。この場合、第１，２，…，Ｎ計算装置Ｐ１，Ｐ２，…，ＰＮにより計算される、ある識別子に対応する照合タグは、ｆ１（ｆ２（…（ｆＮ（Ｈ（識別子）））））となる。識別子の代わりに識別子のハッシュ値を用いることにより、安全性が増す。
【００３９】
ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎは、関数値計算部Ｐｎ３により計算された出力値を辞書順やランダムな順序等の所定の並替方法で並び替えて出力する並替部Ｐｎ４を有していてもよい。並替方法は、元の順番を隠せればどのような方法でも良い。並替部Ｐｎ４は、グループＧごとに並び替えを行う。
【００４０】
図５の例だと、第１計算部Ｐ１の並替部Ｐ１４は、関数値計算部Ｐｎ３が計算したグループＧ＿｛１，１｝に対応する出力値ｆ１（ｉｄ＿｛１，１｝），ｆ１（ｉｄ＿｛１，５｝）を所定の並替方法で並び替えて第２計算装置Ｐ２に送信し、関数値計算部Ｐｎ３が計算したグループＧ＿｛１，２｝に対応する出力値ｆ１（ｉｄ＿｛１，２｝），ｆ１（ｉｄ＿｛１，６｝），ｆ１（ｉｄ＿｛１，７｝）を所定の並替方法で並び替えて第２計算装置Ｐ２に送信し、関数値計算部Ｐｎ３が計算したグループＧ＿｛１，３｝に対応する出力値ｆ１（ｉｄ＿｛１，３｝），ｆ１（ｉｄ＿｛１，４｝）を所定の並替方法で並び替えて第２計算装置Ｐ２に送信してもよい。
【００４１】
同様に、第１計算部Ｐ１の並替部Ｐ１４は、関数値計算部Ｐｎ３が計算したグループＧ＿｛２，１｝に対応する出力値ｆ１（ｆ２（ｉｄ＿｛２，２｝）），ｆ１（ｆ２（ｉｄ＿｛２，５｝）），ｆ１（ｆ２（ｉｄ＿｛２，６｝））を所定の並替方法で並び替えてカウント部２に送信し、関数値計算部Ｐｎ３が計算したグループＧ＿｛２，２｝に対応する出力値ｆ１（ｆ２（ｉｄ＿｛２，１｝）），ｆ１（ｆ２（ｉｄ＿｛２，７｝））を所定の並替方法で並び替えてカウント部２に送信し、関数値計算部Ｐｎ３が計算したグループＧ＿｛２，３｝に対応する出力値ｆ１（ｆ２（ｉｄ＿｛２，３｝）），ｆ１（ｆ２（ｉｄ＿｛２，４｝））を所定の並替方法でカウント部２に送信してもよい。
【００４２】
このように、グループごとに所定の並替方法で並び替えて出力することにより、安全性が増す。より具体的には、後述するように、カウント部２が計算装置の何れかに設けられている場合には、並び替えずに出力値を送信すると、他の計算装置が有するレコードの識別子についての情報をその計算装置が知ることができる可能性がある。グループごとに所定の並替方法で並び替えて出力することにより、カウント部２が計算装置の何れかに設けられている場合であっても、他の計算装置が有するレコードの識別子についての情報をその計算装置に対して秘匿化することができる。
【００４３】
クライアント装置Ｃを構成する重複除去後条件生成部１及びカウント部２のそれぞれは、計算装置の何れかに設けられていてもよい。
【００４４】
カウント部２は、各条件の組を構成する全ての条件に対する照合タグのユニーク数をカウントしてもよい。換言すれば、各条件の組を構成する全ての条件に対する照合タグの集合の和集合の要素の数をカウントしてもよい。ユニーク数は、重複を除いた要素の数である。例えば、集合｛１，２，２，３，３，３，４｝のユニーク数は４である。
【００４５】
また、カウント部２は、条件の組を構成する全ての条件に共通する照合タグの数又はユニーク数をカウントした後に、それらの数をその条件の組を構成する何れかの条件に対応する照合タグの数で割った値を計算して出力してもよい。
【００４６】
ｎ＝１，２，…，Ｎとして、第ｎ計算装置Ｐｎの各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００４７】
クライアント装置Ｃ、第ｎ計算装置の構成をコンピュータによって実現する場合、これらの装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４９】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上記の変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００５０】
Ｃ      クライアント装置
１      重複除去後条件生成部
２      カウント部
Ｐｎ    第ｎ計算装置
Ｐｎ１  記憶部
Ｐｎ２  レコード抽出部
Ｐｎ３  関数値計算部
Ｐｎ４  並替部
Ｐｎ５  乱数生成部
【図１】
0005524012.tif 000002
【図２】
0005524012.tif 000003
【図３】
0005524012.tif 000004
【図４】
0005524012.tif 000005
【図５】
0005524012.tif 000006
【図６】
0005524012.tif 000007