マッチングシステム、マッチングシステムの方法、結合装置及びプログラム
【課題】キーカラムの一致するデータの情報を秘匿化したマッチング技術を提供する。
【解決手段】マッチングシステムは、第一結合装置及び第二結合装置を備える。第一結合装置及び第二結合装置のそれぞれは、秘密鍵及び可換暗号関数ｆを用いて、キーカラムのデータの情報を秘匿化して、マッチングを行う。これにより、キーカラムの一致するデータの情報を秘匿化することができ、プライバシーを保護したデータ処理をすることができる。
【解決手段】マッチングシステムは、第一結合装置及び第二結合装置を備える。第一結合装置及び第二結合装置のそれぞれは、秘密鍵及び可換暗号関数ｆを用いて、キーカラムのデータの情報を秘匿化して、マッチングを行う。これにより、キーカラムの一致するデータの情報を秘匿化することができ、プライバシーを保護したデータ処理をすることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の表形式のデータについて非開示のまま必要なデータを結合する技術に関する。
【背景技術】
【０００２】
非特許文献１に、複数の表形式のデータについて非開示のまま必要なデータを結合する技術が記載されている。以下、非特許文献１に記載された技術でできることを簡単に説明する（例えば、非特許文献１参照。）。
【０００３】
図１０に示すように、第一テーブル及び第二テーブルがあるとする。非特許文献１の技術により、第一テーブルのキーカラムのデータと、第二テーブルのキーカラムのデータとで一致するものを特定し、その一致するデータを含むタプル（行）のデータを結合して取得することができる。
【０００４】
図１０の例だと、第一テーブルのキーカラム及び第二テーブルのキーカラムは、０１４及び０３４のデータが共に含む。したがって、取得することができる結合データは、データ０１４と第一テーブルの０１４のデータを含むタプルのデータｘｘｘと第二テーブルの０１４のデータを含むタプルのデータｂｂｂとを結合したデータ、及び、データ０３４と第一テーブルの０３４のデータを含むタプルのデータｚｚｚと第二テーブルの０３４のデータを含むタプルのデータｃｃｃとを結合したデータとなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R.Agrawal, A.V.Evfimievski, and R.Srikant, “Information Sharing Across Private Databases”, ACM SIGMOD 2003, pp.86-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１の技術では、キーカラムの一致するデータを含むタプルのデータを結合したデータのみならず、キーカラムの一致するデータ自体が分かってしまう。図１０の例では、データ０１４及び０３４において、一致するということが分かってしまう。
【０００７】
この発明は、キーカラムの一致するデータの情報を秘匿化したマッチングシステム、方法、結合装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
この発明の第一の態様であるマッチングシステムは、第一結合装置及び第二結合装置を含む。ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数とする。第一結合装置は、第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信部と、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、ｆ（ｅＳ，ｙ）を鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（E（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、Ｅ＋（E（ｅｘｔ’（ｖ’）））をｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（E（ｅｘｔ’（ｖ’））））を計算する第四計算部と、ｈ’（ｆ（ｅＳ，ｙ））、ｆ（ｅＳ’，ｙ）及びｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第二結合装置に送信する第一送信部と、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、第一結合装置が保有するテーブルの各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）をｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、ｘ及びｃの組（ｘ，ｃ）を第二結合装置に送信する第二送信部と、を含む。第二結合装置は、第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、第二結合装置が保有するテーブルの各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置に送信する送信部と、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第一結合装置から受信する第一受信部と、組（ｘ，ｃ）を第一結合装置から受信する第二受信部と、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、検出されたペアを構成するｆ（ｅＲ，ｘ）を鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて検出されたペアを構成するｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、検出されたペアを構成するｃをｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、検出されたペアを構成するｃ’をｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（E（ｅｘｔ’（ｖ’）））を計算する第二復号部と、Ｅ＋（E（ｅｘｔ’（ｖ’）））を、復号関数Ｅ＋＊及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号部と、を含む。
【０００９】
この発明の第二の態様であるマッチングシステムは、第一結合装置及び第二結合装置を含む。ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数とする。第一結合装置は、第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信部と、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、ｆ（ｅＳ，ｙ）及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第二結合装置に送信する第一送信部と、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、ｘ及びＥ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第二結合装置に送信する第二送信部と、を含む。第二結合装置は、第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、第二結合装置が保有するテーブルの各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置に送信する送信部と、組（ｆ（ｅＳ，ｙ），Ｅ＋（ｅｘｔ’（ｖ’）））を第一結合装置から受信する第一受信部と、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第一結合装置から受信する第二受信部と、第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、を含む。
【発明の効果】
【００１０】
キーカラムの一致するデータの情報を秘匿化することができる。
【図面の簡単な説明】
【００１１】
【図１】マッチングシステムの例を説明するためのブロック図。
【図２】第一実施形態の第一結合装置の例を説明するためのブロック図。
【図３】第一実施形態の第二結合装置の例を説明するためのブロック図。
【図４】第二実施形態の第一結合装置の例を説明するためのブロック図。
【図５】第二実施形態の第二結合装置の例を説明するためのブロック図。
【図６】第一実施形態の第一結合装置の処理の流れの例を説明するためのフローチャート。
【図７】第一実施形態の第二結合装置の処理の流れの例を説明するためのフローチャート。
【図８】第二実施形態の第一結合装置の処理の流れの例を説明するためのフローチャート。
【図９】第二実施形態の第二結合装置の処理の流れの例を説明するためのフローチャート。
【図１０】従来のマッチングシステムの概要を説明するための図。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明の実施形態を説明する。
【００１３】
［第一実施形態］
第一実施形態のマッチングシステムは、図１に示すように、第一結合装置Ｓ及び第二結合装置Ｒを例えば備える。
【００１４】
第一結合装置Ｓは、図２に示すように、記憶部Ｓ０、テーブル記憶部Ｓ１、第一ハッシュ値計算部Ｓ２、秘密鍵生成部Ｓ３、第一計算部Ｓ４、第二計算部Ｓ５、第二ハッシュ値計算部Ｓ６、第三計算部Ｓ７、再暗号化部Ｓ８、第四計算部Ｓ９、第一送信部Ｓ１０、第五計算部Ｓ１１、第六計算部Ｓ１２、第七計算部Ｓ１３、第二送信部Ｓ１４を例えば備える。
【００１５】
第二結合装置Ｒは、図３に示すように、記憶部Ｒ０、テーブル記憶部Ｒ１、ハッシュ値計算部Ｒ２、秘密鍵生成部Ｒ３、第一計算部Ｒ４、送信部Ｒ５、暗号化部Ｒ６、第二受信部Ｒ７、第一受信部Ｒ１５、第二計算部Ｒ８、検出部Ｒ９、第三計算部Ｒ１０、第四計算部Ｒ１１、第二復号部Ｒ１２、第一復号部Ｒ１３、第三復号部Ｒ１４を例えば備える。
【００１６】
第一結合装置Ｓは、テーブルＴＳを保有する。テーブルＴＳはテーブル記憶部Ｓ１に記憶されている。一方、第二結合装置Ｒは、テーブルＴＲを保有する。テーブルＴＲはテーブル記憶部Ｒ１に記憶されている。
【００１７】
テーブルＴＳ及びテーブルＴＲは、カラム（列）及びタプル（行）で構成される。マッチングシステムは、テーブルＴＳ及びテーブルＴＲの所定のカラムにおいて一致するデータを特定し、その一致するデータを含むタプルの全部又は一部のデータを結合したデータを取得する。一致するデータを特定する対象となるカラムをキーカラムと呼ぶことにする。テーブルＴＳのキーカラムＶＳ及びテーブルＴＲのキーカラムＶＲは予め定められているものとする。
【００１８】
第一結合装置Ｓの第一ハッシュ値計算部Ｓ２（図２）は、キーカラムＶＳの各データｖのハッシュ値ｈ（ｖ）を計算する（ステップＡ１）。ハッシュ値ｈ（ｖ）は、第五計算部Ｓ１１及び第六計算部Ｓ１２に送信される。
【００１９】
第一結合装置Ｓの秘密鍵生成部Ｓ３は、秘密鍵ｅＳ及び秘密鍵ｅＳ’を生成する（ステップＡ２）。秘密鍵ｅＳは、第一計算部Ｓ４及び第五計算部Ｓ１１に送信される。秘密鍵ｅＳ’は、第二計算部Ｓ５及び第六計算部Ｓ１２に送信される。秘密鍵ｅＳ及び秘密鍵ｅＳ’は、後述する関数ｆで用いることができればどのようなものでもよい。
【００２０】
第二結合装置Ｒのハッシュ値計算部Ｒ２（図３）は、キーカラムＶＲの各データｖ’のハッシュ値ｈ（ｖ’）を計算する（ステップＢ１）。ハッシュ値ｈ（ｖ’）は、第一計算部Ｒ４に送信される。
【００２１】
第二結合装置Ｒの秘密鍵生成部Ｒ３は、秘密鍵ｅＲを生成する（ステップＢ２）。秘密鍵ｅＲは、第一計算部Ｒ４及び第二計算部Ｒ８に送信される。秘密鍵ｅＲは、後述する関数ｆで用いることができればどのようなものでもよい。
【００２２】
第二結合装置Ｒの第一計算部Ｒ４は、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する（ステップＢ３）。計算されたｙは、送信部Ｒ５に送信される。関数ｆは、逆関数が存在する、所定の秘密鍵を用いた可換暗号関数である。この例では、関数ｆは、所定の秘密鍵として秘密鍵ｅＲを用いている。
【００２３】
例えば、ｐを素数、所定の秘密鍵ｋｓを用いた関数ｆｋｓは次のようにして構成することができる。
【００２４】
ｆｋｓ（ｘ）＝ｘｋｓ ｍｏｄ ｐ
このとき、所定の秘密鍵ｋｒを用いた関数ｆｋｒをｆｋｒ＝ｘｋｒ ｍｏｄ ｐとすると、
ｆｋｓ（ｆｋｒ（ｘ））＝（ｘｋｒ）ｋｓ ｍｏｄ ｐ＝（ｘｋｓ）ｋｒ ｍｏｄ ｐ＝ｆｋｒ（ｆｋｓ（ｘ））となり、関数ｆｋｓ及び関数ｆｋｒが可換となることがわかる。
【００２５】
第二結合装置Ｒの暗号化部Ｒ６は、各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を所定の暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する（ステップＢ４）。計算されたＥ（ｅｘｔ’（ｖ’））は、送信部Ｒ５に送信される。
【００２６】
第二結合装置Ｒの送信部Ｒ５は、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置Ｓに送信する（ステップＢ５）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））は、例えば辞書順に第一結合装置Ｓに送信される。
【００２７】
第一結合装置Ｓの受信部Ｓ１６（図２）は、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を受信する（ステップＡ３）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））のｙは、第一計算部Ｓ４及び第二計算部Ｓ５に送信される。
【００２８】
第一結合装置Ｓの第一計算部Ｓ４は、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する（ステップＡ４）。ｆ（ｅＳ，ｙ）は、第二ハッシュ値計算部Ｓ６及び第一送信部Ｓ１０に送信される。
【００２９】
第一結合装置Ｓの第二計算部Ｓ５は、第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する（ステップＡ５）。ｆ（ｅＳ’，ｙ）は、第一送信部Ｓ１０に送信される。
【００３０】
第一結合装置Ｓの第二ハッシュ値計算部Ｓ６は、ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する（ステップＡ６）。ｈ’（ｆ（ｅＳ，ｙ））は、第一送信部Ｓ１０に送信される。
【００３１】
第一結合装置Ｓの第三計算部Ｓ７は、ｆ（ｅＳ，ｙ）を鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する（ステップＡ７）。ｋ’は、第四計算部Ｓ９に送信される。
【００３２】
第一結合装置Ｓの再暗号化部Ｓ８は、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＡ８）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第四計算部Ｓ９に送信される。
【００３３】
第一結合装置Ｓの第四計算部Ｓ９は、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））をｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する（ステップＡ９）。ｃ’は、第一送信部Ｓ１０に送信される。
【００３４】
第一結合装置Ｓの第一送信部Ｓ１０は、ｈ’（ｆ（ｅＳ，ｙ））、ｆ（ｅＳ’，ｙ）及びｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第二結合装置Ｒに送信する（ステップＡ１０）。
【００３５】
第一結合装置Ｓの第五計算部Ｓ１１は、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する（ステップＡ１１）。ｘは、第二送信部Ｓ１４に送信される。
【００３６】
第一結合装置Ｓの第六計算部Ｓ１２は、ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する（ステップＡ１２）。ｋは、第七計算部Ｓ１３に送信される。
【００３７】
第一結合装置Ｓの第七計算部Ｓ１３は、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）をｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する（ステップＡ１３）。ｃは、第二送信部Ｓ１４に送信される。
【００３８】
第一結合装置Ｓの第二送信部Ｓ１４は、ｘ及びｃの組（ｘ，ｃ）を第二結合装置Ｒに送信する（ステップＡ１４）。組（ｘ，ｃ）は、例えば辞書順で第二結合装置Ｒに送信される。
【００３９】
第二結合装置Ｒの第一受信部Ｒ１５（図３）は、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第一結合装置Ｓから受信する（ステップＢ６）。組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）は、検出部Ｒ９に送信される。
【００４０】
第二結合装置Ｒの第二受信部Ｒ７は、組（ｘ，ｃ）を第一結合装置Ｓから受信する（ステップＢ７）。ｘは、第二計算部Ｒ８に送信される。組（ｘ，ｃ）は、検出部Ｒ９に送信される。
【００４１】
第二結合装置Ｒの第二計算部Ｒ８は、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する（ステップＢ８）。ｈ’（ｆ（ｅＲ，ｘ））は、検出部Ｒ９に送信される。
【００４２】
第二結合装置Ｒの検出部Ｒ９は、第二計算部Ｒ８が計算したｈ’（ｆ（ｅＲ，ｘ））と、受信したｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する（ステップＢ９）。以下のステップＢ１１以降のステップは、この検出されたペアを構成する情報について行われる。
【００４３】
第二結合装置Ｒの第三計算部Ｒ１０は、検出されたペアを構成するｆ（ｅＲ，ｘ）を鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する（ステップＢ１０）。ｇ（ｆ（ｅＲ，ｘ））は、第二復号部Ｒ１２に送信される。
【００４４】
第二結合装置Ｒの第四計算部Ｒ１１は、秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する（ステップＢ１１）。ｆ（ｅＳ’，ｈ（ｖ’））は、第一復号部１３に送信される。
【００４５】
第二結合装置Ｒの第一復号部Ｒ１３は、検出されたペアを構成するｃをｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する（ステップＢ１２）。復号関数Ｋ*は、暗号化関数Ｋに対応する復号関数である。任意のｘに対してＫ*（Ｋ（ｘ））＝ｘとなる。
【００４６】
第二結合装置Ｒの第二復号部Ｒ１２は、検出されたペアを構成するｃ’をｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＢ１３）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第三復号部Ｒ１４に送信される。復号関数Ｋ’*は、暗号化関数Ｋ’に対応する復号関数である。任意のｘに対してＫ’*（Ｋ’（ｘ））＝ｘとなる。
【００４７】
第二結合装置Ｒの第三復号部Ｒ１４は、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、再復号関数Ｅ＋*及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する（ステップＢ１４）。再復号関数Ｅ＋*は、再暗号化関数Ｅ＋に対応する復号関数である。任意のｘに対してＥ＋*（Ｅ＋（ｘ））＝ｘとなる。復号関数Ｅ*は、暗号化関数Ｅに対応する復号関数である。任意のｘに対してＥ*（Ｅ（ｘ））＝ｘとなる。
【００４８】
第一復号部Ｒ１３により計算されるｅｘｔ（ｖ）が、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータを含む、テーブルＴＳのタプルの全部又は一部のデータとなる。また、第三復号部Ｒ１４により計算されるｅｘｔ’（ｖ’）が、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータを含む、テーブルＴＲのタプルの全部又は一部のデータとなる。
【００４９】
ｅｘｔ’（ｖ’）を再暗号化可能な暗号関数で暗号化することにより、第二結合装置ＲによるテーブルＴＲにおける、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータｖ＊のタプルの特定を困難にしている。
【００５０】
また、ｆ（ｅＳ，ｙ）から秘密鍵ｋ’を生成して、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を暗号化し、第二結合装置Ｒにはｆ（ｅＳ，ｙ）ではなく、ｈ’（ｆ（ｅＳ，ｙ））を送信することで、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータｖ＊のｅｘｔ’（ｖ＊）の復号のみを可能としている。
【００５１】
［第二実施形態］
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
【００５２】
第二実施形態の第一結合装置Ｓは、図４に示すように、記憶部Ｓ０、テーブル記憶部Ｓ１、ハッシュ値計算部Ｓ２、秘密鍵生成部Ｓ３、第一計算部Ｓ４、第二計算部Ｓ５、再暗号化部Ｓ８、第一送信部Ｓ１０、第二送信部Ｓ１４、暗号化部Ｓ１５を例えば備える。
【００５３】
第二実施形態の第二結合装置Ｒは、図５に示すように、記憶部Ｒ０、テーブル記憶部Ｒ１、ハッシュ値計算部Ｒ２、秘密鍵生成部Ｒ３、第一計算部Ｒ４、送信部Ｒ５、暗号化部Ｒ６、第二受信部Ｒ７、第一受信部Ｒ１５、第二計算部Ｒ８、検出部Ｒ９、第二復号部Ｒ１２、第一復号部Ｒ１３を例えば備える。
【００５４】
第一結合装置Ｓのハッシュ値計算部Ｓ２（図４）は、テーブル記憶部Ｓ１に記憶されているテーブルＴＳのキーカラムＶｓの各データｖのハッシュ値ｈ（ｖ）を計算する（ステップＡ１）。ハッシュ値ｈ（ｖ）は、第二計算部Ｓ５に送信される。
【００５５】
第一結合装置Ｓの秘密鍵生成部Ｓ３は、秘密鍵ｅＳを生成する（ステップＡ２）。秘密鍵ｅＳは、第二計算部Ｓ５及び第一計算部Ｓ４に送信される。
【００５６】
第二結合装置Ｒのハッシュ値計算部Ｒ２（図５）は、テーブル記憶部Ｒ１に記憶されてうるテーブルＴＲのキーカラムＶＲの各データｖ’のハッシュ値ｈ（ｖ’）を計算する（ステップＢ１）。ハッシュ値ｈ（ｖ’）は、第一計算部Ｒ４に送信される。
【００５７】
第二結合装置Ｒの秘密鍵生成部Ｒ３は、秘密鍵ｅＲを生成する（ステップＢ２）。秘密鍵ｅＲは、第一計算部Ｒ４及び第二計算部Ｒ８に送信される。
【００５８】
第二結合装置Ｒの第一計算部Ｒ４は、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する（ステップＢ３）。計算されたｙは、送信部Ｒ５に送信される。
【００５９】
第二結合装置Ｒの暗号化部Ｒ６は、各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を所定の暗号関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する（ステップＢ４）。計算されたＥ（ｅｘｔ’（ｖ’））は、送信部Ｒ５に送信される。
【００６０】
第二結合装置Ｒの送信部Ｒ５は、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置Ｓに送信する（ステップＢ５）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））は、例えば辞書順に第一結合装置Ｓに送信される。
【００６１】
第一結合装置Ｓの受信部Ｓ１６（図４）は、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を受信する（ステップＡ３）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））のｙは、第一計算部Ｓ４に送信される。
【００６２】
第一結合装置Ｓの第一計算部Ｓ４は、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する（ステップＡ４）。ｆ（ｅＳ，ｙ）は、第一送信部Ｓ１０に送信される。
【００６３】
第一結合装置Ｓの再暗号化部Ｓ８は、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＡ８）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第一送信部Ｓ１０に送信される。
【００６４】
第一結合装置Ｓの第一送信部Ｓ１０は、ｆ（ｅＳ，ｙ）及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第二結合装置Ｒに送信する（ステップＡ１０）。
【００６５】
第一結合装置Ｓの第二計算部Ｓ５は、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する（ステップＡ１１）。ｘは、第二送信部Ｓ１４に送信される。
【００６６】
第一結合装置Ｓの暗号化部Ｓ１５は、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を所定の暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する（ステップＡ１３）。Ｅ（ｅｘｔ（ｖ））は、第二送信部Ｓ１４に送信される。
【００６７】
第一結合装置Ｓの第二送信部Ｓ１４は、ｘ及びＥ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第二結合装置Ｒに送信する（ステップＡ１４）。組（ｘ，Ｅ（ｅｘｔ（ｖ）））は、例えば辞書順で第二結合装置Ｒに送信される。
【００６８】
第二結合装置Ｒの第一受信部Ｒ１５（図５）は、組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第一結合装置Ｓから受信する（ステップＢ６）。組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））は、検出部Ｒ９に送信される。
【００６９】
第二結合装置Ｒの第二受信部Ｒ７は、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第一結合装置Ｓから受信する（ステップＢ７）。ｘは、第二計算部Ｒ８に送信される。組（ｘ，Ｅ（ｅｘ 第二結合装置Ｒの第二計算部Ｒ８は、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する（ステップＢ８）。ｆ（ｅＲ，ｘ）は、検出部Ｒ９に送信される。
【００７０】
第二結合装置Ｒの検出部Ｒ９は、第二計算部Ｒ８が計算したｆ（ｅＲ，ｘ）と、受信したｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出する（ステップＢ９）。検出部Ｒ９は、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する。
【００７１】
第一復号部Ｒ１３が、検出されたペアを構成するＥ（ｅｘｔ（ｖ））を復号関数Ｅ*により復号したｅｘｔ（ｖ）を計算して出力してもよい（ステップＢ１２）。
【００７２】
また、第二復号部Ｒ１２が、検出されたペアを構成するＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を復号関数Ｅ＋*及びＥ*により復号したｅｘｔ’（ｖ’）を計算して出力してもよい（ステップＢ１３）。
【００７３】
［変形例等］
ハッシュ関数ｈ’は、ハッシュ関数ｈと同じでも異なっていてもよい。異なっている場合には、同じ場合よりも安全性が高くなる。
【００７４】
暗号化関数Ｋ’は、暗号化関数Ｋと同じでも異なっていてもよい。異なっている場合には、同じ場合よりも安全性が高くなる。
【００７５】
なお、上記の実施形態では、第一結合装置Ｓ、第二結合装置Ｒの各部間でデータは直接送受信されていたが、データは記憶部Ｓ０，Ｒ０を介してやり取りされてもよい。
【００７６】
第一結合装置Ｓをコンピュータによって実現する場合、第一結合装置Ｓの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第一結合装置Ｓの各部の処理機能がコンピュータ上で実現される。
【００７７】
同様に、第二結合装置Ｒをコンピュータによって実現する場合、第二結合装置Ｒの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第二結合装置Ｒの各部の処理機能がコンピュータ上で実現される。
【００７８】
これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７９】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８０】
また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【技術分野】
【０００１】
この発明は、複数の表形式のデータについて非開示のまま必要なデータを結合する技術に関する。
【背景技術】
【０００２】
非特許文献１に、複数の表形式のデータについて非開示のまま必要なデータを結合する技術が記載されている。以下、非特許文献１に記載された技術でできることを簡単に説明する（例えば、非特許文献１参照。）。
【０００３】
図１０に示すように、第一テーブル及び第二テーブルがあるとする。非特許文献１の技術により、第一テーブルのキーカラムのデータと、第二テーブルのキーカラムのデータとで一致するものを特定し、その一致するデータを含むタプル（行）のデータを結合して取得することができる。
【０００４】
図１０の例だと、第一テーブルのキーカラム及び第二テーブルのキーカラムは、０１４及び０３４のデータが共に含む。したがって、取得することができる結合データは、データ０１４と第一テーブルの０１４のデータを含むタプルのデータｘｘｘと第二テーブルの０１４のデータを含むタプルのデータｂｂｂとを結合したデータ、及び、データ０３４と第一テーブルの０３４のデータを含むタプルのデータｚｚｚと第二テーブルの０３４のデータを含むタプルのデータｃｃｃとを結合したデータとなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R.Agrawal, A.V.Evfimievski, and R.Srikant, “Information Sharing Across Private Databases”, ACM SIGMOD 2003, pp.86-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１の技術では、キーカラムの一致するデータを含むタプルのデータを結合したデータのみならず、キーカラムの一致するデータ自体が分かってしまう。図１０の例では、データ０１４及び０３４において、一致するということが分かってしまう。
【０００７】
この発明は、キーカラムの一致するデータの情報を秘匿化したマッチングシステム、方法、結合装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
この発明の第一の態様であるマッチングシステムは、第一結合装置及び第二結合装置を含む。ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数とする。第一結合装置は、第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信部と、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、ｆ（ｅＳ，ｙ）を鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（E（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、Ｅ＋（E（ｅｘｔ’（ｖ’）））をｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（E（ｅｘｔ’（ｖ’））））を計算する第四計算部と、ｈ’（ｆ（ｅＳ，ｙ））、ｆ（ｅＳ’，ｙ）及びｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第二結合装置に送信する第一送信部と、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、第一結合装置が保有するテーブルの各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）をｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、ｘ及びｃの組（ｘ，ｃ）を第二結合装置に送信する第二送信部と、を含む。第二結合装置は、第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、第二結合装置が保有するテーブルの各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置に送信する送信部と、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第一結合装置から受信する第一受信部と、組（ｘ，ｃ）を第一結合装置から受信する第二受信部と、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、検出されたペアを構成するｆ（ｅＲ，ｘ）を鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて検出されたペアを構成するｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、検出されたペアを構成するｃをｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、検出されたペアを構成するｃ’をｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（E（ｅｘｔ’（ｖ’）））を計算する第二復号部と、Ｅ＋（E（ｅｘｔ’（ｖ’）））を、復号関数Ｅ＋＊及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号部と、を含む。
【０００９】
この発明の第二の態様であるマッチングシステムは、第一結合装置及び第二結合装置を含む。ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数とする。第一結合装置は、第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信部と、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、ｆ（ｅＳ，ｙ）及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第二結合装置に送信する第一送信部と、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、ｘ及びＥ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第二結合装置に送信する第二送信部と、を含む。第二結合装置は、第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、第二結合装置が保有するテーブルの各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置に送信する送信部と、組（ｆ（ｅＳ，ｙ），Ｅ＋（ｅｘｔ’（ｖ’）））を第一結合装置から受信する第一受信部と、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第一結合装置から受信する第二受信部と、第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、を含む。
【発明の効果】
【００１０】
キーカラムの一致するデータの情報を秘匿化することができる。
【図面の簡単な説明】
【００１１】
【図１】マッチングシステムの例を説明するためのブロック図。
【図２】第一実施形態の第一結合装置の例を説明するためのブロック図。
【図３】第一実施形態の第二結合装置の例を説明するためのブロック図。
【図４】第二実施形態の第一結合装置の例を説明するためのブロック図。
【図５】第二実施形態の第二結合装置の例を説明するためのブロック図。
【図６】第一実施形態の第一結合装置の処理の流れの例を説明するためのフローチャート。
【図７】第一実施形態の第二結合装置の処理の流れの例を説明するためのフローチャート。
【図８】第二実施形態の第一結合装置の処理の流れの例を説明するためのフローチャート。
【図９】第二実施形態の第二結合装置の処理の流れの例を説明するためのフローチャート。
【図１０】従来のマッチングシステムの概要を説明するための図。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明の実施形態を説明する。
【００１３】
［第一実施形態］
第一実施形態のマッチングシステムは、図１に示すように、第一結合装置Ｓ及び第二結合装置Ｒを例えば備える。
【００１４】
第一結合装置Ｓは、図２に示すように、記憶部Ｓ０、テーブル記憶部Ｓ１、第一ハッシュ値計算部Ｓ２、秘密鍵生成部Ｓ３、第一計算部Ｓ４、第二計算部Ｓ５、第二ハッシュ値計算部Ｓ６、第三計算部Ｓ７、再暗号化部Ｓ８、第四計算部Ｓ９、第一送信部Ｓ１０、第五計算部Ｓ１１、第六計算部Ｓ１２、第七計算部Ｓ１３、第二送信部Ｓ１４を例えば備える。
【００１５】
第二結合装置Ｒは、図３に示すように、記憶部Ｒ０、テーブル記憶部Ｒ１、ハッシュ値計算部Ｒ２、秘密鍵生成部Ｒ３、第一計算部Ｒ４、送信部Ｒ５、暗号化部Ｒ６、第二受信部Ｒ７、第一受信部Ｒ１５、第二計算部Ｒ８、検出部Ｒ９、第三計算部Ｒ１０、第四計算部Ｒ１１、第二復号部Ｒ１２、第一復号部Ｒ１３、第三復号部Ｒ１４を例えば備える。
【００１６】
第一結合装置Ｓは、テーブルＴＳを保有する。テーブルＴＳはテーブル記憶部Ｓ１に記憶されている。一方、第二結合装置Ｒは、テーブルＴＲを保有する。テーブルＴＲはテーブル記憶部Ｒ１に記憶されている。
【００１７】
テーブルＴＳ及びテーブルＴＲは、カラム（列）及びタプル（行）で構成される。マッチングシステムは、テーブルＴＳ及びテーブルＴＲの所定のカラムにおいて一致するデータを特定し、その一致するデータを含むタプルの全部又は一部のデータを結合したデータを取得する。一致するデータを特定する対象となるカラムをキーカラムと呼ぶことにする。テーブルＴＳのキーカラムＶＳ及びテーブルＴＲのキーカラムＶＲは予め定められているものとする。
【００１８】
第一結合装置Ｓの第一ハッシュ値計算部Ｓ２（図２）は、キーカラムＶＳの各データｖのハッシュ値ｈ（ｖ）を計算する（ステップＡ１）。ハッシュ値ｈ（ｖ）は、第五計算部Ｓ１１及び第六計算部Ｓ１２に送信される。
【００１９】
第一結合装置Ｓの秘密鍵生成部Ｓ３は、秘密鍵ｅＳ及び秘密鍵ｅＳ’を生成する（ステップＡ２）。秘密鍵ｅＳは、第一計算部Ｓ４及び第五計算部Ｓ１１に送信される。秘密鍵ｅＳ’は、第二計算部Ｓ５及び第六計算部Ｓ１２に送信される。秘密鍵ｅＳ及び秘密鍵ｅＳ’は、後述する関数ｆで用いることができればどのようなものでもよい。
【００２０】
第二結合装置Ｒのハッシュ値計算部Ｒ２（図３）は、キーカラムＶＲの各データｖ’のハッシュ値ｈ（ｖ’）を計算する（ステップＢ１）。ハッシュ値ｈ（ｖ’）は、第一計算部Ｒ４に送信される。
【００２１】
第二結合装置Ｒの秘密鍵生成部Ｒ３は、秘密鍵ｅＲを生成する（ステップＢ２）。秘密鍵ｅＲは、第一計算部Ｒ４及び第二計算部Ｒ８に送信される。秘密鍵ｅＲは、後述する関数ｆで用いることができればどのようなものでもよい。
【００２２】
第二結合装置Ｒの第一計算部Ｒ４は、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する（ステップＢ３）。計算されたｙは、送信部Ｒ５に送信される。関数ｆは、逆関数が存在する、所定の秘密鍵を用いた可換暗号関数である。この例では、関数ｆは、所定の秘密鍵として秘密鍵ｅＲを用いている。
【００２３】
例えば、ｐを素数、所定の秘密鍵ｋｓを用いた関数ｆｋｓは次のようにして構成することができる。
【００２４】
ｆｋｓ（ｘ）＝ｘｋｓ ｍｏｄ ｐ
このとき、所定の秘密鍵ｋｒを用いた関数ｆｋｒをｆｋｒ＝ｘｋｒ ｍｏｄ ｐとすると、
ｆｋｓ（ｆｋｒ（ｘ））＝（ｘｋｒ）ｋｓ ｍｏｄ ｐ＝（ｘｋｓ）ｋｒ ｍｏｄ ｐ＝ｆｋｒ（ｆｋｓ（ｘ））となり、関数ｆｋｓ及び関数ｆｋｒが可換となることがわかる。
【００２５】
第二結合装置Ｒの暗号化部Ｒ６は、各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を所定の暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する（ステップＢ４）。計算されたＥ（ｅｘｔ’（ｖ’））は、送信部Ｒ５に送信される。
【００２６】
第二結合装置Ｒの送信部Ｒ５は、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置Ｓに送信する（ステップＢ５）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））は、例えば辞書順に第一結合装置Ｓに送信される。
【００２７】
第一結合装置Ｓの受信部Ｓ１６（図２）は、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を受信する（ステップＡ３）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））のｙは、第一計算部Ｓ４及び第二計算部Ｓ５に送信される。
【００２８】
第一結合装置Ｓの第一計算部Ｓ４は、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する（ステップＡ４）。ｆ（ｅＳ，ｙ）は、第二ハッシュ値計算部Ｓ６及び第一送信部Ｓ１０に送信される。
【００２９】
第一結合装置Ｓの第二計算部Ｓ５は、第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する（ステップＡ５）。ｆ（ｅＳ’，ｙ）は、第一送信部Ｓ１０に送信される。
【００３０】
第一結合装置Ｓの第二ハッシュ値計算部Ｓ６は、ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する（ステップＡ６）。ｈ’（ｆ（ｅＳ，ｙ））は、第一送信部Ｓ１０に送信される。
【００３１】
第一結合装置Ｓの第三計算部Ｓ７は、ｆ（ｅＳ，ｙ）を鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する（ステップＡ７）。ｋ’は、第四計算部Ｓ９に送信される。
【００３２】
第一結合装置Ｓの再暗号化部Ｓ８は、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＡ８）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第四計算部Ｓ９に送信される。
【００３３】
第一結合装置Ｓの第四計算部Ｓ９は、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））をｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する（ステップＡ９）。ｃ’は、第一送信部Ｓ１０に送信される。
【００３４】
第一結合装置Ｓの第一送信部Ｓ１０は、ｈ’（ｆ（ｅＳ，ｙ））、ｆ（ｅＳ’，ｙ）及びｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第二結合装置Ｒに送信する（ステップＡ１０）。
【００３５】
第一結合装置Ｓの第五計算部Ｓ１１は、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する（ステップＡ１１）。ｘは、第二送信部Ｓ１４に送信される。
【００３６】
第一結合装置Ｓの第六計算部Ｓ１２は、ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する（ステップＡ１２）。ｋは、第七計算部Ｓ１３に送信される。
【００３７】
第一結合装置Ｓの第七計算部Ｓ１３は、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）をｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する（ステップＡ１３）。ｃは、第二送信部Ｓ１４に送信される。
【００３８】
第一結合装置Ｓの第二送信部Ｓ１４は、ｘ及びｃの組（ｘ，ｃ）を第二結合装置Ｒに送信する（ステップＡ１４）。組（ｘ，ｃ）は、例えば辞書順で第二結合装置Ｒに送信される。
【００３９】
第二結合装置Ｒの第一受信部Ｒ１５（図３）は、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を第一結合装置Ｓから受信する（ステップＢ６）。組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）は、検出部Ｒ９に送信される。
【００４０】
第二結合装置Ｒの第二受信部Ｒ７は、組（ｘ，ｃ）を第一結合装置Ｓから受信する（ステップＢ７）。ｘは、第二計算部Ｒ８に送信される。組（ｘ，ｃ）は、検出部Ｒ９に送信される。
【００４１】
第二結合装置Ｒの第二計算部Ｒ８は、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する（ステップＢ８）。ｈ’（ｆ（ｅＲ，ｘ））は、検出部Ｒ９に送信される。
【００４２】
第二結合装置Ｒの検出部Ｒ９は、第二計算部Ｒ８が計算したｈ’（ｆ（ｅＲ，ｘ））と、受信したｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する（ステップＢ９）。以下のステップＢ１１以降のステップは、この検出されたペアを構成する情報について行われる。
【００４３】
第二結合装置Ｒの第三計算部Ｒ１０は、検出されたペアを構成するｆ（ｅＲ，ｘ）を鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する（ステップＢ１０）。ｇ（ｆ（ｅＲ，ｘ））は、第二復号部Ｒ１２に送信される。
【００４４】
第二結合装置Ｒの第四計算部Ｒ１１は、秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する（ステップＢ１１）。ｆ（ｅＳ’，ｈ（ｖ’））は、第一復号部１３に送信される。
【００４５】
第二結合装置Ｒの第一復号部Ｒ１３は、検出されたペアを構成するｃをｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する（ステップＢ１２）。復号関数Ｋ*は、暗号化関数Ｋに対応する復号関数である。任意のｘに対してＫ*（Ｋ（ｘ））＝ｘとなる。
【００４６】
第二結合装置Ｒの第二復号部Ｒ１２は、検出されたペアを構成するｃ’をｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＢ１３）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第三復号部Ｒ１４に送信される。復号関数Ｋ’*は、暗号化関数Ｋ’に対応する復号関数である。任意のｘに対してＫ’*（Ｋ’（ｘ））＝ｘとなる。
【００４７】
第二結合装置Ｒの第三復号部Ｒ１４は、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、再復号関数Ｅ＋*及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する（ステップＢ１４）。再復号関数Ｅ＋*は、再暗号化関数Ｅ＋に対応する復号関数である。任意のｘに対してＥ＋*（Ｅ＋（ｘ））＝ｘとなる。復号関数Ｅ*は、暗号化関数Ｅに対応する復号関数である。任意のｘに対してＥ*（Ｅ（ｘ））＝ｘとなる。
【００４８】
第一復号部Ｒ１３により計算されるｅｘｔ（ｖ）が、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータを含む、テーブルＴＳのタプルの全部又は一部のデータとなる。また、第三復号部Ｒ１４により計算されるｅｘｔ’（ｖ’）が、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータを含む、テーブルＴＲのタプルの全部又は一部のデータとなる。
【００４９】
ｅｘｔ’（ｖ’）を再暗号化可能な暗号関数で暗号化することにより、第二結合装置ＲによるテーブルＴＲにおける、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータｖ＊のタプルの特定を困難にしている。
【００５０】
また、ｆ（ｅＳ，ｙ）から秘密鍵ｋ’を生成して、Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を暗号化し、第二結合装置Ｒにはｆ（ｅＳ，ｙ）ではなく、ｈ’（ｆ（ｅＳ，ｙ））を送信することで、テーブルＴＳ及びテーブルＴＲのキーカラムにおいて一致するデータｖ＊のｅｘｔ’（ｖ＊）の復号のみを可能としている。
【００５１】
［第二実施形態］
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
【００５２】
第二実施形態の第一結合装置Ｓは、図４に示すように、記憶部Ｓ０、テーブル記憶部Ｓ１、ハッシュ値計算部Ｓ２、秘密鍵生成部Ｓ３、第一計算部Ｓ４、第二計算部Ｓ５、再暗号化部Ｓ８、第一送信部Ｓ１０、第二送信部Ｓ１４、暗号化部Ｓ１５を例えば備える。
【００５３】
第二実施形態の第二結合装置Ｒは、図５に示すように、記憶部Ｒ０、テーブル記憶部Ｒ１、ハッシュ値計算部Ｒ２、秘密鍵生成部Ｒ３、第一計算部Ｒ４、送信部Ｒ５、暗号化部Ｒ６、第二受信部Ｒ７、第一受信部Ｒ１５、第二計算部Ｒ８、検出部Ｒ９、第二復号部Ｒ１２、第一復号部Ｒ１３を例えば備える。
【００５４】
第一結合装置Ｓのハッシュ値計算部Ｓ２（図４）は、テーブル記憶部Ｓ１に記憶されているテーブルＴＳのキーカラムＶｓの各データｖのハッシュ値ｈ（ｖ）を計算する（ステップＡ１）。ハッシュ値ｈ（ｖ）は、第二計算部Ｓ５に送信される。
【００５５】
第一結合装置Ｓの秘密鍵生成部Ｓ３は、秘密鍵ｅＳを生成する（ステップＡ２）。秘密鍵ｅＳは、第二計算部Ｓ５及び第一計算部Ｓ４に送信される。
【００５６】
第二結合装置Ｒのハッシュ値計算部Ｒ２（図５）は、テーブル記憶部Ｒ１に記憶されてうるテーブルＴＲのキーカラムＶＲの各データｖ’のハッシュ値ｈ（ｖ’）を計算する（ステップＢ１）。ハッシュ値ｈ（ｖ’）は、第一計算部Ｒ４に送信される。
【００５７】
第二結合装置Ｒの秘密鍵生成部Ｒ３は、秘密鍵ｅＲを生成する（ステップＢ２）。秘密鍵ｅＲは、第一計算部Ｒ４及び第二計算部Ｒ８に送信される。
【００５８】
第二結合装置Ｒの第一計算部Ｒ４は、各ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する（ステップＢ３）。計算されたｙは、送信部Ｒ５に送信される。
【００５９】
第二結合装置Ｒの暗号化部Ｒ６は、各データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を所定の暗号関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する（ステップＢ４）。計算されたＥ（ｅｘｔ’（ｖ’））は、送信部Ｒ５に送信される。
【００６０】
第二結合装置Ｒの送信部Ｒ５は、ｙ及びＥ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第一結合装置Ｓに送信する（ステップＢ５）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））は、例えば辞書順に第一結合装置Ｓに送信される。
【００６１】
第一結合装置Ｓの受信部Ｓ１６（図４）は、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を受信する（ステップＡ３）。組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））のｙは、第一計算部Ｓ４に送信される。
【００６２】
第一結合装置Ｓの第一計算部Ｓ４は、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する（ステップＡ４）。ｆ（ｅＳ，ｙ）は、第一送信部Ｓ１０に送信される。
【００６３】
第一結合装置Ｓの再暗号化部Ｓ８は、第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する（ステップＡ８）。Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））は、第一送信部Ｓ１０に送信される。
【００６４】
第一結合装置Ｓの第一送信部Ｓ１０は、ｆ（ｅＳ，ｙ）及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第二結合装置Ｒに送信する（ステップＡ１０）。
【００６５】
第一結合装置Ｓの第二計算部Ｓ５は、ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する（ステップＡ１１）。ｘは、第二送信部Ｓ１４に送信される。
【００６６】
第一結合装置Ｓの暗号化部Ｓ１５は、各データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を所定の暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する（ステップＡ１３）。Ｅ（ｅｘｔ（ｖ））は、第二送信部Ｓ１４に送信される。
【００６７】
第一結合装置Ｓの第二送信部Ｓ１４は、ｘ及びＥ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第二結合装置Ｒに送信する（ステップＡ１４）。組（ｘ，Ｅ（ｅｘｔ（ｖ）））は、例えば辞書順で第二結合装置Ｒに送信される。
【００６８】
第二結合装置Ｒの第一受信部Ｒ１５（図５）は、組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を第一結合装置Ｓから受信する（ステップＢ６）。組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））は、検出部Ｒ９に送信される。
【００６９】
第二結合装置Ｒの第二受信部Ｒ７は、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を第一結合装置Ｓから受信する（ステップＢ７）。ｘは、第二計算部Ｒ８に送信される。組（ｘ，Ｅ（ｅｘ 第二結合装置Ｒの第二計算部Ｒ８は、第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する（ステップＢ８）。ｆ（ｅＲ，ｘ）は、検出部Ｒ９に送信される。
【００７０】
第二結合装置Ｒの検出部Ｒ９は、第二計算部Ｒ８が計算したｆ（ｅＲ，ｘ）と、受信したｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出する（ステップＢ９）。検出部Ｒ９は、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する。
【００７１】
第一復号部Ｒ１３が、検出されたペアを構成するＥ（ｅｘｔ（ｖ））を復号関数Ｅ*により復号したｅｘｔ（ｖ）を計算して出力してもよい（ステップＢ１２）。
【００７２】
また、第二復号部Ｒ１２が、検出されたペアを構成するＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を復号関数Ｅ＋*及びＥ*により復号したｅｘｔ’（ｖ’）を計算して出力してもよい（ステップＢ１３）。
【００７３】
［変形例等］
ハッシュ関数ｈ’は、ハッシュ関数ｈと同じでも異なっていてもよい。異なっている場合には、同じ場合よりも安全性が高くなる。
【００７４】
暗号化関数Ｋ’は、暗号化関数Ｋと同じでも異なっていてもよい。異なっている場合には、同じ場合よりも安全性が高くなる。
【００７５】
なお、上記の実施形態では、第一結合装置Ｓ、第二結合装置Ｒの各部間でデータは直接送受信されていたが、データは記憶部Ｓ０，Ｒ０を介してやり取りされてもよい。
【００７６】
第一結合装置Ｓをコンピュータによって実現する場合、第一結合装置Ｓの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第一結合装置Ｓの各部の処理機能がコンピュータ上で実現される。
【００７７】
同様に、第二結合装置Ｒをコンピュータによって実現する場合、第二結合装置Ｒの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第二結合装置Ｒの各部の処理機能がコンピュータ上で実現される。
【００７８】
これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７９】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８０】
また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【特許請求の範囲】
【請求項１】
第一結合装置及び第二結合装置を含むマッチングシステムにおいて、
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置は、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、
上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、
上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、
上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算部と、
上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、
上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、
上記ｘ及び上記ｃの組（ｘ，ｃ）を上記第二結合装置に送信する第二送信部と、
を含み、
上記第二結合装置は、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信部と、
組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第一結合装置から受信する第一受信部と、
組（ｘ，ｃ）を上記第一結合装置から受信する第二受信部と、
上記第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、
上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、
上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、
上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、
上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、
上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて上記復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、上記復号関数Ｅ＋*及び復号関数Ｅで復号したｅｘｔ’（ｖ’）を計算する第三復号部と、
を含む、
マッチングシステム。
【請求項２】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置から受信する受信部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、
上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、
上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、
上記他の結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算部と、
上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記他の結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、
上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、
上記ｘ及び上記ｃの組（ｘ，ｃ）を上記他の結合装置に送信する第二送信部と、を含む、
結合装置。
【請求項３】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置に送信する送信部と、
組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記他の結合装置から受信する第一受信部と、
組（ｘ，ｃ）を上記他の結合装置から受信する第二受信部と、
上記他の結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、
上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、
上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、
上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、
上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、
上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、復号関数Ｅ＋*及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号部と、を含む、
結合装置。
【請求項４】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が、上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算ステップと、
上記第一結合装置が、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信ステップと、
上記第一結合装置が、上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化ステップと、
上記第一結合装置が、上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算ステップと、
上記第一結合装置が、上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第二結合装置に送信する第一送信ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算ステップと、
上記第一結合装置が、上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算ステップと、
上記第一結合装置が、上記ｘ及び上記ｃの組（ｘ，ｃ）を上記第二結合装置に送信する第二送信ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算ステップと、
上記第二結合装置が、各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記の暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化ステップと、
上記第二結合装置が、上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信ステップと、
上記第二結合装置が、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第一結合装置から受信する第一受信ステップと、
上記第二結合装置が、組（ｘ，ｃ）を上記第一結合装置から受信する第二受信ステップと、
上記第二結合装置が、上記第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算ステップと、
上記第二結合装置が、上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出ステップと、
上記第二結合装置が、上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算ステップと、
上記第二結合装置が、上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算ステップと、
上記第二結合装置が、上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号ステップと、
上記第二結合装置が、上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号ステップと、
上記第二結合装置が、上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、上記復号関数Ｅ＋*及び上記復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号ステップと、を含む、
マッチングシステムの方法。
【請求項５】
第一結合装置及び第二結合装置を含むマッチングシステムにおいて、
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置は、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、
上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第二結合装置に送信する第二送信部と、
を含み、
上記第二結合装置は、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信部と、
組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第一結合装置から受信する第一受信部と、
組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第一結合装置から受信する第二受信部と、
上記第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、
上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、
を含む、
マッチングシステム。
【請求項６】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置から受信する受信部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記他の結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、
上記第二結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、
上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記他の結合装置に送信する第二送信部と、を含む、
結合装置。
【請求項７】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置に送信する送信部と、
組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記他の結合装置から受信する第一受信部と、
組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記他の結合装置から受信する第二受信部と、
上記他の結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、
上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、を含む、
結合装置。
【請求項８】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
第一結合装置が、上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算ステップと、
上記第一結合装置が、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信ステップと、
上記第一結合装置が、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算ステップと、
上記第一結合装置が、上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化ステップと、
上記第一結合装置が、上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第二結合装置に送信する第二送信ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算ステップと、
上記第二結合装置が、各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化ステップと、
上記第二結合装置が、上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信ステップと、
上記第二結合装置が、組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第一結合装置から受信する第一受信ステップと、
上記第二結合装置が、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第一結合装置から受信する第二受信ステップと、
上記第二結合装置が、上記第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算ステップと、
上記第二結合装置が、上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出ステップと、を含む、
マッチングシステムの方法。
【請求項９】
請求項２，３，６，７の何れかの結合装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
第一結合装置及び第二結合装置を含むマッチングシステムにおいて、
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置は、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、
上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、
上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、
上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算部と、
上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、
上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、
上記ｘ及び上記ｃの組（ｘ，ｃ）を上記第二結合装置に送信する第二送信部と、
を含み、
上記第二結合装置は、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信部と、
組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第一結合装置から受信する第一受信部と、
組（ｘ，ｃ）を上記第一結合装置から受信する第二受信部と、
上記第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、
上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、
上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、
上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、
上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、
上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて上記復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、上記復号関数Ｅ＋*及び復号関数Ｅで復号したｅｘｔ’（ｖ’）を計算する第三復号部と、
を含む、
マッチングシステム。
【請求項２】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置から受信する受信部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算部と、
上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算部と、
上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算部と、
上記他の結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算部と、
上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記他の結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算部と、
上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算部と、
上記ｘ及び上記ｃの組（ｘ，ｃ）を上記他の結合装置に送信する第二送信部と、を含む、
結合装置。
【請求項３】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置に送信する送信部と、
組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記他の結合装置から受信する第一受信部と、
組（ｘ，ｃ）を上記他の結合装置から受信する第二受信部と、
上記他の結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算部と、
上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出部と、
上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算部と、
上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算部と、
上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号部と、
上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号部と、
上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、復号関数Ｅ＋*及び復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号部と、を含む、
結合装置。
【請求項４】
ｆを、逆関数が存在する所定の秘密鍵を用いた可換暗号関数、ｇを所定の鍵生成関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が、上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算する第一ハッシュ値計算ステップと、
上記第一結合装置が、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を第二結合装置から受信する受信ステップと、
上記第一結合装置が、上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したｙを秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｆ（ｅＳ’，ｙ）を計算する第二計算ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）のハッシュ値ｈ’（ｆ（ｅＳ，ｙ））を計算する第二ハッシュ値計算ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）を上記鍵生成関数ｇに入力したときの出力値ｋ’＝ｇ（ｆ（ｅＳ，ｙ））を計算する第三計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化ステップと、
上記第一結合装置が、上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を上記ｋ’を用いて所定の暗号化関数Ｋ’で暗号化したｃ’＝Ｋ’（ｋ’，Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を計算する第四計算ステップと、
上記第一結合装置が、上記ｈ’（ｆ（ｅＳ，ｙ））、上記ｆ（ｅＳ’，ｙ）及び上記ｃ’の組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第二結合装置に送信する第一送信ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第五計算ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳ’を用いた関数ｆに入力したときの出力値ｋ＝ｆ（ｅＳ’，ｈ（ｖ））を計算する第六計算ステップと、
上記第一結合装置が、上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記ｋを用いて所定の暗号化関数Ｋで暗号化したｃ＝Ｋ（ｋ，ｅｘｔ（ｖ））を計算する第七計算ステップと、
上記第一結合装置が、上記ｘ及び上記ｃの組（ｘ，ｃ）を上記第二結合装置に送信する第二送信ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算ステップと、
上記第二結合装置が、各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記の暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化ステップと、
上記第二結合装置が、上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信ステップと、
上記第二結合装置が、組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）を上記第一結合装置から受信する第一受信ステップと、
上記第二結合装置が、組（ｘ，ｃ）を上記第一結合装置から受信する第二受信ステップと、
上記第二結合装置が、上記第一結合装置から受信したｘを用いて、秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）のハッシュ値ｈ’（ｆ（ｅＲ，ｘ））を計算する第二計算ステップと、
上記第二結合装置が、上記ｈ’（ｆ（ｅＲ，ｘ））と、ｈ’（ｆ（ｅＳ，ｙ））とが一致する組（ｈ’（ｆ（ｅＳ，ｙ）），ｆ（ｅＳ’，ｙ），ｃ’）と組（ｘ，ｃ）とのペアを検出する検出ステップと、
上記第二結合装置が、上記検出されたペアを構成するｆ（ｅＲ，ｘ）を上記鍵生成関数ｇに入力したときの出力値ｇ（ｆ（ｅＲ，ｘ））を計算する第三計算ステップと、
上記第二結合装置が、上記秘密鍵ｅＲを用いたｆの逆関数ｆ−１を用いて上記検出されたペアを構成する上記ｆ（ｅＳ’，ｙ）を復号したｆ−１（ｅＲ，ｆ（ｅＳ’，ｙ））＝ｆ（ｅＳ’，ｈ（ｖ’））を計算する第四計算ステップと、
上記第二結合装置が、上記検出されたペアを構成するｃを上記ｆ（ｅＳ’，ｈ（ｖ’））を用いて復号関数Ｋ*により復号したＫ*（ｆ（ｅＳ’，ｈ（ｖ’）），ｃ）＝ｅｘｔ（ｖ）を計算する第一復号ステップと、
上記第二結合装置が、上記検出されたペアを構成するｃ’を上記ｇ（ｆ（ｅＲ，ｘ））を用いて復号関数Ｋ’*により復号したＫ’*（ｇ（ｆ（ｅＲ，ｘ）），ｃ’）＝Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する第二復号ステップと、
上記第二結合装置が、上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））を、上記復号関数Ｅ＋*及び上記復号関数Ｅ*で復号したｅｘｔ’（ｖ’）を計算する第三復号ステップと、を含む、
マッチングシステムの方法。
【請求項５】
第一結合装置及び第二結合装置を含むマッチングシステムにおいて、
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置は、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信部と、
上記第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、
上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、
上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第二結合装置に送信する第二送信部と、
を含み、
上記第二結合装置は、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信部と、
組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第一結合装置から受信する第一受信部と、
組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第一結合装置から受信する第二受信部と、
上記第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、
上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、
を含む、
マッチングシステム。
【請求項６】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算部と、
組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置から受信する受信部と、
上記他の結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算部と、
上記他の結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化部と、
上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信部と、
上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算部と、
上記第二結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化部と、
上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記他の結合装置に送信する第二送信部と、を含む、
結合装置。
【請求項７】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算部と、
各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算部と、
上記第二結合装置が保有するテーブルの各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化部と、
上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を他の結合装置に送信する送信部と、
組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記他の結合装置から受信する第一受信部と、
組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記他の結合装置から受信する第二受信部と、
上記他の結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算部と、
上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出部と、を含む、
結合装置。
【請求項８】
ｆを所定の秘密鍵を用いた可換暗号関数とし、Ｅを所定の暗号化関数として、
第一結合装置が、上記第一結合装置が保有するテーブルの予め定められたキーカラムの各データｖのハッシュ値ｈ（ｖ）を計算するハッシュ値計算ステップと、
上記第一結合装置が、組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第二結合装置から受信する受信ステップと、
上記第一結合装置が、第二結合装置から受信したｙを秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｆ（ｅＳ，ｙ）を計算する第一計算ステップと、
上記第一結合装置が、上記第二結合装置から受信したＥ（ｅｘｔ’（ｖ’））を所定の再暗号化関数Ｅ＋で暗号化したＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を計算する再暗号化ステップと、
上記第一結合装置が、上記ｆ（ｅＳ，ｙ）及び上記Ｅ＋（Ｅ（ｅｘｔ’（ｖ’）））の組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第二結合装置に送信する第一送信ステップと、
上記第一結合装置が、上記ｈ（ｖ）を秘密鍵ｅＳを用いた関数ｆに入力したときの出力値ｘ＝ｆ（ｅＳ，ｈ（ｖ））を計算する第二計算ステップと、
上記第一結合装置が、上記第一結合装置が保有するテーブルの各上記データｖを含むタプルの全部又は一部のデータｅｘｔ（ｖ）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ（ｖ））を計算する暗号化ステップと、
上記第一結合装置が、上記ｘ及び上記Ｅ（ｅｘｔ（ｖ））の組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第二結合装置に送信する第二送信ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの予め定められたキーカラムの各データｖ’のハッシュ値ｈ（ｖ’）を計算するハッシュ値計算ステップと、
上記第二結合装置が、上記第二結合装置が保有するテーブルの各上記ハッシュ値ｈ（ｖ’）を秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｙ＝ｆ（ｅＲ，ｈ（ｖ’））を計算する第一計算ステップと、
上記第二結合装置が、各上記データｖ’を含むタプルの全部又は一部のデータｅｘｔ’（ｖ’）を上記暗号化関数Ｅで暗号化したＥ（ｅｘｔ’（ｖ’））を計算する暗号化ステップと、
上記第二結合装置が、上記ｙ及び上記Ｅ（ｅｘｔ’（ｖ’））の組（ｙ，Ｅ（ｅｘｔ’（ｖ’）））を上記第一結合装置に送信する送信ステップと、
上記第二結合装置が、組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））を上記第一結合装置から受信する第一受信ステップと、
上記第二結合装置が、組（ｘ，Ｅ（ｅｘｔ（ｖ）））を上記第一結合装置から受信する第二受信ステップと、
上記第二結合装置が、上記第一結合装置から受信したｘを秘密鍵ｅＲを用いた関数ｆに入力したときの出力値ｆ（ｅＲ，ｘ）を計算する第二計算ステップと、
上記第二結合装置が、上記ｆ（ｅＲ，ｘ）と、ｆ（ｅＳ，ｙ）とが一致する組（ｆ（ｅＳ，ｙ），Ｅ＋（Ｅ（ｅｘｔ’（ｖ’））））と組（ｘ，Ｅ（ｅｘｔ（ｖ）））とのペアを検出して、検出されたペアを構成するＥ（ｅｘｔ（ｖ））及びＥ＋（Ｅ（ｅｘｔ’（ｖ’）））を出力する検出ステップと、を含む、
マッチングシステムの方法。
【請求項９】
請求項２，３，６，７の何れかの結合装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１５０２７６（Ｐ２０１２−１５０２７６Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１１−８８２１（Ｐ２０１１−８８２１）
【出願日】平成２３年１月１９日（２０１１．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２３年１月１９日（２０１１．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]