マッチングシステム、マッチングシステムの方法、結合装置及びプログラム
【課題】ｎ個のテーブル記憶部に記録されたデータに対して、一致するキーカラムを秘匿化しつつキーカラムが一致するデータのタプルを結合したデータを出力するマッチング技術を提供する。
【解決手段】すべてのｋ（ｋ＝１，２，…，ｎ）について、一致データｖ＊を含むタプルの全部または一部のデータｅｘｔｋ（ｖ＊）を所定の順序で取得した後に、同一の順序のｖ＊のｅｘｔｋ（ｖ＊）（ｋ＝１，２，…，ｎ）の集合を取得する。この値および所定の多項式の各係数に対して、準同型性を持つ暗号関数による暗号化と置換を含むミックスネットの処理と所定の順序による並び替えを行い、キーカラムが一致するデータのタプルを結合したデータを出力する。
【解決手段】すべてのｋ（ｋ＝１，２，…，ｎ）について、一致データｖ＊を含むタプルの全部または一部のデータｅｘｔｋ（ｖ＊）を所定の順序で取得した後に、同一の順序のｖ＊のｅｘｔｋ（ｖ＊）（ｋ＝１，２，…，ｎ）の集合を取得する。この値および所定の多項式の各係数に対して、準同型性を持つ暗号関数による暗号化と置換を含むミックスネットの処理と所定の順序による並び替えを行い、キーカラムが一致するデータのタプルを結合したデータを出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の表形式のデータについて非開示のまま必要なデータを結合する技術に関する。
【背景技術】
【０００２】
非特許文献１に、複数の表形式のデータについて非開示のまま必要なデータを結合する技術が記載されている。以下、非特許文献１に記載された技術でできることを簡単に説明する（例えば、非特許文献１参照。）。
【０００３】
図６に示すように、第１テーブル及び第２テーブルがあるとする。非特許文献１の技術により、第１テーブルのキーカラムのデータと、第２テーブルのキーカラムのデータとで一致するものを特定し、その一致するデータを含むタプル（行）のデータを結合して取得することができる。
【０００４】
図６の例だと、第１テーブルのキーカラム及び第２テーブルのキーカラムは、０１４及び０３４のデータが共に含む。したがって、取得することができる結合データは、データ０１４と第１テーブルの０１４のデータを含むタプルのデータｘｘｘと第２テーブルの０１４のデータを含むタプルのデータｂｂｂとを結合したデータ、及び、データ０３４と第１テーブルの０３４のデータを含むタプルのデータｚｚｚと第２テーブルの０３４のデータを含むタプルのデータｃｃｃとを結合したデータとなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R.Agrawal, A.V.Evfimievski, and R.Srikant, “Information Sharing Across Private Databases”, ACM SIGMOD 2003, pp.86-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１の技術では、キーカラムの一致するデータを含むタプルのデータを結合したデータのみならず、キーカラムの一致するデータ自体が分かってしまう。図６の例では、データ０１４及び０３４において、一致するということが分かってしまう。
【０００７】
この発明は、キーカラムの一致するデータの情報を秘匿化したマッチングシステム、方法、結合装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
この発明の第一の態様であるマッチングシステムは、ｎを２以上の整数、ｋを１以上ｎ以下の整数として、ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、ｃとｄとの組（ｄ，ｃ）を生成する関数値計算部と、複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算部と、Ｅ’を準同型性を持つ暗号関数として、複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、を含む。
【発明の効果】
【０００９】
キーカラムの一致するデータの情報を秘匿化することができる。
【図面の簡単な説明】
【００１０】
【図１】マッチングシステムの例を説明するためのブロック図。
【図２】第一ミックスネット演算部の変形例を説明するためのブロック図。
【図３】第二ミックスネット演算部の変形例を説明するためのブロック図。
【図４】第三ミックスネット演算部の変形例を説明するためのブロック図。
【図５】マッチングシステムの方法の例を説明するためのプログラム。
【図６】従来のマッチングシステムの概要を説明するための図。
【発明を実施するための形態】
【００１１】
以下、図面を参照してこの発明の実施形態を説明する。
【００１２】
［第一実施形態］
第一実施形態のマッチングシステムは、図１に示すように、第１結合装置１、第２結合装置２、…、第ｋ結合装置ｋ、…、第ｎ結合装置ｎ、テーブル記憶部１１，２１，…，ｋ１，ｎ１、第一ミックスネット演算部ａ，フラグ付与部ｂ、第二ミックスネット演算部ｃ、順序付与部ｄ、第三ミックスネット演算部ｅ、順序復号部ｆ、並替部ｇ、制御部ｉを例えば備える。ｎは２以上の整数である。
【００１３】
第１結合装置１は、第１テーブルＴ１を保有する。第１テーブルＴ１はテーブル記憶部１１に記憶されている。同様にして、ｉ＝２，３，…，ｎとして、第ｉ結合装置ｉは、第ｉテーブルＴｉを保有する。第ｉテーブルＴｉはテーブル記憶部ｉ１に記憶されている。
【００１４】
各テーブルＴｉは、カラム（列）及びタプル（行）で構成される。マッチングシステムは、すべてのテーブルＴｉ（ｉ＝１，２，…，ｎ）の所定のカラムにおいて一致するデータを特定し、その一致するデータｖ＊（以下、一致データｖ＊と呼ぶ。）を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を結合したデータを取得する。一致するデータを特定する対象となるカラムをキーカラムと呼ぶことにする。各テーブルＴｉのキーカラムＶｉは予め定められているものとする。
【００１５】
制御部ｉは、ｋを１からｎまでの何れかの数であって、まだ設定されていない数に設定する（ステップＳ１）。例えば、ｋ＝１とする。
【００１６】
以下のステップＳ２からステップＳ１０の処理により、所定の順序で並んだ、テーブルＴｋの一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。制御部ｉがｋを異なる値に順次変えてステップＳ２からステップＳ１０の処理を繰り返すことにより、各テーブルＴｋ（ｋ＝１，２，…，ｎ）の一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。各ｋに対応して求まったデータは、共通する所定の順序、例えば一致データｖ＊の辞書順で並んでいる。したがって、同一の順序のｖ＊のｅｘｔｋ（ｖ＊）（ｋ＝１，２，…，ｎ）の集合を取得することにより、同一の一致データｖ＊についてのｅｘｔｋ（ｖ＊）の集合、すなわち（ｅｘｔ１（ｖ＊），ｅｘｔ２（ｖ＊），…，ｅｘｔｎ（ｖ＊））を取得することができる。
【００１７】
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとして、各第ｉ結合装置は、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する（ステップＳ２）。
【００１８】
ここで、ｔは所定の数である。ｔは、例えば１であってもよいし、乱数であってもよい。Ｊｉは、キーカラムＶｉを構成するデータｖの数である。上記の多項式ｆｉ（ｘ）の式の中の下付きのＶｉは、キーカラムＶｉを意味する。Ｅ（ａｉ，ｊ）は、第一ミックスネット演算部ａに送信される。
【００１９】
関数値計算部ｈは、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する（ステップＳ３）。ｒｉは、整数の乱数である。ｅｘｔｋ（ｖ）は、キーカラムＶｋのデータｖを含むタプルの全部又は一部のデータである。キーカラムＶｋのデータｖの数をＪｋ個とすると、Ｊｋ個の組（ｄ，ｃ）が生成される。生成された組（ｄ，ｃ）は、第一ミックスネット演算部ａに所定の順序で送信される。所定の順序とは、例えば辞書順である。以下、単に所定の順序といった場合には、この所定の順序を意味する。
【００２０】
暗号関数Ｅは準同型性の性質を持つため、加法的に記載すれば、Ｅ（αβ）＝Ｅ（β＋β＋…＋β）＝Ｅ（β）＋Ｅ（β）＋…＋Ｅ（β）＝αＥ（β）となる。このため、Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉとなるのである。
【００２１】
関数値計算部ｈは、図１に示すように第ｋ結合装置ｋの中に設けられている。このため、ステップＳ１の処理において、第１結合装置１から第ｎ結合装置ｎで第ｋ結合装置ｋとして選択される可能性がある結合装置は、関数計算部ｈを備えていることになる。なお、関数値計算部ｈは、第ｋ結合装置ｋの外部に設けられていてもよい。
【００２２】
第一ミックスネット演算部ａは、複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する（ステップＳ４）。置換πは位数Ｊｋの対称群の元である。複数の組（ｄ’π，ｃ’π）は、フラグ付与部ｂに送信される。複数の組（ｄ，ｃ）の数がＪｋあるため、組（ｄ’π，ｃ’π）の数もＪｋである。
【００２３】
例えば組（ｄ，ｃ）の数が３つであり、それぞれ組（ｄ１，ｃ１）、組（ｄ２，ｃ２）及び組（ｄ３，ｃ３）であるとする。このとき、これらの３つの組（ｄ，ｃ）のそれぞれを暗号化して、組（ｄ１’，ｃ１’）、組（ｄ２’，ｃ２’）及び組（ｄ３’，ｃ３’）とする。置換π：｛１，２，３｝→｛１，２，３｝は１をπ（１）に写し、２をπ（２）に写し、３をπ（３）に写す全単射の写像であり、例えばπ（１）＝２、π（２）＝３、π（３）＝１であるとする。この場合、これらの組（ｄ１’，ｃ１’）、組（ｄ２’，ｃ２’）及び組（ｄ３’，ｃ３’）を置換πで置換すると、組（ｄπ（３）’，ｃπ（３）’）、組（ｄπ（１）’，ｃπ（１）’）及び組（ｄπ（２）’，ｃπ（２）’）となる。
【００２４】
フラグ付与部ｂは、複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成する（ステップＳ５）。複数の組（ｄ’π，ｃ’π）の数がＪｋであるため、組（ｄ’π，Ｅ’（ｂ）π）の数もＪｋ個となる。生成された複数の組（ｄ’π，Ｅ’（ｂ）π）は、第二ミックスネット演算部ｃに送信される。
【００２５】
ｖが一致データｖ＊である場合にはｃπ＝０となりｂ＝１となり、ｖが一致データｖ＊でない場合にはｃπ≠０の場合にはｂ＝０となる。
【００２６】
ｃ’πの復号は、図１に例示するフラグ付与部ｂの復号部ｂ１により行われる。また、ｂの暗号化は、フラグ付与部ｂの暗号化部ｂ２により行われる。Ｅ’は、準同型性を持つ暗号関数である。
【００２７】
第一ミックスネット演算部ａによるミックスネットの処理で、置換πに基づいて複数の組（ｄ，ｃ）の順序が入れ替わるため、置換πを知らないフラグ付与部ｂは、任意の組（ｄ’π，ｃ’π）が一致データｖ＊に対応するかどうかを知ることができるが、その組（ｄ’π，ｃ’π）がどのデータｖに対応するものであるのかを知ることができない。このように、組（ｄ’π，ｃ’π）とデータｖとの対応関係をフラグ付与部ｂに秘匿化するために、第一ミックスネット演算部ａによるミックスネットの処理を行っている。なお、第一ミックスネット演算部ａによるミックスネットの処理で入れ替わった複数の組（ｄ，ｃ）及び複数の組（ｄ’π，Ｅ’（ｂ）π）の順番は、以下の第二ミックスネット演算部ｂによるミックスネットの処理で元の順番、すなわち関数値計算部ｈのステップＳ３の処理で説明をした「所定の順番」に戻る。
【００２８】
第二ミックスネット演算部ｃは、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して置換πの逆置換π−１により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝１，…，Ｊｋ）を生成する（ステップＳ６）。組（ｄ’π，Ｅ’（ｂ）π）の数がＪｋ個とであるため、組（ｄｊ’’，Ｅ’’（ｂｊ））の数もＪｋ個となる。組（ｄｊ’’，Ｅ’’（ｂｊ））は、「所定の順序」におけるｊ番目の組（ｄ’’，Ｅ’’（ｂ））を意味する。生成された複数の組（ｄｊ’’，Ｅ’’（ｂｊ））は、順序付与部ｄに送信される。ある値ｘについてのＥ（ｘ）の再暗号化により生成されたＥ’’（ｘ）は、その値ｘを暗号関数Ｅ’’に入力したときの出力値と見ることができる。この場合の暗号関数Ｅ’’は、準同型性を持つとする。
【００２９】
置換πの逆置換π−１は、π・π−１が恒等置換となるような置換のことである。例えば、置換π：｛１，２，３｝→｛１，２，３｝を１をπ（１）に写し、２をπ（２）に写し、３をπ（３）に写す全単射の写像であり、π（１）＝２、π（２）＝３、π（３）＝１であるとした場合の逆置換π−１：｛１，２，３｝→｛１，２，３｝は、１をπ−１（１）に写し、２をπ−１（２）に写し、３をπ−１（３）に写す全単射の写像であり、π−１（１）＝２、π−１（２）＝１、π−１（３）＝２である。
【００３０】
順序付与部ｄは、複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する（ステップＳ７）。組（ｄｊ’’，Ｅ’’（ｂｊ））の数がＪｋであるため、組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の数もＪｋとなる。
【００３１】
先に述べたように、ｖが一致データｖ＊である場合にはｃπ＝０となりｂ＝１となり、ｖが一致データｖ＊でない場合にはｃπ≠０の場合にはｂ＝０となる。このため、順序ｅｊ’’は、一致データｖ＊を所定の順序で並べたときの順序を暗号関数Ｅ’’で暗号化したものとなる。
【００３２】
第三ミックスネット演算部ｅは、複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する（ステップＳ８）。
【００３３】
置換π＊は、位数Ｊｋの対称群の元である。複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）は、順序復号部ｆに送信される。複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の数がＪｋであるため、組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）の数もＪｋである。
【００３４】
第三ミックスネット演算部ｅによるミックスネットの処理で、置換π＊に基づいて複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の順番が入れ替わる。これにより、置換π＊を知らない順序復号部ｆは、任意の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）が「所定の順序」における何番目の一致データｖ＊かを知ることができるが、その組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）がどのデータｖに対応するものなのかを知ることはできない。このように、組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）とデータｖとの対応関係を順序復号部ｆに秘匿化するために、第三ミックスネット演算部ｅによるミックスネットの処理を行っている。
【００３５】
順序復号部ｆは、Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する（ステップＳ９）。生成された順序ｅπ＊（ｊ）及び順序ｅπ＊（ｊ）に対応するｄπ＊（ｊ）’’’は、並替部ｇに送信される。
【００３６】
並替部ｇは、順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する（ステップＳ１０）。このｄπ＊（ｊ）’’’が、一致データｖ＊のを含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）に対応する。一致データｖ＊の個数だけｄπ＊（ｊ）’’’が出力される。
【００３７】
制御部ｉは、１からｎまでのすべての整数がｋに設定されたかどうか判定する（ステップＳ１１）。設定されていない場合には、ステップＳ１に戻り、制御部ｉは、１からｎまでの何れかの数であってまだ設定されていない数をｋに設定する。１からｎまでのすべての整数がｋに設定されたたと判定された場合には、マッチングシステムの処理を終了する。
【００３８】
このようにして、ステップＳ２からステップＳ１０の処理を繰り返すことにより、各テーブルＴｋ（ｋ＝１，２，…，ｎ）の一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。
【００３９】
［第二実施形態］
第二実施形態のマッチングシステム及び方法は、関数値計算部ｈ、第一ミックスネット演算部ａ、フラグ付与部ｂにおいて第一実施形態のマッチングシステム及び方法と異なる。以下、第一実施形態と異なる部分を中心に説明する。同様の部分については説明を省略する。
【００４０】
第二実施形態の関数値計算部ｈは、ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ−１｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ−１｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する（ステップＳ３）。
【００４１】
第一実施形態とは、ｃの定義が異なる。また、第一実施形態では組（ｄ，ｃ）が送信されるのに対して、第二実施形態ではｃだけが第一ミックスネット演算部ａに所定の順序で送信される。
【００４２】
ここで、||はビット結合を表わす。検査符号ｔｋ（ｖ）は、ｅｘｔｋ（ｖ）に対応するビット列である。例えば、検査符号ｔｋ（ｖ）は、ｖに依存しない００…０等の一定のビット列であってもよいし、ｖに依存するビット列、例えばｅｘｔｋ（ｖ）のハッシュ値であってもよい。
【００４３】
第一ミックスネット演算部ａは、所定の順序で並んだ複数のｃを置換πにより置換した複数のｃπを生成する。順序が並び替えられた複数のｃπは、フラグ付与部ｂに送信される。
【００４４】
フラグ付与部ｂ３は、Ｅ’を準同型性を持つ暗号関数として、複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
ｃ’πの復号は、図１に例示するフラグ付与部ｂの復号部ｂ１により行われる。また、ｂの暗号化は、フラグ付与部ｂの暗号化部ｂ２により行われる。さらに、ｃπの復号結果＝ｅｘｔｋ（ｖ）であるかどうかの判断は、判定部ｂ３により行われる。
【００４５】
判定部ｂ３は、復号部ｂ１によるｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が、関数値計算部ｈがビット結合したｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する。
【００４６】
ｃπの復号結果＝ｅｘｔｋ（ｖ）でない場合には、ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列は、関数値計算部ｈがｅｘｔｋ（ｖ）に対してビット結合したｔｋ（ｖ）と一致しない可能性が非常に高い。このため、復号部ｂ１によるｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が、関数値計算部ｈがビット結合したｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）と判断できるのである。 フラグ付与部ｂは、上記の一致の判定をする必要があるため、検査符号ｔｋ（ｖ）についての情報を事前に知っているとする。検査符号ｔｋ（ｖ）がｖに依存するビット列である場合には、フラグ付与部ｂは置換πについての情報を知っており、ｃπに対応する検査符号ｔｋ（ｖ）をわかっているものとする。
【００４７】
このように、フラグ付与部ｂが検査符号ｔｋ（ｖ）を用いてｃπの復号結果＝ｅｘｔｋ（ｖ）であるかを判定可能とすることにより、フラグ付与部ｂに対してｅｘｔｋ（ｖ）を秘匿化することができる。
【００４８】
他の処理は第一実施形態と同様である。
【００４９】
［変形例等］
暗号関数Ｅ，Ｅ’，Ｅ’’Ｅ’’’は、準同型性の性質を持つ確率暗号であってもよい。これにより、安全性が増す。
【００５０】
第一ミックスネット演算部ａは、図２に例示するように、第１結合装置１に設けられた第一ミックスネット構成部ａ１、第２結合装置２に設けられた第一ミックスネット演算部ａ２、…、第ｋ結合装置ｋに設けられた第一ミックスネット構成部ａｋ、…、第ｎ結合装置ｎに設けられた第一ミックスネット構成部ａｎにより構成されてもよい。この場合、これらのｎ個の第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）が共同して処理を行うことにより、第一ミックスネット演算部ａの処理を実現する。
【００５１】
例えば、再暗号化関数が多重暗号又は閾値関数であるとして、順次ｉ＝ｋ＋１，ｋ＋２，…，ｎ，１，２，…，ｋ−１として、第一ミックスネット構成部ａｉが、複数の組（ｄ，ｃ）を再暗号化して予め定められた順序で入れ替えて、第一ミックスネット構成部ａｉ＋１（ｉ＝ｎである場合には、第一ミックスネット構成部ａ１）に送信する。
【００５２】
また、この際に、各第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）が、ｄのみを再暗号化して、ｃについては部分的な復号を行ってもよい。各第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）がｃについての部分的な復号を行うことにより、ｃが復元される。すなわち、第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）により構成される第一ミックスネット演算部ａが、ミックスネットの処理と同時に、復号部ｂ１の処理を行ってもよい。
【００５３】
同様にして、第二ミックスネット構成部ｃが、図４に例示するように、第１結合装置１に設けられた第二ミックスネット構成部ｃ１、第２結合装置２に設けられた第二ミックスネット演算部ｃ２、…、第ｋ結合装置ｋに設けられた第二ミックスネット構成部ｃｋ、…、第ｎ結合装置ｎに設けられた第二ミックスネット構成部ｃｎにより構成されてもよい。この場合、順次ｉ＝ｋ−１，ｋ−２，…，１，ｎ，ｎ−１，…，ｋ＋１として、第二ミックスネット構成部ｃｉが、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して予め定められた順序で入れ替えて、第二ミックスネット構成部ａｉ＋１（ｉ＝ｎである場合には、第一ミックスネット構成部ａ１）に送信する。
【００５４】
同様にして、第三ミックスネット構成部ｅが、図５に例示するように、第１結合装置１に設けられた第三ミックスネット構成部ｅ１、第２結合装置２に設けられた第三ミックスネット演算部ｅ２、…、第ｋ結合装置ｋに設けられた第三ミックスネット構成部ｅｋ、…、第ｎ結合装置ｎに設けられた第三ミックスネット構成部ｅｎにより構成されてもよい。
【００５５】
また、この際に、各第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）が、ｄｊ’’及びｅｊ’’を再暗号化して、Ｅ’’（ｂｊ）については部分的な復号を行ってもよい。各第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）がＥ’’（ｂｊ）についての部分的な復号を行うことにより、ｂπ＊（ｊ）が復元される。すなわち、第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）により構成される第三ミックスネット演算部ｅが、ミックスネットの処理と同時に、Ｅ’’’（ｂπ＊（ｊ））の復号を行ってもよい。
【００５６】
マッチングシステムは、並替部ｇにより出力されたｄπ＊（ｊ）’’’を復号して、ｅｘｔｋ（ｖ＊）を生成する最終復号部を有していてもよい。
【００５７】
なお、上記の実施形態では、マッチングシステムの各部間でデータは直接送受信されていたが、データは図示されていない記憶部を介してやり取りされてもよい。
【００５８】
第ｉ結合装置ｉ（ｉ＝１，２，…，ｎ）をコンピュータによって実現する場合、第ｉ結合装置ｉの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第ｉ結合装置ｉの各部の処理機能がコンピュータ上で実現される。
【００５９】
これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６０】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６１】
また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【技術分野】
【０００１】
この発明は、複数の表形式のデータについて非開示のまま必要なデータを結合する技術に関する。
【背景技術】
【０００２】
非特許文献１に、複数の表形式のデータについて非開示のまま必要なデータを結合する技術が記載されている。以下、非特許文献１に記載された技術でできることを簡単に説明する（例えば、非特許文献１参照。）。
【０００３】
図６に示すように、第１テーブル及び第２テーブルがあるとする。非特許文献１の技術により、第１テーブルのキーカラムのデータと、第２テーブルのキーカラムのデータとで一致するものを特定し、その一致するデータを含むタプル（行）のデータを結合して取得することができる。
【０００４】
図６の例だと、第１テーブルのキーカラム及び第２テーブルのキーカラムは、０１４及び０３４のデータが共に含む。したがって、取得することができる結合データは、データ０１４と第１テーブルの０１４のデータを含むタプルのデータｘｘｘと第２テーブルの０１４のデータを含むタプルのデータｂｂｂとを結合したデータ、及び、データ０３４と第１テーブルの０３４のデータを含むタプルのデータｚｚｚと第２テーブルの０３４のデータを含むタプルのデータｃｃｃとを結合したデータとなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R.Agrawal, A.V.Evfimievski, and R.Srikant, “Information Sharing Across Private Databases”, ACM SIGMOD 2003, pp.86-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１の技術では、キーカラムの一致するデータを含むタプルのデータを結合したデータのみならず、キーカラムの一致するデータ自体が分かってしまう。図６の例では、データ０１４及び０３４において、一致するということが分かってしまう。
【０００７】
この発明は、キーカラムの一致するデータの情報を秘匿化したマッチングシステム、方法、結合装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
この発明の第一の態様であるマッチングシステムは、ｎを２以上の整数、ｋを１以上ｎ以下の整数として、ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、ｃとｄとの組（ｄ，ｃ）を生成する関数値計算部と、複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算部と、Ｅ’を準同型性を持つ暗号関数として、複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、を含む。
【発明の効果】
【０００９】
キーカラムの一致するデータの情報を秘匿化することができる。
【図面の簡単な説明】
【００１０】
【図１】マッチングシステムの例を説明するためのブロック図。
【図２】第一ミックスネット演算部の変形例を説明するためのブロック図。
【図３】第二ミックスネット演算部の変形例を説明するためのブロック図。
【図４】第三ミックスネット演算部の変形例を説明するためのブロック図。
【図５】マッチングシステムの方法の例を説明するためのプログラム。
【図６】従来のマッチングシステムの概要を説明するための図。
【発明を実施するための形態】
【００１１】
以下、図面を参照してこの発明の実施形態を説明する。
【００１２】
［第一実施形態］
第一実施形態のマッチングシステムは、図１に示すように、第１結合装置１、第２結合装置２、…、第ｋ結合装置ｋ、…、第ｎ結合装置ｎ、テーブル記憶部１１，２１，…，ｋ１，ｎ１、第一ミックスネット演算部ａ，フラグ付与部ｂ、第二ミックスネット演算部ｃ、順序付与部ｄ、第三ミックスネット演算部ｅ、順序復号部ｆ、並替部ｇ、制御部ｉを例えば備える。ｎは２以上の整数である。
【００１３】
第１結合装置１は、第１テーブルＴ１を保有する。第１テーブルＴ１はテーブル記憶部１１に記憶されている。同様にして、ｉ＝２，３，…，ｎとして、第ｉ結合装置ｉは、第ｉテーブルＴｉを保有する。第ｉテーブルＴｉはテーブル記憶部ｉ１に記憶されている。
【００１４】
各テーブルＴｉは、カラム（列）及びタプル（行）で構成される。マッチングシステムは、すべてのテーブルＴｉ（ｉ＝１，２，…，ｎ）の所定のカラムにおいて一致するデータを特定し、その一致するデータｖ＊（以下、一致データｖ＊と呼ぶ。）を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を結合したデータを取得する。一致するデータを特定する対象となるカラムをキーカラムと呼ぶことにする。各テーブルＴｉのキーカラムＶｉは予め定められているものとする。
【００１５】
制御部ｉは、ｋを１からｎまでの何れかの数であって、まだ設定されていない数に設定する（ステップＳ１）。例えば、ｋ＝１とする。
【００１６】
以下のステップＳ２からステップＳ１０の処理により、所定の順序で並んだ、テーブルＴｋの一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。制御部ｉがｋを異なる値に順次変えてステップＳ２からステップＳ１０の処理を繰り返すことにより、各テーブルＴｋ（ｋ＝１，２，…，ｎ）の一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。各ｋに対応して求まったデータは、共通する所定の順序、例えば一致データｖ＊の辞書順で並んでいる。したがって、同一の順序のｖ＊のｅｘｔｋ（ｖ＊）（ｋ＝１，２，…，ｎ）の集合を取得することにより、同一の一致データｖ＊についてのｅｘｔｋ（ｖ＊）の集合、すなわち（ｅｘｔ１（ｖ＊），ｅｘｔ２（ｖ＊），…，ｅｘｔｎ（ｖ＊））を取得することができる。
【００１７】
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとして、各第ｉ結合装置は、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する（ステップＳ２）。
【００１８】
ここで、ｔは所定の数である。ｔは、例えば１であってもよいし、乱数であってもよい。Ｊｉは、キーカラムＶｉを構成するデータｖの数である。上記の多項式ｆｉ（ｘ）の式の中の下付きのＶｉは、キーカラムＶｉを意味する。Ｅ（ａｉ，ｊ）は、第一ミックスネット演算部ａに送信される。
【００１９】
関数値計算部ｈは、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する（ステップＳ３）。ｒｉは、整数の乱数である。ｅｘｔｋ（ｖ）は、キーカラムＶｋのデータｖを含むタプルの全部又は一部のデータである。キーカラムＶｋのデータｖの数をＪｋ個とすると、Ｊｋ個の組（ｄ，ｃ）が生成される。生成された組（ｄ，ｃ）は、第一ミックスネット演算部ａに所定の順序で送信される。所定の順序とは、例えば辞書順である。以下、単に所定の順序といった場合には、この所定の順序を意味する。
【００２０】
暗号関数Ｅは準同型性の性質を持つため、加法的に記載すれば、Ｅ（αβ）＝Ｅ（β＋β＋…＋β）＝Ｅ（β）＋Ｅ（β）＋…＋Ｅ（β）＝αＥ（β）となる。このため、Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉとなるのである。
【００２１】
関数値計算部ｈは、図１に示すように第ｋ結合装置ｋの中に設けられている。このため、ステップＳ１の処理において、第１結合装置１から第ｎ結合装置ｎで第ｋ結合装置ｋとして選択される可能性がある結合装置は、関数計算部ｈを備えていることになる。なお、関数値計算部ｈは、第ｋ結合装置ｋの外部に設けられていてもよい。
【００２２】
第一ミックスネット演算部ａは、複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する（ステップＳ４）。置換πは位数Ｊｋの対称群の元である。複数の組（ｄ’π，ｃ’π）は、フラグ付与部ｂに送信される。複数の組（ｄ，ｃ）の数がＪｋあるため、組（ｄ’π，ｃ’π）の数もＪｋである。
【００２３】
例えば組（ｄ，ｃ）の数が３つであり、それぞれ組（ｄ１，ｃ１）、組（ｄ２，ｃ２）及び組（ｄ３，ｃ３）であるとする。このとき、これらの３つの組（ｄ，ｃ）のそれぞれを暗号化して、組（ｄ１’，ｃ１’）、組（ｄ２’，ｃ２’）及び組（ｄ３’，ｃ３’）とする。置換π：｛１，２，３｝→｛１，２，３｝は１をπ（１）に写し、２をπ（２）に写し、３をπ（３）に写す全単射の写像であり、例えばπ（１）＝２、π（２）＝３、π（３）＝１であるとする。この場合、これらの組（ｄ１’，ｃ１’）、組（ｄ２’，ｃ２’）及び組（ｄ３’，ｃ３’）を置換πで置換すると、組（ｄπ（３）’，ｃπ（３）’）、組（ｄπ（１）’，ｃπ（１）’）及び組（ｄπ（２）’，ｃπ（２）’）となる。
【００２４】
フラグ付与部ｂは、複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成する（ステップＳ５）。複数の組（ｄ’π，ｃ’π）の数がＪｋであるため、組（ｄ’π，Ｅ’（ｂ）π）の数もＪｋ個となる。生成された複数の組（ｄ’π，Ｅ’（ｂ）π）は、第二ミックスネット演算部ｃに送信される。
【００２５】
ｖが一致データｖ＊である場合にはｃπ＝０となりｂ＝１となり、ｖが一致データｖ＊でない場合にはｃπ≠０の場合にはｂ＝０となる。
【００２６】
ｃ’πの復号は、図１に例示するフラグ付与部ｂの復号部ｂ１により行われる。また、ｂの暗号化は、フラグ付与部ｂの暗号化部ｂ２により行われる。Ｅ’は、準同型性を持つ暗号関数である。
【００２７】
第一ミックスネット演算部ａによるミックスネットの処理で、置換πに基づいて複数の組（ｄ，ｃ）の順序が入れ替わるため、置換πを知らないフラグ付与部ｂは、任意の組（ｄ’π，ｃ’π）が一致データｖ＊に対応するかどうかを知ることができるが、その組（ｄ’π，ｃ’π）がどのデータｖに対応するものであるのかを知ることができない。このように、組（ｄ’π，ｃ’π）とデータｖとの対応関係をフラグ付与部ｂに秘匿化するために、第一ミックスネット演算部ａによるミックスネットの処理を行っている。なお、第一ミックスネット演算部ａによるミックスネットの処理で入れ替わった複数の組（ｄ，ｃ）及び複数の組（ｄ’π，Ｅ’（ｂ）π）の順番は、以下の第二ミックスネット演算部ｂによるミックスネットの処理で元の順番、すなわち関数値計算部ｈのステップＳ３の処理で説明をした「所定の順番」に戻る。
【００２８】
第二ミックスネット演算部ｃは、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して置換πの逆置換π−１により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝１，…，Ｊｋ）を生成する（ステップＳ６）。組（ｄ’π，Ｅ’（ｂ）π）の数がＪｋ個とであるため、組（ｄｊ’’，Ｅ’’（ｂｊ））の数もＪｋ個となる。組（ｄｊ’’，Ｅ’’（ｂｊ））は、「所定の順序」におけるｊ番目の組（ｄ’’，Ｅ’’（ｂ））を意味する。生成された複数の組（ｄｊ’’，Ｅ’’（ｂｊ））は、順序付与部ｄに送信される。ある値ｘについてのＥ（ｘ）の再暗号化により生成されたＥ’’（ｘ）は、その値ｘを暗号関数Ｅ’’に入力したときの出力値と見ることができる。この場合の暗号関数Ｅ’’は、準同型性を持つとする。
【００２９】
置換πの逆置換π−１は、π・π−１が恒等置換となるような置換のことである。例えば、置換π：｛１，２，３｝→｛１，２，３｝を１をπ（１）に写し、２をπ（２）に写し、３をπ（３）に写す全単射の写像であり、π（１）＝２、π（２）＝３、π（３）＝１であるとした場合の逆置換π−１：｛１，２，３｝→｛１，２，３｝は、１をπ−１（１）に写し、２をπ−１（２）に写し、３をπ−１（３）に写す全単射の写像であり、π−１（１）＝２、π−１（２）＝１、π−１（３）＝２である。
【００３０】
順序付与部ｄは、複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する（ステップＳ７）。組（ｄｊ’’，Ｅ’’（ｂｊ））の数がＪｋであるため、組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の数もＪｋとなる。
【００３１】
先に述べたように、ｖが一致データｖ＊である場合にはｃπ＝０となりｂ＝１となり、ｖが一致データｖ＊でない場合にはｃπ≠０の場合にはｂ＝０となる。このため、順序ｅｊ’’は、一致データｖ＊を所定の順序で並べたときの順序を暗号関数Ｅ’’で暗号化したものとなる。
【００３２】
第三ミックスネット演算部ｅは、複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する（ステップＳ８）。
【００３３】
置換π＊は、位数Ｊｋの対称群の元である。複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）は、順序復号部ｆに送信される。複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の数がＪｋであるため、組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）の数もＪｋである。
【００３４】
第三ミックスネット演算部ｅによるミックスネットの処理で、置換π＊に基づいて複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）の順番が入れ替わる。これにより、置換π＊を知らない順序復号部ｆは、任意の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）が「所定の順序」における何番目の一致データｖ＊かを知ることができるが、その組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）がどのデータｖに対応するものなのかを知ることはできない。このように、組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）とデータｖとの対応関係を順序復号部ｆに秘匿化するために、第三ミックスネット演算部ｅによるミックスネットの処理を行っている。
【００３５】
順序復号部ｆは、Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する（ステップＳ９）。生成された順序ｅπ＊（ｊ）及び順序ｅπ＊（ｊ）に対応するｄπ＊（ｊ）’’’は、並替部ｇに送信される。
【００３６】
並替部ｇは、順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する（ステップＳ１０）。このｄπ＊（ｊ）’’’が、一致データｖ＊のを含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）に対応する。一致データｖ＊の個数だけｄπ＊（ｊ）’’’が出力される。
【００３７】
制御部ｉは、１からｎまでのすべての整数がｋに設定されたかどうか判定する（ステップＳ１１）。設定されていない場合には、ステップＳ１に戻り、制御部ｉは、１からｎまでの何れかの数であってまだ設定されていない数をｋに設定する。１からｎまでのすべての整数がｋに設定されたたと判定された場合には、マッチングシステムの処理を終了する。
【００３８】
このようにして、ステップＳ２からステップＳ１０の処理を繰り返すことにより、各テーブルＴｋ（ｋ＝１，２，…，ｎ）の一致データｖ＊を含むタプルの全部又は一部のデータｅｘｔｋ（ｖ＊）を取得することができる。
【００３９】
［第二実施形態］
第二実施形態のマッチングシステム及び方法は、関数値計算部ｈ、第一ミックスネット演算部ａ、フラグ付与部ｂにおいて第一実施形態のマッチングシステム及び方法と異なる。以下、第一実施形態と異なる部分を中心に説明する。同様の部分については説明を省略する。
【００４０】
第二実施形態の関数値計算部ｈは、ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ−１｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ−１｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する（ステップＳ３）。
【００４１】
第一実施形態とは、ｃの定義が異なる。また、第一実施形態では組（ｄ，ｃ）が送信されるのに対して、第二実施形態ではｃだけが第一ミックスネット演算部ａに所定の順序で送信される。
【００４２】
ここで、||はビット結合を表わす。検査符号ｔｋ（ｖ）は、ｅｘｔｋ（ｖ）に対応するビット列である。例えば、検査符号ｔｋ（ｖ）は、ｖに依存しない００…０等の一定のビット列であってもよいし、ｖに依存するビット列、例えばｅｘｔｋ（ｖ）のハッシュ値であってもよい。
【００４３】
第一ミックスネット演算部ａは、所定の順序で並んだ複数のｃを置換πにより置換した複数のｃπを生成する。順序が並び替えられた複数のｃπは、フラグ付与部ｂに送信される。
【００４４】
フラグ付与部ｂ３は、Ｅ’を準同型性を持つ暗号関数として、複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
ｃ’πの復号は、図１に例示するフラグ付与部ｂの復号部ｂ１により行われる。また、ｂの暗号化は、フラグ付与部ｂの暗号化部ｂ２により行われる。さらに、ｃπの復号結果＝ｅｘｔｋ（ｖ）であるかどうかの判断は、判定部ｂ３により行われる。
【００４５】
判定部ｂ３は、復号部ｂ１によるｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が、関数値計算部ｈがビット結合したｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する。
【００４６】
ｃπの復号結果＝ｅｘｔｋ（ｖ）でない場合には、ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列は、関数値計算部ｈがｅｘｔｋ（ｖ）に対してビット結合したｔｋ（ｖ）と一致しない可能性が非常に高い。このため、復号部ｂ１によるｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が、関数値計算部ｈがビット結合したｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）と判断できるのである。 フラグ付与部ｂは、上記の一致の判定をする必要があるため、検査符号ｔｋ（ｖ）についての情報を事前に知っているとする。検査符号ｔｋ（ｖ）がｖに依存するビット列である場合には、フラグ付与部ｂは置換πについての情報を知っており、ｃπに対応する検査符号ｔｋ（ｖ）をわかっているものとする。
【００４７】
このように、フラグ付与部ｂが検査符号ｔｋ（ｖ）を用いてｃπの復号結果＝ｅｘｔｋ（ｖ）であるかを判定可能とすることにより、フラグ付与部ｂに対してｅｘｔｋ（ｖ）を秘匿化することができる。
【００４８】
他の処理は第一実施形態と同様である。
【００４９】
［変形例等］
暗号関数Ｅ，Ｅ’，Ｅ’’Ｅ’’’は、準同型性の性質を持つ確率暗号であってもよい。これにより、安全性が増す。
【００５０】
第一ミックスネット演算部ａは、図２に例示するように、第１結合装置１に設けられた第一ミックスネット構成部ａ１、第２結合装置２に設けられた第一ミックスネット演算部ａ２、…、第ｋ結合装置ｋに設けられた第一ミックスネット構成部ａｋ、…、第ｎ結合装置ｎに設けられた第一ミックスネット構成部ａｎにより構成されてもよい。この場合、これらのｎ個の第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）が共同して処理を行うことにより、第一ミックスネット演算部ａの処理を実現する。
【００５１】
例えば、再暗号化関数が多重暗号又は閾値関数であるとして、順次ｉ＝ｋ＋１，ｋ＋２，…，ｎ，１，２，…，ｋ−１として、第一ミックスネット構成部ａｉが、複数の組（ｄ，ｃ）を再暗号化して予め定められた順序で入れ替えて、第一ミックスネット構成部ａｉ＋１（ｉ＝ｎである場合には、第一ミックスネット構成部ａ１）に送信する。
【００５２】
また、この際に、各第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）が、ｄのみを再暗号化して、ｃについては部分的な復号を行ってもよい。各第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）がｃについての部分的な復号を行うことにより、ｃが復元される。すなわち、第一ミックスネット構成部ａｉ（ｉ＝１，２，…，ｎ）により構成される第一ミックスネット演算部ａが、ミックスネットの処理と同時に、復号部ｂ１の処理を行ってもよい。
【００５３】
同様にして、第二ミックスネット構成部ｃが、図４に例示するように、第１結合装置１に設けられた第二ミックスネット構成部ｃ１、第２結合装置２に設けられた第二ミックスネット演算部ｃ２、…、第ｋ結合装置ｋに設けられた第二ミックスネット構成部ｃｋ、…、第ｎ結合装置ｎに設けられた第二ミックスネット構成部ｃｎにより構成されてもよい。この場合、順次ｉ＝ｋ−１，ｋ−２，…，１，ｎ，ｎ−１，…，ｋ＋１として、第二ミックスネット構成部ｃｉが、複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して予め定められた順序で入れ替えて、第二ミックスネット構成部ａｉ＋１（ｉ＝ｎである場合には、第一ミックスネット構成部ａ１）に送信する。
【００５４】
同様にして、第三ミックスネット構成部ｅが、図５に例示するように、第１結合装置１に設けられた第三ミックスネット構成部ｅ１、第２結合装置２に設けられた第三ミックスネット演算部ｅ２、…、第ｋ結合装置ｋに設けられた第三ミックスネット構成部ｅｋ、…、第ｎ結合装置ｎに設けられた第三ミックスネット構成部ｅｎにより構成されてもよい。
【００５５】
また、この際に、各第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）が、ｄｊ’’及びｅｊ’’を再暗号化して、Ｅ’’（ｂｊ）については部分的な復号を行ってもよい。各第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）がＥ’’（ｂｊ）についての部分的な復号を行うことにより、ｂπ＊（ｊ）が復元される。すなわち、第三ミックスネット構成部ｅｉ（ｉ＝１，２，…，ｎ）により構成される第三ミックスネット演算部ｅが、ミックスネットの処理と同時に、Ｅ’’’（ｂπ＊（ｊ））の復号を行ってもよい。
【００５６】
マッチングシステムは、並替部ｇにより出力されたｄπ＊（ｊ）’’’を復号して、ｅｘｔｋ（ｖ＊）を生成する最終復号部を有していてもよい。
【００５７】
なお、上記の実施形態では、マッチングシステムの各部間でデータは直接送受信されていたが、データは図示されていない記憶部を介してやり取りされてもよい。
【００５８】
第ｉ結合装置ｉ（ｉ＝１，２，…，ｎ）をコンピュータによって実現する場合、第ｉ結合装置ｉの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、第ｉ結合装置ｉの各部の処理機能がコンピュータ上で実現される。
【００５９】
これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６０】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６１】
また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【特許請求の範囲】
【請求項１】
ｎを２以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する関数値計算部と、
上記複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算部と、
Ｅ’を準同型性を持つ暗号関数として、上記複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、
を含むマッチングシステム。
【請求項２】
ｎを３以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、||をビット結合とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する関数値計算部と、
所定の順序で並んだ上記複数のｃを置換πにより置換した複数のｃπを生成する第一ミックスネット演算部と、
各上記ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が上記ｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する判定部と、
Ｅ’を準同型性を持つ暗号関数として、上記複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、
を含むマッチングシステム。
【請求項３】
ｎを２以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合ステップと、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する関数値計算ステップと、
上記複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算ステップと、
Ｅ’を準同型性を持つ暗号関数として、上記複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与ステップと、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算ステップと、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号ステップと、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替ステップと、
を含むマッチングシステムの方法。
【請求項４】
ｎを３以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合ステップと、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、||をビット結合とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する関数値計算ステップと、
所定の順序で並んだ上記複数のｃを置換πにより置換した複数のｃπを生成する第一ミックスネット演算ステップと、
各上記ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が上記ｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する判定ステップと、
Ｅ’を準同型性を持つ暗号関数として、上記複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与ステップと、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算ステップと、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号ステップと、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替ステップと、
を含むマッチングシステムの方法。
【請求項５】
請求項１又は請求項２のマッチングシステムの第ｉ結合装置である結合装置。
【請求項６】
請求項５の結合装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
ｎを２以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する関数値計算部と、
上記複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算部と、
Ｅ’を準同型性を持つ暗号関数として、上記複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、
を含むマッチングシステム。
【請求項２】
ｎを３以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合装置と、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、||をビット結合とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する関数値計算部と、
所定の順序で並んだ上記複数のｃを置換πにより置換した複数のｃπを生成する第一ミックスネット演算部と、
各上記ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が上記ｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する判定部と、
Ｅ’を準同型性を持つ暗号関数として、上記複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与部と、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与部と、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算部と、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号部と、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替部と、
を含むマッチングシステム。
【請求項３】
ｎを２以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合ステップと、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）として、キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＝Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）vｊｒｉを計算し、ｄ＝Ｅ（ｅｘｔｋ（ｖ））を計算し、上記ｃとｄとの組（ｄ，ｃ）を生成する関数値計算ステップと、
上記複数の組（ｄ，ｃ）を再暗号化して置換πにより置換した複数の組（ｄ’π，ｃ’π）を生成する第一ミックスネット演算ステップと、
Ｅ’を準同型性を持つ暗号関数として、上記複数の組（ｄ’π，ｃ’π）のそれぞれについて、ｃ’πの復号結果ｃπ＝０である場合にはｂ＝１とし、ｃ’πの復号結果ｃπ＝０でない場合にはｂ＝０として、そのｃ’πの組（ｄ’π，ｃ’π）のｄ’ πとＥ’（ｂ）πとの組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与ステップと、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算ステップと、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号ステップと、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替ステップと、
を含むマッチングシステムの方法。
【請求項４】
ｎを３以上の整数、ｋを１以上ｎ以下の整数として、
ｉ＝１，…，ｋ−１，ｋ＋１，…，ｎとし、第ｉテーブルの予め定められたキーカラムＶｉのデータをｖとし、ｔを所定の数として、ｆｉ（ｘ）＝ｔΠｖ∈Ｖｉ（ｘ−ｖ）＝Σｊ＝０Ｊｉ−１ａｉ，ｊｘｊで定義される多項式ｆｉ（ｘ）の各係数ａｉ，ｊを準同型性を持つ暗号関数Ｅで暗号化したＥ（ａｉ，ｊ）を計算する第ｉ結合ステップと、
ｒｉを整数の乱数とし、第ｋテーブルの予め定められたキーカラムＶｋのデータｖを含むタプルの全部又は一部のデータをｅｘｔｋ（ｖ）とし、||をビット結合とし、ｅｘｔｋ（ｖ）に対応するビット列を検査符号ｔｋ（ｖ）として，キーカラムＶｋの各データｖについて、上記Ｅ（ａｉ，ｊ）を用いて、ｃ＝Ｅ（（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝ｆｉ（ｖ）ｒｉ）＋（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））＝（Σｉ∈｛１，２，…，ｎ｝−｛ｋ｝Ｅ（ａｉ，ｊ）ｖｊｒｉ）＋Ｅ（（ｅｘｔｋ（ｖ）||ｔｋ（ｖ）））を計算する関数値計算ステップと、
所定の順序で並んだ上記複数のｃを置換πにより置換した複数のｃπを生成する第一ミックスネット演算ステップと、
各上記ｃπの復号結果のビット列のうちｔｋ（ｖ）に対応するビット列が上記ｔｋ（ｖ）と一致する場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）であり、一致しない場合にはそのｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判断する判定ステップと、
Ｅ’を準同型性を持つ暗号関数として、上記複数のｃπのそれぞれについて、ｃπの復号結果＝ｅｘｔｋ（ｖ）であると判定された場合にはｂ＝１とし、ｃπの復号結果＝ｅｘｔｋ（ｖ）でないと判定された場合にはｂ＝０として、そのｃπに対応するＥ’（ｂ）πとｄπ’＝Ｅ（ｅｘｔｋ（ｖ））の組（ｄ’π，Ｅ’（ｂ）π）を生成するフラグ付与ステップと、
上記複数の組（ｄ’π，Ｅ’（ｂ）π）を再暗号化して上記置換πの逆置換により置換した複数の組（ｄｊ’’，Ｅ’’（ｂｊ））（ｊ＝1，2，…，Ｊｋ）を生成する第二ミックスネット演算ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ））のそれぞれについて、Ｅ’’（ｂｊ）を用いて、順序ｅｊ’’＝Ｅ’’（Σｋ＝１ｊｂｋ）＝Σｋ＝１ｊＥ’’（ｂｋ）を計算して、計算された順序ｅｊ’’を組（ｄｊ’’，Ｅ’’（ｂｊ））に追加した組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を生成する順序付与ステップと、
上記複数の組（ｄｊ’’，Ｅ’’（ｂｊ），ｅｊ’’）を再暗号化して置換π＊により置換した複数の組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）を生成する第三ミックスネット演算ステップと、
Ｅ’’’（ｂπ＊（ｊ））を復号したｂπ＊（ｊ）＝１となる組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｅπ＊（ｊ）’’’を復号して順序ｅπ＊（ｊ）を生成する順序復号ステップと、
上記順序ｅπ＊（ｊ）で組（ｄπ＊（ｊ）’’’，Ｅ’’’（ｂπ＊（ｊ）），ｅπ＊（ｊ）’’’）のｄπ＊（ｊ）’’’を出力する並替ステップと、
を含むマッチングシステムの方法。
【請求項５】
請求項１又は請求項２のマッチングシステムの第ｉ結合装置である結合装置。
【請求項６】
請求項５の結合装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１５０３７９（Ｐ２０１２−１５０３７９Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１１−１０５４９（Ｐ２０１１−１０５４９）
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]