"nを2以上の整数、kを1以上n以下の整数として、i=1,...,k-1,k1,...,nとし、第iテーブルの予め定められたキーカラムViのデータをvとし、tを所定の数として、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算する第i結合装置と、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとして、キーカラムVkの各データvについて、上記Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivri=Σi∈{1,2,...,n}-{k}Eai,jvjriを計算し、d=Eextkvを計算し、上記cとdとの組d,cを生成する関数値計算部と、上記複数の組d,cを再暗号化して置換πにより置換した複数の組d’π,c’πを生成する第一ミックスネット演算部と、E’を準同型性を持つ暗号関数として、上記複数の組d’π,c’πのそれぞれについて、c’πの復号結果cπ=0である場合にはb=1とし、c’πの復号結果cπ=0でない場合にはb=0として、そのc’πの組d’π,c’πのd’πとE’bπとの組d’π,E’bπを生成するフラグ付与部と、上記複数の組d’π,E’bπを再暗号化して上記置換πの逆置換により置換した複数の組dj’’,E’’bjj=1,2,...,Jkを生成する第二ミックスネット演算部と、上記複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成する順序付与部と、上記複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成する第三ミックスネット演算部と、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成する順序復号部と、上記順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力する並替部と、を含むマッチングシステム。nを3以上の整数、kを1以上n以下の整数として、i=1,...,k-1,k1,...,nとし、第iテーブルの予め定められたキーカラムViのデータをvとし、tを所定の数として、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算する第i結合装置と、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとし、をビット結合とし、extkvに対応するビット列を検査符号tkvとして,キーカラムVkの各データvについて、上記Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivriextkvtkv=Σi∈{1,2,...,n}-{k}Eai,jvjriEextkvtkvを計算する関数値計算部と、所定の順序で並んだ上記複数のcを置換πにより置換した複数のcπを生成する第一ミックスネット演算部と、各上記cπの復号結果のビット列のうちtkvに対応するビット列が上記tkvと一致する場合にはそのcπの復号結果=extkvであり、一致しない場合にはそのcπの復号結果=extkvでないと判断する判定部と、E’を準同型性を持つ暗号関数として、上記複数のcπのそれぞれについて、cπの復号結果=extkvであると判定された場合にはb=1とし、cπの復号結果=extkvでないと判定された場合にはb=0として、そのcπに対応するE’bπとdπ’=Eextkvの組d’π,E’bπを生成するフラグ付与部と、上記複数の組d’π,E’bπを再暗号化して上記置換πの逆置換により置換した複数の組dj’’,E’’bjj=1,2,...,Jkを生成する第二ミックスネット演算部と、上記複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成する順序付与部と、上記複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成する第三ミックスネット演算部と、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成する順序復号部と、上記順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力する並替部と、を含むマッチングシステム。nを2以上の整数、kを1以上n以下の整数として、i=1,...,k-1,k1,...,nとし、第iテーブルの予め定められたキーカラムViのデータをvとし、tを所定の数として、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算する第i結合ステップと、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとして、キーカラムVkの各データvについて、上記Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivri=Σi∈{1,2,...,n}-{k}Eai,jvjriを計算し、d=Eextkvを計算し、上記cとdとの組d,cを生成する関数値計算ステップと、上記複数の組d,cを再暗号化して置換πにより置換した複数の組d’π,c’πを生成する第一ミックスネット演算ステップと、E’を準同型性を持つ暗号関数として、上記複数の組d’π,c’πのそれぞれについて、c’πの復号結果cπ=0である場合にはb=1とし、c’πの復号結果cπ=0でない場合にはb=0として、そのc’πの組d’π,c’πのd’πとE’bπとの組d’π,E’bπを生成するフラグ付与ステップと、上記複数の組d’π,E’bπを再暗号化して上記置換πの逆置換により置換した複数の組dj’’,E’’bjj=1,2,...,Jkを生成する第二ミックスネット演算ステップと、上記複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成する順序付与ステップと、上記複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成する第三ミックスネット演算ステップと、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成する順序復号ステップと、上記順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力する並替ステップと、を含むマッチングシステムの方法。nを3以上の整数、kを1以上n以下の整数として、i=1,...,k-1,k1,...,nとし、第iテーブルの予め定められたキーカラムViのデータをvとし、tを所定の数として、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算する第i結合ステップと、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとし、をビット結合とし、extkvに対応するビット列を検査符号tkvとして,キーカラムVkの各データvについて、上記Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivriextkvtkv=Σi∈{1,2,...,n}-{k}Eai,jvjriEextkvtkvを計算する関数値計算ステップと、所定の順序で並んだ上記複数のcを置換πにより置換した複数のcπを生成する第一ミックスネット演算ステップと、各上記cπの復号結果のビット列のうちtkvに対応するビット列が上記tkvと一致する場合にはそのcπの復号結果=extkvであり、一致しない場合にはそのcπの復号結果=extkvでないと判断する判定ステップと、E’を準同型性を持つ暗号関数として、上記複数のcπのそれぞれについて、cπの復号結果=extkvであると判定された場合にはb=1とし、cπの復号結果=extkvでないと判定された場合にはb=0として、そのcπに対応するE’bπとdπ’=Eextkvの組d’π,E’bπを生成するフラグ付与ステップと、上記複数の組d’π,E’bπを再暗号化して上記置換πの逆置換により置換した複数の組dj’’,E’’bjj=1,2,...,Jkを生成する第二ミックスネット演算ステップと、上記複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成する順序付与ステップと、上記複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成する第三ミックスネット演算ステップと、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成する順序復号ステップと、上記順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力する並替ステップと、を含むマッチングシステムの方法。請求項1又は請求項2のマッチングシステムの第i結合装置である結合装置。請求項5の結合装置の各部としてコンピュータを機能させるためのプログラム。しかしながら、非特許文献1の技術では、キーカラムの一致するデータを含むタプルのデータを結合したデータのみならず、キーカラムの一致するデータ自体が分かってしまう。図6の例では、データ014及び034において、一致するということが分かってしまう。この発明は、キーカラムの一致するデータの情報を秘匿化したマッチングシステム、方法、結合装置及びプログラムを提供することを目的とする。この発明の第一の態様であるマッチングシステムは、nを2以上の整数、kを1以上n以下の整数として、i=1,...,k-1,k1,...,nとし、第iテーブルの予め定められたキーカラムViのデータをvとし、tを所定の数として、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算する第i結合装置と、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとして、キーカラムVkの各データvについて、Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivri=Σi∈{1,2,...,n}-{k}Eai,jvjriを計算し、d=Eextkvを計算し、cとdとの組d,cを生成する関数値計算部と、複数の組d,cを再暗号化して置換πにより置換した複数の組d’π,c’πを生成する第一ミックスネット演算部と、E’を準同型性を持つ暗号関数として、複数の組d’π,c’πのそれぞれについて、c’πの復号結果cπ=0である場合にはb=1とし、c’πの復号結果cπ=0でない場合にはb=0として、そのc’πの組d’π,c’πのd’πとE’bπとの組d’π,E’bπを生成するフラグ付与部と、複数の組d’π,E’bπを再暗号化して置換πの逆置換により置換した複数の組dj’’,E’’bjj=1,2,...,Jkを生成する第二ミックスネット演算部と、複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成する順序付与部と、複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成する第三ミックスネット演算部と、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成する順序復号部と、順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力する並替部と、を含む。キーカラムの一致するデータの情報を秘匿化することができる。以下、図面を参照してこの発明の実施形態を説明する。[第一実施形態]第一実施形態のマッチングシステムは、図1に示すように、第1結合装置1、第2結合装置2、...、第k結合装置k、...、第n結合装置n、テーブル記憶部11,21,...,k1,n1、第一ミックスネット演算部a,フラグ付与部b、第二ミックスネット演算部c、順序付与部d、第三ミックスネット演算部e、順序復号部f、並替部g、制御部iを例えば備える。nは2以上の整数である。第1結合装置1は、第1テーブルT1を保有する。第1テーブルT1はテーブル記憶部11に記憶されている。同様にして、i=2,3,...,nとして、第i結合装置iは、第iテーブルTiを保有する。第iテーブルTiはテーブル記憶部i1に記憶されている。各テーブルTiは、カラム列及びタプル行で構成される。マッチングシステムは、すべてのテーブルTii=1,2,...,nの所定のカラムにおいて一致するデータを特定し、その一致するデータv以下、一致データvと呼ぶ。を含むタプルの全部又は一部のデータextkvを結合したデータを取得する。一致するデータを特定する対象となるカラムをキーカラムと呼ぶことにする。各テーブルTiのキーカラムViは予め定められているものとする。制御部iは、kを1からnまでの何れかの数であって、まだ設定されていない数に設定するステップS1。例えば、k=1とする。以下のステップS2からステップS10の処理により、所定の順序で並んだ、テーブルTkの一致データvを含むタプルの全部又は一部のデータextkvを取得することができる。制御部iがkを異なる値に順次変えてステップS2からステップS10の処理を繰り返すことにより、各テーブルTkk=1,2,...,nの一致データvを含むタプルの全部又は一部のデータextkvを取得することができる。各kに対応して求まったデータは、共通する所定の順序、例えば一致データvの辞書順で並んでいる。したがって、同一の順序のvのextkvk=1,2,...,nの集合を取得することにより、同一の一致データvについてのextkvの集合、すなわちext1v,ext2v,...,extnvを取得することができる。i=1,...,k-1,k1,...,nとして、各第i結合装置は、fix=tΠv∈Vix-v=Σj=0Ji-1ai,jxjで定義される多項式fixの各係数ai,jを準同型性を持つ暗号関数Eで暗号化したEai,jを計算するステップS2。ここで、tは所定の数である。tは、例えば1であってもよいし、乱数であってもよい。Jiは、キーカラムViを構成するデータvの数である。上記の多項式fixの式の中の下付きのViは、キーカラムViを意味する。Eai,jは、第一ミックスネット演算部aに送信される。関数値計算部hは、キーカラムVkの各データvについて、上記Eai,jを用いて、c=EΣi∈{1,2,...,n}-{k}fivri=Σi∈{1,2,...,n}-{k}Eai,jvjriを計算し、d=Eextkvを計算し、上記cとdとの組d,cを生成するステップS3。riは、整数の乱数である。extkvは、キーカラムVkのデータvを含むタプルの全部又は一部のデータである。キーカラムVkのデータvの数をJk個とすると、Jk個の組d,cが生成される。生成された組d,cは、第一ミックスネット演算部aに所定の順序で送信される。所定の順序とは、例えば辞書順である。以下、単に所定の順序といった場合には、この所定の順序を意味する。暗号関数Eは準同型性の性質を持つため、加法的に記載すれば、Eαβ=Eββ...β=EβEβ...Eβ=αEβとなる。このため、EΣi∈{1,2,...,n}-{k}fivri=Σi∈{1,2,...,n}-{k}Eai,jvjriとなるのである。関数値計算部hは、図1に示すように第k結合装置kの中に設けられている。このため、ステップS1の処理において、第1結合装置1から第n結合装置nで第k結合装置kとして選択される可能性がある結合装置は、関数計算部hを備えていることになる。なお、関数値計算部hは、第k結合装置kの外部に設けられていてもよい。第一ミックスネット演算部aは、複数の組d,cを再暗号化して置換πにより置換した複数の組d’π,c’πを生成するステップS4。置換πは位数Jkの対称群の元である。複数の組d’π,c’πは、フラグ付与部bに送信される。複数の組d,cの数がJkあるため、組d’π,c’πの数もJkである。例えば組d,cの数が3つであり、それぞれ組d1,c1、組d2,c2及び組d3,c3であるとする。このとき、これらの3つの組d,cのそれぞれを暗号化して、組d1’,c1’、組d2’,c2’及び組d3’,c3’とする。置換π:{1,2,3}→{1,2,3}は1をπ1に写し、2をπ2に写し、3をπ3に写す全単射の写像であり、例えばπ1=2、π2=3、π3=1であるとする。この場合、これらの組d1’,c1’、組d2’,c2’及び組d3’,c3’を置換πで置換すると、組dπ3’,cπ3’、組dπ1’,cπ1’及び組dπ2’,cπ2’となる。フラグ付与部bは、複数の組d’π,c’πのそれぞれについて、c’πの復号結果cπ=0である場合にはb=1とし、c’πの復号結果cπ=0でない場合にはb=0として、そのc’πの組d’π,c’πのd’πとE’bπとの組d’π,E’bπを生成するステップS5。複数の組d’π,c’πの数がJkであるため、組d’π,E’bπの数もJk個となる。生成された複数の組d’π,E’bπは、第二ミックスネット演算部cに送信される。vが一致データvである場合にはcπ=0となりb=1となり、vが一致データvでない場合にはcπ≠0の場合にはb=0となる。c’πの復号は、図1に例示するフラグ付与部bの復号部b1により行われる。また、bの暗号化は、フラグ付与部bの暗号化部b2により行われる。E’は、準同型性を持つ暗号関数である。第一ミックスネット演算部aによるミックスネットの処理で、置換πに基づいて複数の組d,cの順序が入れ替わるため、置換πを知らないフラグ付与部bは、任意の組d’π,c’πが一致データvに対応するかどうかを知ることができるが、その組d’π,c’πがどのデータvに対応するものであるのかを知ることができない。このように、組d’π,c’πとデータvとの対応関係をフラグ付与部bに秘匿化するために、第一ミックスネット演算部aによるミックスネットの処理を行っている。なお、第一ミックスネット演算部aによるミックスネットの処理で入れ替わった複数の組d,c及び複数の組d’π,E’bπの順番は、以下の第二ミックスネット演算部bによるミックスネットの処理で元の順番、すなわち関数値計算部hのステップS3の処理で説明をした所定の順番に戻る。第二ミックスネット演算部cは、複数の組d’π,E’bπを再暗号化して置換πの逆置換π-1により置換した複数の組dj’’,E’’bjj=1,...,Jkを生成するステップS6。組d’π,E’bπの数がJk個とであるため、組dj’’,E’’bjの数もJk個となる。組dj’’,E’’bjは、所定の順序におけるj番目の組d’’,E’’bを意味する。生成された複数の組dj’’,E’’bjは、順序付与部dに送信される。ある値xについてのExの再暗号化により生成されたE’’xは、その値xを暗号関数E’’に入力したときの出力値と見ることができる。この場合の暗号関数E’’は、準同型性を持つとする。置換πの逆置換π-1は、ππ-1が恒等置換となるような置換のことである。例えば、置換π:{1,2,3}→{1,2,3}を1をπ1に写し、2をπ2に写し、3をπ3に写す全単射の写像であり、π1=2、π2=3、π3=1であるとした場合の逆置換π-1:{1,2,3}→{1,2,3}は、1をπ-11に写し、2をπ-12に写し、3をπ-13に写す全単射の写像であり、π-11=2、π-12=1、π-13=2である。順序付与部dは、複数の組dj’’,E’’bjのそれぞれについて、E’’bjを用いて、順序ej’’=E’’Σk=1jbk=Σk=1jE’’bkを計算して、計算された順序ej’’を組dj’’,E’’bjに追加した組dj’’,E’’bj,ej’’を生成するステップS7。組dj’’,E’’bjの数がJkであるため、組dj’’,E’’bj,ej’’の数もJkとなる。先に述べたように、vが一致データvである場合にはcπ=0となりb=1となり、vが一致データvでない場合にはcπ≠0の場合にはb=0となる。このため、順序ej’’は、一致データvを所定の順序で並べたときの順序を暗号関数E’’で暗号化したものとなる。第三ミックスネット演算部eは、複数の組dj’’,E’’bj,ej’’を再暗号化して置換πにより置換した複数の組dπj’’’,E’’’bπj,eπj’’’を生成するステップS8。置換πは、位数Jkの対称群の元である。複数の組dπj’’’,E’’’bπj,eπj’’’は、順序復号部fに送信される。複数の組dj’’,E’’bj,ej’’の数がJkであるため、組dπj’’’,E’’’bπj,eπj’’’の数もJkである。第三ミックスネット演算部eによるミックスネットの処理で、置換πに基づいて複数の組dj’’,E’’bj,ej’’の順番が入れ替わる。これにより、置換πを知らない順序復号部fは、任意の組dπj’’’,E’’’bπj,eπj’’’が所定の順序における何番目の一致データvかを知ることができるが、その組dπj’’’,E’’’bπj,eπj’’’がどのデータvに対応するものなのかを知ることはできない。このように、組dπj’’’,E’’’bπj,eπj’’’とデータvとの対応関係を順序復号部fに秘匿化するために、第三ミックスネット演算部eによるミックスネットの処理を行っている。順序復号部fは、E’’’bπjを復号したbπj=1となる組dπj’’’,E’’’bπj,eπj’’’のeπj’’’を復号して順序eπjを生成するステップS9。生成された順序eπj及び順序eπjに対応するdπj’’’は、並替部gに送信される。並替部gは、順序eπjで組dπj’’’,E’’’bπj,eπj’’’のdπj’’’を出力するステップS10。このdπj’’’が、一致データvのを含むタプルの全部又は一部のデータextkvに対応する。一致データvの個数だけdπj’’’が出力される。制御部iは、1からnまでのすべての整数がkに設定されたかどうか判定するステップS11。設定されていない場合には、ステップS1に戻り、制御部iは、1からnまでの何れかの数であってまだ設定されていない数をkに設定する。1からnまでのすべての整数がkに設定されたたと判定された場合には、マッチングシステムの処理を終了する。このようにして、ステップS2からステップS10の処理を繰り返すことにより、各テーブルTkk=1,2,...,nの一致データvを含むタプルの全部又は一部のデータextkvを取得することができる。[第二実施形態]第二実施形態のマッチングシステム及び方法は、関数値計算部h、第一ミックスネット演算部a、フラグ付与部bにおいて第一実施形態のマッチングシステム及び方法と異なる。以下、第一実施形態と異なる部分を中心に説明する。同様の部分については説明を省略する。第二実施形態の関数値計算部hは、riを整数の乱数とし、第kテーブルの予め定められたキーカラムVkのデータvを含むタプルの全部又は一部のデータをextkvとし、extkvに対応するビット列を検査符号tkvとして,キーカラムVkの各データvについて、Eai,jを用いて、c=EΣi∈{1,2,...,n-1}-{k}fivriextkvtkv=Σi∈{1,2,...,n-1}-{k}Eai,jvjriEextkvtkvを計算するステップS3。第一実施形態とは、cの定義が異なる。また、第一実施形態では組d,cが送信されるのに対して、第二実施形態ではcだけが第一ミックスネット演算部aに所定の順序で送信される。ここで、はビット結合を表わす。検査符号tkvは、extkvに対応するビット列である。例えば、検査符号tkvは、vに依存しない00...0等の一定のビット列であってもよいし、vに依存するビット列、例えばextkvのハッシュ値であってもよい。第一ミックスネット演算部aは、所定の順序で並んだ複数のcを置換πにより置換した複数のcπを生成する。順序が並び替えられた複数のcπは、フラグ付与部bに送信される。フラグ付与部b3は、E’を準同型性を持つ暗号関数として、複数のcπのそれぞれについて、cπの復号結果=extkvであると判定された場合にはb=1とし、cπの復号結果=extkvでないと判定された場合にはb=0として、そのcπに対応するE’bπとdπ’=Eextkvの組d’π,E’bπを生成するフラグ付与部と、c’πの復号は、図1に例示するフラグ付与部bの復号部b1により行われる。また、bの暗号化は、フラグ付与部bの暗号化部b2により行われる。さらに、cπの復号結果=extkvであるかどうかの判断は、判定部b3により行われる。判定部b3は、復号部b1によるcπの復号結果のビット列のうちtkvに対応するビット列が、関数値計算部hがビット結合したtkvと一致する場合にはそのcπの復号結果=extkvであり、一致しない場合にはそのcπの復号結果=extkvでないと判断する。cπの復号結果=extkvでない場合には、cπの復号結果のビット列のうちtkvに対応するビット列は、関数値計算部hがextkvに対してビット結合したtkvと一致しない可能性が非常に高い。このため、復号部b1によるcπの復号結果のビット列のうちtkvに対応するビット列が、関数値計算部hがビット結合したtkvと一致する場合にはそのcπの復号結果=extkvと判断できるのである。フラグ付与部bは、上記の一致の判定をする必要があるため、検査符号tkvについての情報を事前に知っているとする。検査符号tkvがvに依存するビット列である場合には、フラグ付与部bは置換πについての情報を知っており、cπに対応する検査符号tkvをわかっているものとする。このように、フラグ付与部bが検査符号tkvを用いてcπの復号結果=extkvであるかを判定可能とすることにより、フラグ付与部bに対してextkvを秘匿化することができる。他の処理は第一実施形態と同様である。[変形例等]暗号関数E,E’,E’’E’’’は、準同型性の性質を持つ確率暗号であってもよい。これにより、安全性が増す。第一ミックスネット演算部aは、図2に例示するように、第1結合装置1に設けられた第一ミックスネット構成部a1、第2結合装置2に設けられた第一ミックスネット演算部a2、...、第k結合装置kに設けられた第一ミックスネット構成部ak、...、第n結合装置nに設けられた第一ミックスネット構成部anにより構成されてもよい。この場合、これらのn個の第一ミックスネット構成部aii=1,2,...,nが共同して処理を行うことにより、第一ミックスネット演算部aの処理を実現する。例えば、再暗号化関数が多重暗号又は閾値関数であるとして、順次i=k1,k2,...,n,1,2,...,k-1として、第一ミックスネット構成部aiが、複数の組d,cを再暗号化して予め定められた順序で入れ替えて、第一ミックスネット構成部ai1i=nである場合には、第一ミックスネット構成部a1に送信する。また、この際に、各第一ミックスネット構成部aii=1,2,...,nが、dのみを再暗号化して、cについては部分的な復号を行ってもよい。各第一ミックスネット構成部aii=1,2,...,nがcについての部分的な復号を行うことにより、cが復元される。すなわち、第一ミックスネット構成部aii=1,2,...,nにより構成される第一ミックスネット演算部aが、ミックスネットの処理と同時に、復号部b1の処理を行ってもよい。同様にして、第二ミックスネット構成部cが、図4に例示するように、第1結合装置1に設けられた第二ミックスネット構成部c1、第2結合装置2に設けられた第二ミックスネット演算部c2、...、第k結合装置kに設けられた第二ミックスネット構成部ck、...、第n結合装置nに設けられた第二ミックスネット構成部cnにより構成されてもよい。この場合、順次i=k-1,k-2,...,1,n,n-1,...,k1として、第二ミックスネット構成部ciが、複数の組d’π,E’bπを再暗号化して予め定められた順序で入れ替えて、第二ミックスネット構成部ai1i=nである場合には、第一ミックスネット構成部a1に送信する。同様にして、第三ミックスネット構成部eが、図5に例示するように、第1結合装置1に設けられた第三ミックスネット構成部e1、第2結合装置2に設けられた第三ミックスネット演算部e2、...、第k結合装置kに設けられた第三ミックスネット構成部ek、...、第n結合装置nに設けられた第三ミックスネット構成部enにより構成されてもよい。また、この際に、各第三ミックスネット構成部eii=1,2,...,nが、dj’’及びej’’を再暗号化して、E’’bjについては部分的な復号を行ってもよい。各第三ミックスネット構成部eii=1,2,...,nがE’’bjについての部分的な復号を行うことにより、bπjが復元される。すなわち、第三ミックスネット構成部eii=1,2,...,nにより構成される第三ミックスネット演算部eが、ミックスネットの処理と同時に、E’’’bπjの復号を行ってもよい。マッチングシステムは、並替部gにより出力されたdπj’’’を復号して、extkvを生成する最終復号部を有していてもよい。なお、上記の実施形態では、マッチングシステムの各部間でデータは直接送受信されていたが、データは図示されていない記憶部を介してやり取りされてもよい。第i結合装置ii=1,2,...,nをコンピュータによって実現する場合、第i結合装置iの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第i結合装置iの各部の処理機能がコンピュータ上で実現される。これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。"