分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラム
【課題】 従来の分散型秘匿化データ統合装置では、第３者による中央集権的な集計サーバを必要としていた。また、第３者による中央集権的な集計サーバを置かない場合、データを秘匿化していても集合演算を行うと他ノードからデータの内容を推測される危険性があった。
【解決手段】 各ノードが保持している要素集合にダミー文字列を加えることにより文字列撹乱、要素数撹乱を行った上で暗号化を行い、他のノードにデータ送信する。集計ノードは、暗号化された要素集合を復号化し、文字列撹乱、要素数撹乱で加えられたダミー文字列を正確に除去した上で集合演算を行う。このような構成を採用することによって、中央集権的な集計サーバを置かなくても、要素集合を他のノードから推測できない状態にしながら、分散ノード間で連携してデータ統合を行うことができる。
【解決手段】 各ノードが保持している要素集合にダミー文字列を加えることにより文字列撹乱、要素数撹乱を行った上で暗号化を行い、他のノードにデータ送信する。集計ノードは、暗号化された要素集合を復号化し、文字列撹乱、要素数撹乱で加えられたダミー文字列を正確に除去した上で集合演算を行う。このような構成を採用することによって、中央集権的な集計サーバを置かなくても、要素集合を他のノードから推測できない状態にしながら、分散ノード間で連携してデータ統合を行うことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムに関し、特に中央集権型の集計サーバを必要とせず、かつ、統合対象となるテーブルのキー、属性、および生データをお互いに推測されることなく統合することが可能な分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムに関する。
【背景技術】
【０００２】
近年、顧客の購買履歴等から有用な知識を抽出する仕組みとしてデータマイニングの重要性が高まっている。特に、複数の企業が持つデータを統合することによって、より広範囲で深い消費者行動に関する知識が得られるものと期待されている。一方で、個人情報保護の観点から、複数の企業が生の顧客データをそのまま公開して統合データを構築するわけにはいかず、プライバシーを保護しながらデータマイニングを行う手法が必須である。
【０００３】
分散サーバに格納されている分散データを秘匿化して統合する従来技術は、大きく以下の３通りのアプローチに分類できる。
(A)ハッシュ関数を使った匿名IDの利用
(B)乱数によるノイズを用いたデータ撹乱
(C)準同型暗号による電子投票プロトコル
【０００４】
(A)のハッシュ関数を使った匿名IDの利用とは、人名のような特定の個人を識別可能な識別情報に対してハッシュ関数を用いて元の識別情報を類推しにくい匿名IDを生成し、匿名IDを用いて顧客データを統合・管理する方法である。特許文献1では、個人IDをハッシュ関数を用いて匿名IDを生成し、匿名IDをキーとして個人の購買履歴データを収集することによって、特定の個人IDと購買履歴データが結びつかない状態で購買商品や金額の集計する方法が開示されている。
【０００５】
(B)の乱数によるノイズを用いたデータ撹乱とは、集計対象となる数値データに対して乱数によるノイズを加えることによって撹乱データを生成し、個別のデータの内容を秘匿化する方法である。特許文献２では、あらかじめ撹乱データに含まれるノイズの統計的分布を決めておき、撹乱データの合計を計算した後にノイズの平均値を除去することによって、近似的に生データの合計を得る方法が開示されている。
【０００６】
(C)の準同型暗号による電子投票プロトコルとは、暗号化によってデータを秘匿化するとともに、秘匿化されたデータ同士を演算することによって、元のデータの演算も行うことができる方法である。このような暗号方式の例として、加法準同型暗号を持つ、Paillier暗号が挙げられる。Paillier暗号では、メッセージx1に対する暗号化e(x1)と、メッセージx2に対する暗号化e(x2)の間に、以下のような関係が成り立っており、これを加法準同型性と呼ぶ。
e(x1) * e(x2) = e(x1 + x2)
【０００７】
非特許文献１では、この準同型性を利用して、データ入力ノードから暗号化された数値データを集計サーバに送信し、集計サーバで受信したデータの積を計算し、その結果を管理サーバ側で復号化することによって、データ入力ノードに入力された数値の合計を求める方法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−３０１９７８
【特許文献２】特開２００７−２８８４８０
【非特許文献】
【０００９】
【非特許文献１】谷川浩司、中西透、舩曵信生、プライバシーを保護した授業評価アンケートの実装、電子情報通信学会技術研究報告、ISEC2006-59、pp. 145-151、July 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記(A)〜(C)のいずれのアプローチにおいても、第３者による中央集権的な集計サーバを必要とする。そのため、集計サーバにデータ処理が集中し、ボトルネックになる可能性がある。
【００１１】
また、従来技術では、第３者による中央集権的な集計サーバを置かない場合、データを秘匿化した状態で集合演算を行えない。例えば、アプローチ(A)の特許文献１の方法では、あるノードに格納されている情報の一部が別のノードに推測されてしまう危険性がある。具体的には、ノードN1には人名K1、K2、K3の３名の人物の購買金額情報が、ノードN2には人名K2、K4、K5の３名の人物の購買金額情報が、ノードN3には人名K1、K3、K4、K5の４名の人物の購買金額情報が格納されていたとする。ここで、ノードN3を集計ノードとし、ノードN1とN2からは、人名をハッシュ関数h()で匿名化してデータを送信することを考えてみる。この場合、ノードN1からはh(K1)、h(K2)、h(K3)のハッシュ値にそれぞれ購買金額情報が付与されて送信されることになるが、集計ノードであるノードN3には、人名K1およびK3が格納されているので、h(K1)とh(K3)の元データが人名K1とK3であることが推測できてしまい、これら２名の購買金額情報がノードN3に知られてしまうことになる。同様に、ノードN2からはh(K2)、h(K4)、h(K5)のハッシュ値にそれぞれ購買金額情報が付与されて送信されることになるが、集計ノードであるノードN3には、人名K4およびK5が格納されているので、これら２名の購買金額情報がノードN3に知られてしまうことになる。さらに、アプローチ(A)の特許文献１とアプローチ(C)の非特許文献１を組み合わせて、購買金額情報を準同型暗号化データとしてノードN3に送信した場合でも、同様の理由でノードN3は少なくとも、ノードN1には人名K1とK3のデータが存在し、ノードN2には人名K4とK5のデータが存在していることが推測できてしまう。また、ノードN1とN2にはそれぞれ３名ずつのデータが格納されていることも、ノードN3は推測できてしまう。
【００１２】
また、アプローチ(B)の特許文献２の問題点は、分散サーバの数が少ないと誤差が大きく、正確な合計が求まらないことである。その理由は、分散サーバの数が少ないと、大数の法則があてはまらなくなるからである。このような誤差を取り除くためには、ノイズを正確に除去する仕組みが必要である。
【００１３】
本発明の目的は、データ統合の処理量を分散できる分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の１視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムであって、第２のノードは、少なくとも、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段とを備え、
第１のノードは、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、を備えている分散型データ統合システムがえられる。
【００１５】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを複合化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段とを備え第１のノードとして機能するようにしてもよい。
【００１６】
本発明の別の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えているノードが得られる。
【００１７】
本発明のさらに別の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムであって、第２のノードは、少なくとも、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段とを備え、第１のノードは、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを含む分散型データ統合システムが得られる。
【００１８】
本発明の他の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段と、を備えているノードが得られる。
【００１９】
また、本発明の１実施形態は、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合方法であって、集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、集計ノードにおいて、秘匿化データの和集合を復号化する処理と、集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を含むことを特徴とする分散型データ統合方法を提供する。
【００２０】
本発明の実施形態の別の視点によれば、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合方法であって、各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、を含むことを特徴とする分散型データ統合方法が得られる。
【００２１】
本発明の別の実施形態は、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させる分散型データ統合プログラムであって、
ノードが集計ノードの場合には、集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、参加ノードから送信される秘匿化データの和集合を受信する処理と、集計ノードにおいて、秘匿化データの和集合を復号化する処理と、集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を実行させ、ノードが参加ノードの場合には、秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の他の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の他の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理とを実行させることを特徴とする分散型データ統合プログラムを提供する。
【００２２】
本発明のさらに他の実施形態によれば、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおいてノードに実行させる分散型統合プログラムであって、各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、を実行させることを特徴とする分散型データ統合プログラムが得られる。
【発明の効果】
【００２３】
本発明は、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用しているため、データ統合の処理量を分散できる。
【００２４】
本発明の実施形態では、要素集合を秘匿化した状態で集合演算を行うので、分散ノード間でデータの集計を行う際にも、他のノードから自ノードが保持しているキー集合や属性集合を推測される心配がない。
【００２５】
本発明の実施形態では、データ秘匿化のために、文字列撹乱、要素数撹乱、数値撹乱で加えたノイズを正確に除去することができるから、分散サーバの数が少なくても、正確な統合データを求めることができる。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】本発明の第１の実施の形態の要素集合データの流れを示すプロトコル図である。
【図４】本発明の第２の実施の形態の構成を示すブロック図である。
【図５】本発明の第２の実施の形態の要素集合データの流れを示すプロトコル図である。
【図６】本発明の第３の実施の形態の構成を示すブロック図である。
【図７】本発明の第３の実施の形態の動作を示す流れ図である。
【図８】本発明の第３の実施の形態の秘匿化数値合計計算処理の動作を示す流れ図である。
【図９】本発明の第３の実施の形態の秘匿化キー和集合演算処理の流れを示すプロトコル図である。
【図１０】本発明の第３の実施の形態の秘匿化数値合計計算処理の流れを示すプロトコル図である。
【図１１】本発明の第３の実施の形態で最終的に統合されるテーブルデータの例を示す。
【図１２】本発明の第４〜６の実施の形態の構成を示すブロック図である。
【発明を実施するための形態】
【００２７】
次に、発明の実施形態について図面を参照して詳細に説明する。
【００２８】
図１を参照すると、本発明の第１の実施の形態におけるノードは、プログラム制御により動作する処理装置１と、ハードディスクやフラッシュメモリなどの記憶装置２とを備える。ノードN1の処理装置１は、通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４とを含む。また、ノードN2およびN3の処理装置１は、通信手段１１と要素集合秘匿化手段１２のみを含む。また、全てのノードN1〜N3の記憶装置２は、要素集合記憶部２１を含む。さらに、３台のノードN1〜N3がネットワーク３を介して接続されている。
【００２９】
通信手段１１は、ネットワーク３を介して他のノードと通信を行う。
【００３０】
要素集合秘匿化手段１２は、各ノードが保持している要素集合の集合演算を行う際に、各要素の秘匿化を行う。具体的には、i番目のノードNiのm個の文字列の集合STR={str_1, str_2, str_3, ..., str_m}に対し、それぞれの文字列の末尾にあらかじめ定められた長さLの固定長ダミー文字列D={d_1, d_2, d_3, ..., d_m}を付加することによって、文字列撹乱した上で、１番目のノードN1の公開鍵を用いて公開鍵暗号方式で暗号化を行う。すなわち、m個の数列E1(STR) = {E1(str_1.d_1), E1(str_2.d_2), E1(str_3.d_3), ..., E1(str_m.d_m)}を求める。ここで、E1(x)はノードN1の公開鍵で文字列xを暗号化する関数であり、「．」は前後の文字列を接続する演算子であるとする。公開鍵暗号方式にはRSA暗号、ElGamal暗号、Paillier暗号などがあり、あらかじめノード間でどの暗号方式を用いるかを定めてあれば、いずれの方式を利用してもかまわない。
【００３１】
さらに、要素集合秘匿化手段１２は、長さLのr個の固定長ダミー文字列D'={d_m+1, d_m+2, d_m+3, ..., d_m+r}に対しても同じ公開鍵暗号方式で暗号化を行うことによって、要素数撹乱も行う。ここで、rは毎回乱数で決める。
【００３２】
以上の操作により、ノードN1以外のノードはノードNiが保持している文字列そのものの情報や文字列の数に関して推測できなくなる。
【００３３】
一方、ノードN1は、これらのデータが送信されてきた場合、自分の秘密鍵D1を使って元の文字列を正確に復元できる。例えば、送信されてきたデータが、E1(str_1.d_1)であったとすると、D1(E1(str_1.d_1))より、文字列str_1.d_1を得る。ここで、後ろのダミー文字列の長さは固定長Lなので、末尾のL文字分を消去すればstr_1が復元できる。また、ダミー文字列だけが暗号化されたデータE1(d_m+1)が送信されてきたとすると、D1(E1(d_m+1))より、d_m+1を得る。この場合、末尾のL文字分を消去すると空文字列になるため、送信されてきたデータはダミー文字列のみであったことが分かる。
【００３４】
復号化手段１３は、暗号化されたデータを復号化する。具体的には、データxをi番目のノードNiの公開鍵で暗号化したEi(x)に対してノードNiの復号化関数Di()を適用し、Di(Ei(x)) = xを得る。
【００３５】
ダミー文字列除去手段１４は、復号化されたデータからダミー文字列を除去する。要素集合秘匿化手段１２は、あらかじめ定められた長さLの固定長のダミー文字列を各要素の末尾に付与していることが分かっているので、復号化することによって得られた文字列の末尾L文字を削除すれば良い。また、末尾L文字を削除した結果が空文字列になった場合は、ダミーの文字列のみからなる要素数撹乱のためのデータであり、無視すればよい。これによって、文字列撹乱と要素数撹乱の効果を正確に取り除くことができる。
【００３６】
次に、図１、図２及び図３を用いて、本実施の形態の動作について詳細に説明する。
【００３７】
図２は、本実施の形態における集合演算のための動作を表す流れ図である。また、図３は、本実施の形態における各ノードが持つ要素集合記憶部２１の例と、データの流れを表すプロトコル図である。図３を参照すると、ノードN1には要素集合K_N1 = {K1, K2, K3}が、ノードN2には要素集合K_N2 = {K2, K4, K5}が、ノードN3には要素集合K_N3 = {K1, K3, K4, K5}が格納されていることが分かる。
【００３８】
以下、データ統合に参加するノードの一つであるノードN1を集計ノードと決定したと仮定して、処理の流れを説明する。
【００３９】
まず、処理対象のノードのポインタiを1に設定する（図２のステップS111）。次に、i+1番目のノードが存在していれば（図２のステップS112）、通信手段１１を使ってノードNiからノードNi+1に対して要素集合秘匿化手段１２で秘匿化されたテーブルのキーの要素集合を送信する（図２のステップS113）。図３では、ノードN1における要素集合秘匿化手段１２は、ノードN1における要素集合K_N1 = {K1, K2, K3}を秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15)}に変換してノードN2に送信している。この時、ノードN2はこれらの秘匿化要素集合を受け取っても、元データであるK1、K2、K3や、ノードN1が保持しているテーブルのキーの数を推測することはできない。
【００４０】
次に、処理対象のノードのポインタiを1増加させ（図２のステップS114）、再度、i+1番目のノードが存在しているかチェックし（図２のステップS112）、存在していれば通信手段１１を使ってノードNiからノードNi+1に対し、ノードNi-1から送信された秘匿化要素集合と、ノードNiにおける要素集合秘匿化手段１２で秘匿化した要素集合の和集合を送信する（図２のステップS113）。図３では、ノードN2はノードN1から秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15)}を受け取っており、さらに、ノードN2における要素集合K_N2 = {K2, K4, K5}をノードN2における要素集合秘匿化手段１２によって秘匿化要素集合{E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}に変換し、両者の秘匿化要素集合の和集合である{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}をノードN3に送信している。この時、ノードN3はこれらの秘匿化要素集合を受け取っても、元データであるK1、K2、K3、K4、K5や、ノードN1およびN2が保持しているテーブルのキーの数を推測することはできない。また、秘匿化要素集合のどの要素がノードN1に由来し、どの要素がノードN2に由来するかを推測することもできない。
【００４１】
さらに、処理対象のノードのポインタiを１増加させ（図２のステップS114）、再度、i+1番目のノードが存在しているかチェックする（図２のステップS112）。iが３の場合は、ノードN4は存在しないため、通信手段１１を使ってノードNiからノードN1に対して、ノードNi-1から受け取った秘匿化要素集合にノードNiにおけるテーブルのキー集合を要素集合秘匿化手段１２で秘匿化した集合を加えた集合を送信する（図２のステップS115）。図３では、ノードN3は、ノードN2から受け取った秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}に加えて、ノードN3における要素集合K_N3 = {K1, K3, K4, K5}をノードN3における要素集合秘匿化手段１２によって秘匿化要素集合{E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}に変換し、両者の秘匿化要素集合をあわせた{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26), E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}をノードN1に送信している。この時、ノードN1はこれらの秘匿化要素集合を受け取っても、ノードN2およびN3が保持しているテーブルのキーの数を推測することはできない。また、秘匿化要素集合のどのデータがノードN2に由来し、どのデータがノードN3に由来するかを推測することもできない。
【００４２】
次に、ノードN1は、自分の秘密鍵を用いた復号化D1を行い、秘匿化要素集合の復号化データの集合を得る（図２のステップS116）。図３で、ノードN1は{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26), E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}を受け取っているので、復号化すると、復号化要素集合として、{K1.D11, K2.D12, K3.D13, D14, D15, K2.D21, K4.D22, K5.D23, D24, D25, D26, K1.D31, K3.D32, K4.D33, K5.D34, D35}を得る。
【００４３】
次に、ノードN1は、得られた復号化要素集合から文字列撹乱と要素数撹乱で加えられているダミー文字列を除去する（図２のステップS117）。この処理は、復号化要素集合の各文字列の末尾L文字を削除することで達成される。図３の例の場合、この処理により、ダミー文字列除去後の多重集合として{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}を得る。この時点も、ノードN1はこれらの要素がノードN2とN3のどちらに由来しているのかは推測できない。
【００４４】
次に、ノードN1は、得られたダミー文字列除去後の多重集合から重複を除いた和集合を演算する（図２のステップS118）。図３の例の場合、これにより、全ノードN1〜N3が格納している要素集合の和集合として{K1, K2, K3, K4, K5}を得ることができる。こうして、ノードN1、N2、N3も、自分のデータでないものは、他のどのノードに由来しているかを推測できないまま、全てのノードのテーブルキーの和集合を求めることができる。
【００４５】
次に、ノードN1は、得られたテーブルキー和集合を他のノードN2、N3に一斉送信する（図２のステップS119）。
【００４６】
上記説明では、説明を簡単にするため、各ノードの要素集合秘匿化手段１２は、要素集合の順番をそのまま残した形で秘匿化を行っていたが、実際は要素の順番を変えたり、ダミーの要素を間に入れたりすることも考えられ、本実施の形態に述べた方法に限定されない。この場合、例えば、図３でノードN2からノードN3に送信される秘匿化要素集合の順序は、{E1(K2.D12), E1(D26), E1(D14), E1(D15), E1(K2.D21), E1(K1.D11), E1(K4.D22), E1(D24), E1(D25), E1(K3.D13), E1(K5.D23)}のように、ランダムに入れ替わっていても良い。
【００４７】
また、上記説明では、説明を簡単にするため、各ノードの要素集合をそのまま使っているが、人名が外に対して明らかになると困る場合は、ハッシュ関数h()を使って、ノードN1の要素集合をh(K_N1) = {h(K1), h(K2), h(K3)}、ノードN2の要素集合をh(K_N2) = {h(K2), h(K4), h(K5)}、ノードN3の要素集合をh(K_N3) = {h(K1), h(K3), h(K4), h(K5)}、として、図２に示す秘匿化和集合演算処理を行ってもよく、本実施の形態に述べた方法に限定されない。この場合、自分のテーブルに登録されているキー以外はハッシュ値としてしか認識されず、より秘匿性の高いデータ統合方式となる。
【００４８】
また、上記説明では、説明を簡単にするため、要素集合秘匿化手段１２は、各要素の文字列の末尾にあらかじめ定められた長さLの固定長ダミー文字列を付加する方法について述べたが、あらかじめダミー文字列の付与ルールが決められており、ダミー文字列除去手段１４によって正確にダミー文字列を除去できるのであれば、別の方法であってもかまわない。例えば、長さLの固定長のダミー文字列を先頭に付加してもよいし、要素の文字列の奇数番目に固定長のダミー文字列を挿入するという方法も考えられる。後者の場合、元の文字列が"ABCDEFG"で、長さ１のダミー文字列を奇数番目に挿入したとすると、"zA2B3CaD1F8G"という文字列が生成されるので、ダミー文字列除去手段１４は奇数番目の文字列を除去すれば元の文字列"ABCDEFG"が再現できる。
【００４９】
また、上記説明では、説明を簡単にするため、ダミー文字列除去後の多重集合として{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}から和集合を求める方法について述べたが、他にも、出現頻度や積集合などの他の集合演算も可能であり、本実施の形態に述べた方法に限定されない。出現頻度の演算は、単に多重集合内の各要素の出現頻度を計数するだけでよい。例えば、多重集合{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}から、各要素の出現頻度は(K1, K2, K3, K4, K5) = (2, 2, 2, 2, 2)と求まる。さらに、積集合は出現頻度がノードの数に等しい要素を抽出することによって求めることができる。例えば、ノードN1〜N3が格納している要素集合の多重集合が{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}の場合、各要素の出現頻度は(K1, K2, K3, K4, K5) = (2, 2, 2, 2, 2)であるので、積集合は空集合となる。
【００５０】
また、上記説明では、説明を簡単にするため、３台のノードがデータ統合に参加する場合について述べたが、３台以上のノードが参加する場合も考えられ、本実施の形態で述べた方法に限定されない。
【００５１】
本実施の形態では、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用している。そのため、第３者による中央集権的な集計サーバは不要である。
【００５２】
また、本実施の形態では、要素集合秘匿化手段によってデータを秘匿化した状態で集合演算を行うことができる。そのため、ノード間でデータの和集合を求める際にも、他のノードからデータを推測される心配がなくなる。
【００５３】
また、本実施の形態では、データ秘匿化のために、文字列撹乱、要素数撹乱で加えたノイズを正確に除去することができる。そのため、分散サーバの数が少なくても、正確な統合データを求めることができる。
【００５４】
次に本発明の第２の実施の形態について、図面を参照して詳細に説明する。
【００５５】
図４を参照すると、本発明の第２の実施の形態は、図１に示された第１の実施の形態の構成における、ノードN2およびノードN3の処理装置１が、復号化手段１３およびダミー文字列除去手段１４を備えている点で異なる。この場合、全てのノードの機能は等価であるので、ノードのIDを読み替えることによって、任意のノードを集計ノードとして集合演算を行うことができる。
【００５６】
例えば、図５のようにノードN1に２種類の要素集合K_N1 = {K1, K2, K3}とA_N1 = {A1, A2}、ノードN2に２種類の要素集合K_N2 = {K2, K4, K5}とA_N2 = {A1, A3, A4}、ノードN3に２種類の要素集合K_N3 = {K1, K3, K4, K5}とA_N3 = {A1, A2, A5}が格納されている場合、第１の実施の形態と同じ方法で要素集合K_N1、K_N2、K_N3の和集合をノードN1を集計ノードとして求めるのと同時に、要素集合A_N1、A_N2、A_N3の和集合をノードN2を集計ノードとして並列に求めることができる。また、集計ノードをラウンドロビン式に決定したり、乱数により決定することによって、集計処理が特定ノードに集中することを防ぎ、負荷を分散することできる。なお、図５で、E2()は、ノードN2の公開鍵である。
【００５７】
本実施の形態では、データ統合に参加する任意のノードが集計ノードの役割を果たすことができる。そのため、集計処理を並列化させ、負荷を分散させることができる。
【００５８】
次に本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【００５９】
図６を参照すると、本発明の第３の実施の形態におけるノードは、第２の実施の形態におけるノードの処理装置１の構成に、数値秘匿化手段１５と数値ノイズ除去手段１６が加わっている。また、記憶装置２が要素集合記憶部２１の代わりにテーブル記憶部２２を備える。
【００６０】
数値秘匿化手段１５は、各ノードが保持している数値データの合計を演算する際に、各数値データの秘匿化を行う。具体的には、i番目のノードNiは、数値データv_iに対し、十分大きなモジュラー数Xに乱数R_iをかけたものを加え、数値撹乱した上で、加法準同型性を持つ公開鍵暗号方式を用いて、ノードN1の公開鍵を用いて計算結果を暗号化する。すなわち、E1(v_i+X*R_i)を求める。加法準同型性を持つ公開鍵暗号方式には、Paillier暗号、modified-ElGamal暗号などがあり、あらかじめノード間でどの暗号方式を用いるかを定めてあれば、いずれの方式を利用してもかまわない。
【００６１】
ここで、十分大きなモジュラー数Xとは全てのノードの数値データの合計よりも大きな数である必要がある。モジュラー数Xの求め方には、例えば、次のような方法が考えられる。
【００６２】
(1)各ノードの数値データに正の乱数を足した数をお互いブロードキャストする
(2)ブロードキャストされた数値の最大値にノード数をかけて１を足す
これにより、データ統合に参加する分散ノードは自分の数値データを公開することなく、モジュラー数Xを決定することができる。
【００６３】
なお、ここでは、説明を簡単にするために、各ノードの数値データに正の乱数を足した数をお互いブロードキャストし、ブロードキャストされた数値の最大値にノード数をかけて１を足すことによってモジュラー数Xを決定する方法について説明したが、他にも、各ノードの数値データよりも大きな乱数を順に足しこんでいくことによってモジュラー数Xを決定する方法もあり、本実施の形態で述べた方法に限定されない。この場合、ノードN1がノードN1の数値データv_1よりも大きな乱数r_1をノードN2に対して送信し、ノードN2はノードN2の数値データv_2よりも大きな乱数r_2をr_1に加えたr_1+r_2をノードN3に送信し、ノードN3はノードN3の数値データv_3よりも大きな乱数r_2をr_1+r_2に加えたr_1+r_2+r_3をモジュラー数Xとし、ノードN1とN2に通知する。一般的に、ノード数がN台の場合は、r_1+r_2+r_3+...+r_NとN個の乱数を足し合わせたものをモジュラー数Xとすればよい。
【００６４】
数値秘匿化手段１５は、また、自ノードの秘匿化数値データと、他のノードからの秘匿化数値データの積をとり、
E(x1)*E(x2) = E(x1 + x2)
に該当する計算を行う。
【００６５】
数値ノイズ除去手段１６は、復号化された数値データをモジュラー数Xで割った余りを求めることによって、数値撹乱のためにノイズとして加算したモジュラーXと乱数R_iの積X*R_iを除去する。
【００６６】
次に、図６及び図７〜図１１を用いて、本実施の形態の動作について詳細に説明する。
【００６７】
図７は、本実施の形態における動作を表す流れ図である。
【００６８】
まず、データ統合に参加する各ノードは自分が保有するテーブルのキーKを秘匿化した上で、秘匿化和集合演算処理によって、ノード全体でのテーブルのキーKの和集合を求める（図７のステップS101）。図９では、ノードN1のテーブルのキー集合は{K1, K2, K3}、ノードN2のテーブルのキー集合は{K2, K4, K5}、ノードN3のテーブルのキー集合は{K1, K3, K4, K5}の場合の例を示している。また、各テーブルのセルは、単一の要素又は複数の要素からなる要素集合をその構成としている。ノードN1について述べると、セル(K1, A1), (K2, A1), (K3, A1)は、それぞれ要素集合として単一の要素の数値｛12｝,｛4｝,｛7｝を内容としている。セル(K1, A2)は要素集合{a, b}が、セル(K2, A2), (K3, A3)は、それぞれ要素集合として単一要素の文字｛c｝,｛d｝がその内容となっている。
【００６９】
秘匿化和集合演算処理は、第１の実施の形態で述べた図２のステップS111〜S119と同一であるため、ここでは説明を省略する。各ノードのテーブルが図９のようになっている場合、ノードN1〜N3はお互いの保有する属性に関する情報を推測することなく、キーKの和集合として{K1, K2, K3, K4, K5}を得ることができる。
【００７０】
ノード全体でのテーブルのキーKの和集合が求まると、各ノードは自分のノードで、どのキーのデータが欠落しているかを知ることができるので、テーブルに欠落していたキーを追加し、デフォルトの値を設定する。デフォルトの値としては、数値データの場合は０に、文字列データの場合は空文字列に、集合データの場合は空集合に設定すればよい。
【００７１】
次に、データ統合に参加する各ノードは自分が保有するテーブルの属性Aを秘匿化した上で、秘匿化和集合演算処理によって、ノード全体での属性Aの和集合を求める（図２のステップS102）。この場合の秘匿化和集合演算処理も、第１の実施の形態で述べた図２のステップS111〜S119と同一であるため、ここでは説明を省略する。各ノードのテーブルが図９のようになっている場合、ノードN1〜N3はお互いの保有する属性に関する情報を推測することなく、属性Aの和集合として{A1, A2, A3}を得ることができる。この段階で、全てのノードのキーと属性が揃ったことになる。
【００７２】
ノード全体でのテーブルの属性Aの和集合が求まると、各ノードは自分のノードで、どの属性のデータが欠落しているかを知ることができるので、テーブルに欠落していた属性を追加し、デフォルトの値を設定する。デフォルトの値としては、数値データの場合は０に、文字列データの場合は空文字列に、集合データの場合は空集合に設定すればよい。
【００７３】
各ノードの初期のテーブルが図９のようになっていた場合、各ノードが欠落していたキーと属性を追加し、デフォルトの値を設定した例を図１０に示す。図１０を見ると、図９でノードN1に欠落していたキーK4、K5と属性A3が追加され、それぞれの行列に対して、数値データには０が、集合データには空集合が設定されていることが分かる。また、図９でノードN2に欠落していたキーK1とK3の行が追加され、数値データには０が、集合データには空集合が設定されていることが分かる。さらに、図９でノードN3に欠落していたキーK2の行が追加され、数値データには０が、集合データには空集合が設定されていることが分かる。
【００７４】
次に、データ統合に参加する各ノードは、テーブルのスキャンを開始するために、キーポインタKpの値をK1に、属性ポインタApの値をA1に設定する（図７のステップS103）。キーポインタKpと属性ポインタApで指定されるセルの値が数値データであった場合（図７のステップS104）、秘匿化数値合計計算処理によって、そのセルの数値データを秘匿化した上で合計を計算する（図７のステップS105）。
【００７５】
図８は、秘匿化数値合計計算処理の動作を表す流れ図である。
【００７６】
秘匿化数値合計計算処理では、まず、処理対象のノードのポインタiを１に設定する（図８のステップS121）。次に、i+1番目のノードが存在していれば（図８のステップS122）、通信手段１１を使ってノードNiからノードNi+1に対して数値秘匿化手段１５で秘匿化された数値データを送信する（図８のステップS123）。
【００７７】
図１０に、具体的なテーブルとデータの流れの模式図を示す。図１０では、ノードN1のテーブルのセルの値は１２であり、これをV1_11と記述することにする。また、図１０では、ノードN1における数値秘匿化手段１５は、V1_11にモジュラー数Xと乱数R1の積を足したV1_11+X*R1を計算した上で、ノードN1の公開鍵で暗号化し、E1(V1_11+X*R1)をノードN2に送信する。この時、ノードN2はこれらの秘匿化数値データを受け取っても、元データであるV1_11を推測することはできない。
【００７８】
次に、処理対象のノードのポインタiを1増加させ（図８のステップS124）、再度、i+1番目のノードが存在しているかチェックし（図８のステップS122）、存在していれば通信手段１１を使ってノードNiからノードNi+1に対し、ノードNi-1から送信された秘匿化数値データと、ノードNiにおける数値秘匿化手段１５で秘匿化した数値データの積を送信する（図８のステップS123）。図１０では、ノードN2はノードN1から秘匿化数値データE1(V1_11+X*R1)に、さらに、ノードN2におけるセルの数値データV2_11 = 0をノードN2における数値秘匿化手段１５によって秘匿化された数値データE1(V2_11+X*R2)の積をとって、ノードN3に送信している。この時、ノードN3に送信される秘匿化数値データはE1(V1_11+X*R1)*E1(V2_11+X*R2)であるが、これは、E1(V1_11+V2_11+X*(R1+R2))に等しい。この時、ノードN3はこれらの秘匿化数値データを受け取っても、元データであるV1_11やV2_11を推測することはできない。
【００７９】
さらに、処理対象のノードのポインタiを１増加させ（図８のステップS124）、再度、i+1番目のノードが存在しているかチェックする（図8のステップS122）。iが3の場合は、ノードN4は存在しないため、通信手段１１を使ってノードNiからノードN1に対して、ノードNi-1から受け取った秘匿化数値データに、Niにおける数値秘匿化手段１５で秘匿化した数値データの積を送信する（図８のステップS125）。図１０では、ノードN3は、ノード2から受け取った秘匿化数値データE1(V1_11+X*R1)*E1(V2_11+X*R2)に、ノードN3におけるセルの数値データV3_11 = 5を数値秘匿化手段１５によって秘匿化された数値データE1(V3_11+X*R3)を掛けた、E1(V1_11+X*R1)*E1(V2_11+X*R2)*E1(V3_11+X*R3) = E1(V1_11+V2_11+V3_11+X*(R1+R2+R3))をノードN1に送信している。この時、ノードN1はこの秘匿化数値データを受け取っても、ノードN2およびN3のセルの数値データV2_11、V3_11を推測することはできない。
【００８０】
次に、ノードN1は、自分の秘密鍵を用いた復号化D1を行い、秘匿化数値データの復号化データを得る（図８のステップS126）。図１０で、ノードN1はE1(V1_11+V2_11+V3_11+X*(R1+R2+R3))を受け取っているので、復号化すると、復号化数値データとして、V1_11+V2_11+V3_11+X*(R1+R2+R3)を得る。
【００８１】
次に、ノードN1は、得られた復号化数値データから数値撹乱で加えられているノイズを除去する（図８のステップS127）。この処理は、復号化数値データをモジュラー数Xで割った余りを計算することで達成される。図１０の例の場合、この処理により、ノイズ除去後の数値データとしてV1_11+V2_11+V3_11を得る。この時も、ノードN1はこれらの数値データがノードN2とN3のどちらにどれだけ由来しているのかは推測できない。こうして、ノードN1、N2、N3も、自分のデータでないものは、どのノードに由来しているか推測できないまま、全てのノードのセルの数値データの合計を求めることができた。
【００８２】
次に、ノードN1は、得られた数値データの合計を他のノードN2、N3に一斉送信する（図８のステップS128）。これにより、各ノードは自分のノードの該当セルの値を修正する。
【００８３】
次に、データ統合に参加する各ノードはさらに別のセルをスキャンし、未処理のセルがあればそのセルの位置をキーポインタKp、属性ポインタApにセットし（図７のステップS107）、セルが数値データか否かを判定する（図７のステップS104）。例えば、キーポインタKpがK1〜K5まで変化し、属性ポインタApがA1のままだった場合、図１０のテーブルの属性A1の列をスキャンしながら統合することになる。
【００８４】
また、セルが数値データでなかった場合（図７のステップS104）、セルの値を集合として秘匿化データ和集合演算処理によって、セルの値の和集合を求める（図７のステップS106）。この処理の詳細も１1の実施の形態で説明した方法と同じであり、テーブルのキーの和集合や、属性の和集合を求める方法と同様である。各ノードのデータが図１０のようになっている場合、ノードN1〜N3のセルの値の和集合として{a,b}を得ることができる。
【００８５】
さらに、未処理のセルがあればそのセルの位置をキーポインタKp、属性ポインタApにセットして統合処理を続け（図７のステップS107）、未処理のセルがなくなったら統合処理が終了する。この時、ノードN1〜N3で統合されたテーブルは図１１のように全て同じ値を持つ。
【００８６】
なお、ここでは、説明を簡単にするためキーポインタKp、属性ポインタApを個別に設定してセルを１つずつ統合していく方法について説明したが、テーブルの列または行方向をひとまとめとして、１行ずつ、あるいは１列ずつ統合処理する方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８７】
さらに、ここでは、説明を簡単にするため、常にノードN1からデータの送信が開始され、最後にノードN1でデータが復元される方法について説明したが、他にも、ラウンドロビン式にデータの送信開始と復元するノードを割り当て、並列に処理する方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８８】
また、ここでは、各セルについて統合データが得られる度にそのセルを修正する方法について説明したが、他にも、各ノードが初期のテーブルとは独立に統合テーブルを保持し、統合データは統合テーブルに格納するなどの方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８９】
本実施の形態では、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用している。そのため、中央集権的な集計サーバは不要であり、データが集中することによるボトルネックの問題を解消できる。
【００９０】
また、本実施の形態では、要素集合秘匿化手段によってデータを秘匿化した状態で和集合を求めることができる。そのため、分散ノード間でデータの集計を行う際にも、他のノードからデータを推測される心配がなくなる。
【００９１】
また、本実施の形態では、データ秘匿化のために、文字列撹乱、要素数撹乱、数値撹乱で加えたノイズを正確に除去することができる。そのため、分散サーバの数が少なくても、正確な統合データを求めることができる。
【００９２】
次に、本発明の第４の実施の形態について、図面を参照して詳細に説明する。
【００９３】
図１２を参照すると本発明の第４の実施の形態は、入力手段５０１、データ処理装置５０２、出力手段５０３、記憶装置５０４を備える。さらに、第１の実施の形態の分散型秘匿化データ統合装置を実現するための分散型秘匿化データ統合プログラム５００を備える。
【００９４】
入力手段５０１は、マウス、キーボード等、操作者からの指示を入力するための装置である。また、出力手段５０３は、表示画面、プリンタ等のデータ処理装置５０２による処理結果を出力する装置である。
【００９５】
分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第１の実施形態におけるノードN1〜N3の処理装置１と同一の処理を実行する。
【００９６】
図１２におけるデータ処理装置５０２は、図１における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４の処理を実行し、図１２における記憶装置５０４には、図１における要素集合記憶部２１、の情報が格納される。
【００９７】
次に、本発明の第５の実施の形態について、図面を参照して詳細に説明する。
【００９８】
第５の実施の形態は、第４の実施の形態と同様に図１２の構成図を用いる。分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第２の実施形態における処理装置２と同一の処理を実行する。
【００９９】
図１２におけるデータ処理装置５０２は、図４における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４の処理を実行し、図１２における記憶装置５０４には、図４における要素集合記憶部２１の情報が格納される。
【０１００】
次に、本発明の第６の実施の形態について、図面を参照して詳細に説明する。
【０１０１】
第６の実施の形態は、第４の実施の形態と同様に図１２の構成図を用いる。分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第２の実施形態における処理装置２と同一の処理を実行する。
【０１０２】
図１２におけるデータ処理装置５０２は、図６における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４、数値秘匿化手段１５、数値ノイズ除去手段１６の処理を実行し、図１２における記憶装置５０４には、図６におけるテーブル記憶部２２の情報が格納される。
【産業上の利用可能性】
【０１０３】
本発明は、異なる企業間における顧客データのデータマイニングや、異なる国における人脈データの統合などに適用が可能である。
【符号の説明】
【０１０４】
１ 処理装置
２ 記憶装置
３ ネットワーク
１１ 通信手段
１２ 要素集合秘匿化手段
１３ 復号化手段
１４ ダミー文字列除去手段
１５ 数値秘匿化手段
１６ 数値ノイズ除去手段
２１ 要素集合記憶部
２２ テーブル記憶部
【技術分野】
【０００１】
本発明は、分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムに関し、特に中央集権型の集計サーバを必要とせず、かつ、統合対象となるテーブルのキー、属性、および生データをお互いに推測されることなく統合することが可能な分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムに関する。
【背景技術】
【０００２】
近年、顧客の購買履歴等から有用な知識を抽出する仕組みとしてデータマイニングの重要性が高まっている。特に、複数の企業が持つデータを統合することによって、より広範囲で深い消費者行動に関する知識が得られるものと期待されている。一方で、個人情報保護の観点から、複数の企業が生の顧客データをそのまま公開して統合データを構築するわけにはいかず、プライバシーを保護しながらデータマイニングを行う手法が必須である。
【０００３】
分散サーバに格納されている分散データを秘匿化して統合する従来技術は、大きく以下の３通りのアプローチに分類できる。
(A)ハッシュ関数を使った匿名IDの利用
(B)乱数によるノイズを用いたデータ撹乱
(C)準同型暗号による電子投票プロトコル
【０００４】
(A)のハッシュ関数を使った匿名IDの利用とは、人名のような特定の個人を識別可能な識別情報に対してハッシュ関数を用いて元の識別情報を類推しにくい匿名IDを生成し、匿名IDを用いて顧客データを統合・管理する方法である。特許文献1では、個人IDをハッシュ関数を用いて匿名IDを生成し、匿名IDをキーとして個人の購買履歴データを収集することによって、特定の個人IDと購買履歴データが結びつかない状態で購買商品や金額の集計する方法が開示されている。
【０００５】
(B)の乱数によるノイズを用いたデータ撹乱とは、集計対象となる数値データに対して乱数によるノイズを加えることによって撹乱データを生成し、個別のデータの内容を秘匿化する方法である。特許文献２では、あらかじめ撹乱データに含まれるノイズの統計的分布を決めておき、撹乱データの合計を計算した後にノイズの平均値を除去することによって、近似的に生データの合計を得る方法が開示されている。
【０００６】
(C)の準同型暗号による電子投票プロトコルとは、暗号化によってデータを秘匿化するとともに、秘匿化されたデータ同士を演算することによって、元のデータの演算も行うことができる方法である。このような暗号方式の例として、加法準同型暗号を持つ、Paillier暗号が挙げられる。Paillier暗号では、メッセージx1に対する暗号化e(x1)と、メッセージx2に対する暗号化e(x2)の間に、以下のような関係が成り立っており、これを加法準同型性と呼ぶ。
e(x1) * e(x2) = e(x1 + x2)
【０００７】
非特許文献１では、この準同型性を利用して、データ入力ノードから暗号化された数値データを集計サーバに送信し、集計サーバで受信したデータの積を計算し、その結果を管理サーバ側で復号化することによって、データ入力ノードに入力された数値の合計を求める方法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−３０１９７８
【特許文献２】特開２００７−２８８４８０
【非特許文献】
【０００９】
【非特許文献１】谷川浩司、中西透、舩曵信生、プライバシーを保護した授業評価アンケートの実装、電子情報通信学会技術研究報告、ISEC2006-59、pp. 145-151、July 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記(A)〜(C)のいずれのアプローチにおいても、第３者による中央集権的な集計サーバを必要とする。そのため、集計サーバにデータ処理が集中し、ボトルネックになる可能性がある。
【００１１】
また、従来技術では、第３者による中央集権的な集計サーバを置かない場合、データを秘匿化した状態で集合演算を行えない。例えば、アプローチ(A)の特許文献１の方法では、あるノードに格納されている情報の一部が別のノードに推測されてしまう危険性がある。具体的には、ノードN1には人名K1、K2、K3の３名の人物の購買金額情報が、ノードN2には人名K2、K4、K5の３名の人物の購買金額情報が、ノードN3には人名K1、K3、K4、K5の４名の人物の購買金額情報が格納されていたとする。ここで、ノードN3を集計ノードとし、ノードN1とN2からは、人名をハッシュ関数h()で匿名化してデータを送信することを考えてみる。この場合、ノードN1からはh(K1)、h(K2)、h(K3)のハッシュ値にそれぞれ購買金額情報が付与されて送信されることになるが、集計ノードであるノードN3には、人名K1およびK3が格納されているので、h(K1)とh(K3)の元データが人名K1とK3であることが推測できてしまい、これら２名の購買金額情報がノードN3に知られてしまうことになる。同様に、ノードN2からはh(K2)、h(K4)、h(K5)のハッシュ値にそれぞれ購買金額情報が付与されて送信されることになるが、集計ノードであるノードN3には、人名K4およびK5が格納されているので、これら２名の購買金額情報がノードN3に知られてしまうことになる。さらに、アプローチ(A)の特許文献１とアプローチ(C)の非特許文献１を組み合わせて、購買金額情報を準同型暗号化データとしてノードN3に送信した場合でも、同様の理由でノードN3は少なくとも、ノードN1には人名K1とK3のデータが存在し、ノードN2には人名K4とK5のデータが存在していることが推測できてしまう。また、ノードN1とN2にはそれぞれ３名ずつのデータが格納されていることも、ノードN3は推測できてしまう。
【００１２】
また、アプローチ(B)の特許文献２の問題点は、分散サーバの数が少ないと誤差が大きく、正確な合計が求まらないことである。その理由は、分散サーバの数が少ないと、大数の法則があてはまらなくなるからである。このような誤差を取り除くためには、ノイズを正確に除去する仕組みが必要である。
【００１３】
本発明の目的は、データ統合の処理量を分散できる分散型秘匿化データ統合装置、分散型秘匿化データ統合方法および分散型秘匿化データ統合用プログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の１視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムであって、第２のノードは、少なくとも、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段とを備え、
第１のノードは、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、を備えている分散型データ統合システムがえられる。
【００１５】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを複合化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段とを備え第１のノードとして機能するようにしてもよい。
【００１６】
本発明の別の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えているノードが得られる。
【００１７】
本発明のさらに別の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムであって、第２のノードは、少なくとも、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段とを備え、第１のノードは、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを含む分散型データ統合システムが得られる。
【００１８】
本発明の他の視点によれば、少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段と、を備えているノードが得られる。
【００１９】
また、本発明の１実施形態は、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合方法であって、集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、集計ノードにおいて、秘匿化データの和集合を復号化する処理と、集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を含むことを特徴とする分散型データ統合方法を提供する。
【００２０】
本発明の実施形態の別の視点によれば、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合方法であって、各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、を含むことを特徴とする分散型データ統合方法が得られる。
【００２１】
本発明の別の実施形態は、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させる分散型データ統合プログラムであって、
ノードが集計ノードの場合には、集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、参加ノードから送信される秘匿化データの和集合を受信する処理と、集計ノードにおいて、秘匿化データの和集合を復号化する処理と、集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を実行させ、ノードが参加ノードの場合には、秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の他の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の他の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理とを実行させることを特徴とする分散型データ統合プログラムを提供する。
【００２２】
本発明のさらに他の実施形態によれば、少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおいてノードに実行させる分散型統合プログラムであって、各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、を実行させることを特徴とする分散型データ統合プログラムが得られる。
【発明の効果】
【００２３】
本発明は、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用しているため、データ統合の処理量を分散できる。
【００２４】
本発明の実施形態では、要素集合を秘匿化した状態で集合演算を行うので、分散ノード間でデータの集計を行う際にも、他のノードから自ノードが保持しているキー集合や属性集合を推測される心配がない。
【００２５】
本発明の実施形態では、データ秘匿化のために、文字列撹乱、要素数撹乱、数値撹乱で加えたノイズを正確に除去することができるから、分散サーバの数が少なくても、正確な統合データを求めることができる。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】本発明の第１の実施の形態の要素集合データの流れを示すプロトコル図である。
【図４】本発明の第２の実施の形態の構成を示すブロック図である。
【図５】本発明の第２の実施の形態の要素集合データの流れを示すプロトコル図である。
【図６】本発明の第３の実施の形態の構成を示すブロック図である。
【図７】本発明の第３の実施の形態の動作を示す流れ図である。
【図８】本発明の第３の実施の形態の秘匿化数値合計計算処理の動作を示す流れ図である。
【図９】本発明の第３の実施の形態の秘匿化キー和集合演算処理の流れを示すプロトコル図である。
【図１０】本発明の第３の実施の形態の秘匿化数値合計計算処理の流れを示すプロトコル図である。
【図１１】本発明の第３の実施の形態で最終的に統合されるテーブルデータの例を示す。
【図１２】本発明の第４〜６の実施の形態の構成を示すブロック図である。
【発明を実施するための形態】
【００２７】
次に、発明の実施形態について図面を参照して詳細に説明する。
【００２８】
図１を参照すると、本発明の第１の実施の形態におけるノードは、プログラム制御により動作する処理装置１と、ハードディスクやフラッシュメモリなどの記憶装置２とを備える。ノードN1の処理装置１は、通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４とを含む。また、ノードN2およびN3の処理装置１は、通信手段１１と要素集合秘匿化手段１２のみを含む。また、全てのノードN1〜N3の記憶装置２は、要素集合記憶部２１を含む。さらに、３台のノードN1〜N3がネットワーク３を介して接続されている。
【００２９】
通信手段１１は、ネットワーク３を介して他のノードと通信を行う。
【００３０】
要素集合秘匿化手段１２は、各ノードが保持している要素集合の集合演算を行う際に、各要素の秘匿化を行う。具体的には、i番目のノードNiのm個の文字列の集合STR={str_1, str_2, str_3, ..., str_m}に対し、それぞれの文字列の末尾にあらかじめ定められた長さLの固定長ダミー文字列D={d_1, d_2, d_3, ..., d_m}を付加することによって、文字列撹乱した上で、１番目のノードN1の公開鍵を用いて公開鍵暗号方式で暗号化を行う。すなわち、m個の数列E1(STR) = {E1(str_1.d_1), E1(str_2.d_2), E1(str_3.d_3), ..., E1(str_m.d_m)}を求める。ここで、E1(x)はノードN1の公開鍵で文字列xを暗号化する関数であり、「．」は前後の文字列を接続する演算子であるとする。公開鍵暗号方式にはRSA暗号、ElGamal暗号、Paillier暗号などがあり、あらかじめノード間でどの暗号方式を用いるかを定めてあれば、いずれの方式を利用してもかまわない。
【００３１】
さらに、要素集合秘匿化手段１２は、長さLのr個の固定長ダミー文字列D'={d_m+1, d_m+2, d_m+3, ..., d_m+r}に対しても同じ公開鍵暗号方式で暗号化を行うことによって、要素数撹乱も行う。ここで、rは毎回乱数で決める。
【００３２】
以上の操作により、ノードN1以外のノードはノードNiが保持している文字列そのものの情報や文字列の数に関して推測できなくなる。
【００３３】
一方、ノードN1は、これらのデータが送信されてきた場合、自分の秘密鍵D1を使って元の文字列を正確に復元できる。例えば、送信されてきたデータが、E1(str_1.d_1)であったとすると、D1(E1(str_1.d_1))より、文字列str_1.d_1を得る。ここで、後ろのダミー文字列の長さは固定長Lなので、末尾のL文字分を消去すればstr_1が復元できる。また、ダミー文字列だけが暗号化されたデータE1(d_m+1)が送信されてきたとすると、D1(E1(d_m+1))より、d_m+1を得る。この場合、末尾のL文字分を消去すると空文字列になるため、送信されてきたデータはダミー文字列のみであったことが分かる。
【００３４】
復号化手段１３は、暗号化されたデータを復号化する。具体的には、データxをi番目のノードNiの公開鍵で暗号化したEi(x)に対してノードNiの復号化関数Di()を適用し、Di(Ei(x)) = xを得る。
【００３５】
ダミー文字列除去手段１４は、復号化されたデータからダミー文字列を除去する。要素集合秘匿化手段１２は、あらかじめ定められた長さLの固定長のダミー文字列を各要素の末尾に付与していることが分かっているので、復号化することによって得られた文字列の末尾L文字を削除すれば良い。また、末尾L文字を削除した結果が空文字列になった場合は、ダミーの文字列のみからなる要素数撹乱のためのデータであり、無視すればよい。これによって、文字列撹乱と要素数撹乱の効果を正確に取り除くことができる。
【００３６】
次に、図１、図２及び図３を用いて、本実施の形態の動作について詳細に説明する。
【００３７】
図２は、本実施の形態における集合演算のための動作を表す流れ図である。また、図３は、本実施の形態における各ノードが持つ要素集合記憶部２１の例と、データの流れを表すプロトコル図である。図３を参照すると、ノードN1には要素集合K_N1 = {K1, K2, K3}が、ノードN2には要素集合K_N2 = {K2, K4, K5}が、ノードN3には要素集合K_N3 = {K1, K3, K4, K5}が格納されていることが分かる。
【００３８】
以下、データ統合に参加するノードの一つであるノードN1を集計ノードと決定したと仮定して、処理の流れを説明する。
【００３９】
まず、処理対象のノードのポインタiを1に設定する（図２のステップS111）。次に、i+1番目のノードが存在していれば（図２のステップS112）、通信手段１１を使ってノードNiからノードNi+1に対して要素集合秘匿化手段１２で秘匿化されたテーブルのキーの要素集合を送信する（図２のステップS113）。図３では、ノードN1における要素集合秘匿化手段１２は、ノードN1における要素集合K_N1 = {K1, K2, K3}を秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15)}に変換してノードN2に送信している。この時、ノードN2はこれらの秘匿化要素集合を受け取っても、元データであるK1、K2、K3や、ノードN1が保持しているテーブルのキーの数を推測することはできない。
【００４０】
次に、処理対象のノードのポインタiを1増加させ（図２のステップS114）、再度、i+1番目のノードが存在しているかチェックし（図２のステップS112）、存在していれば通信手段１１を使ってノードNiからノードNi+1に対し、ノードNi-1から送信された秘匿化要素集合と、ノードNiにおける要素集合秘匿化手段１２で秘匿化した要素集合の和集合を送信する（図２のステップS113）。図３では、ノードN2はノードN1から秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15)}を受け取っており、さらに、ノードN2における要素集合K_N2 = {K2, K4, K5}をノードN2における要素集合秘匿化手段１２によって秘匿化要素集合{E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}に変換し、両者の秘匿化要素集合の和集合である{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}をノードN3に送信している。この時、ノードN3はこれらの秘匿化要素集合を受け取っても、元データであるK1、K2、K3、K4、K5や、ノードN1およびN2が保持しているテーブルのキーの数を推測することはできない。また、秘匿化要素集合のどの要素がノードN1に由来し、どの要素がノードN2に由来するかを推測することもできない。
【００４１】
さらに、処理対象のノードのポインタiを１増加させ（図２のステップS114）、再度、i+1番目のノードが存在しているかチェックする（図２のステップS112）。iが３の場合は、ノードN4は存在しないため、通信手段１１を使ってノードNiからノードN1に対して、ノードNi-1から受け取った秘匿化要素集合にノードNiにおけるテーブルのキー集合を要素集合秘匿化手段１２で秘匿化した集合を加えた集合を送信する（図２のステップS115）。図３では、ノードN3は、ノードN2から受け取った秘匿化要素集合{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26)}に加えて、ノードN3における要素集合K_N3 = {K1, K3, K4, K5}をノードN3における要素集合秘匿化手段１２によって秘匿化要素集合{E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}に変換し、両者の秘匿化要素集合をあわせた{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26), E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}をノードN1に送信している。この時、ノードN1はこれらの秘匿化要素集合を受け取っても、ノードN2およびN3が保持しているテーブルのキーの数を推測することはできない。また、秘匿化要素集合のどのデータがノードN2に由来し、どのデータがノードN3に由来するかを推測することもできない。
【００４２】
次に、ノードN1は、自分の秘密鍵を用いた復号化D1を行い、秘匿化要素集合の復号化データの集合を得る（図２のステップS116）。図３で、ノードN1は{E1(K1.D11), E1(K2.D12), E1(K3.D13), E1(D14), E1(D15), E1(K2.D21), E1(K4.D22), E1(K5.D23), E1(D24), E1(D25), E1(D26), E1(K1.D31), E1(K3.D32), E1(K4.D33), E1(K5.D34), E1(D35)}を受け取っているので、復号化すると、復号化要素集合として、{K1.D11, K2.D12, K3.D13, D14, D15, K2.D21, K4.D22, K5.D23, D24, D25, D26, K1.D31, K3.D32, K4.D33, K5.D34, D35}を得る。
【００４３】
次に、ノードN1は、得られた復号化要素集合から文字列撹乱と要素数撹乱で加えられているダミー文字列を除去する（図２のステップS117）。この処理は、復号化要素集合の各文字列の末尾L文字を削除することで達成される。図３の例の場合、この処理により、ダミー文字列除去後の多重集合として{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}を得る。この時点も、ノードN1はこれらの要素がノードN2とN3のどちらに由来しているのかは推測できない。
【００４４】
次に、ノードN1は、得られたダミー文字列除去後の多重集合から重複を除いた和集合を演算する（図２のステップS118）。図３の例の場合、これにより、全ノードN1〜N3が格納している要素集合の和集合として{K1, K2, K3, K4, K5}を得ることができる。こうして、ノードN1、N2、N3も、自分のデータでないものは、他のどのノードに由来しているかを推測できないまま、全てのノードのテーブルキーの和集合を求めることができる。
【００４５】
次に、ノードN1は、得られたテーブルキー和集合を他のノードN2、N3に一斉送信する（図２のステップS119）。
【００４６】
上記説明では、説明を簡単にするため、各ノードの要素集合秘匿化手段１２は、要素集合の順番をそのまま残した形で秘匿化を行っていたが、実際は要素の順番を変えたり、ダミーの要素を間に入れたりすることも考えられ、本実施の形態に述べた方法に限定されない。この場合、例えば、図３でノードN2からノードN3に送信される秘匿化要素集合の順序は、{E1(K2.D12), E1(D26), E1(D14), E1(D15), E1(K2.D21), E1(K1.D11), E1(K4.D22), E1(D24), E1(D25), E1(K3.D13), E1(K5.D23)}のように、ランダムに入れ替わっていても良い。
【００４７】
また、上記説明では、説明を簡単にするため、各ノードの要素集合をそのまま使っているが、人名が外に対して明らかになると困る場合は、ハッシュ関数h()を使って、ノードN1の要素集合をh(K_N1) = {h(K1), h(K2), h(K3)}、ノードN2の要素集合をh(K_N2) = {h(K2), h(K4), h(K5)}、ノードN3の要素集合をh(K_N3) = {h(K1), h(K3), h(K4), h(K5)}、として、図２に示す秘匿化和集合演算処理を行ってもよく、本実施の形態に述べた方法に限定されない。この場合、自分のテーブルに登録されているキー以外はハッシュ値としてしか認識されず、より秘匿性の高いデータ統合方式となる。
【００４８】
また、上記説明では、説明を簡単にするため、要素集合秘匿化手段１２は、各要素の文字列の末尾にあらかじめ定められた長さLの固定長ダミー文字列を付加する方法について述べたが、あらかじめダミー文字列の付与ルールが決められており、ダミー文字列除去手段１４によって正確にダミー文字列を除去できるのであれば、別の方法であってもかまわない。例えば、長さLの固定長のダミー文字列を先頭に付加してもよいし、要素の文字列の奇数番目に固定長のダミー文字列を挿入するという方法も考えられる。後者の場合、元の文字列が"ABCDEFG"で、長さ１のダミー文字列を奇数番目に挿入したとすると、"zA2B3CaD1F8G"という文字列が生成されるので、ダミー文字列除去手段１４は奇数番目の文字列を除去すれば元の文字列"ABCDEFG"が再現できる。
【００４９】
また、上記説明では、説明を簡単にするため、ダミー文字列除去後の多重集合として{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}から和集合を求める方法について述べたが、他にも、出現頻度や積集合などの他の集合演算も可能であり、本実施の形態に述べた方法に限定されない。出現頻度の演算は、単に多重集合内の各要素の出現頻度を計数するだけでよい。例えば、多重集合{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}から、各要素の出現頻度は(K1, K2, K3, K4, K5) = (2, 2, 2, 2, 2)と求まる。さらに、積集合は出現頻度がノードの数に等しい要素を抽出することによって求めることができる。例えば、ノードN1〜N3が格納している要素集合の多重集合が{|K1, K2, K3, K2, K4, K5, K1, K3, K4, K5|}の場合、各要素の出現頻度は(K1, K2, K3, K4, K5) = (2, 2, 2, 2, 2)であるので、積集合は空集合となる。
【００５０】
また、上記説明では、説明を簡単にするため、３台のノードがデータ統合に参加する場合について述べたが、３台以上のノードが参加する場合も考えられ、本実施の形態で述べた方法に限定されない。
【００５１】
本実施の形態では、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用している。そのため、第３者による中央集権的な集計サーバは不要である。
【００５２】
また、本実施の形態では、要素集合秘匿化手段によってデータを秘匿化した状態で集合演算を行うことができる。そのため、ノード間でデータの和集合を求める際にも、他のノードからデータを推測される心配がなくなる。
【００５３】
また、本実施の形態では、データ秘匿化のために、文字列撹乱、要素数撹乱で加えたノイズを正確に除去することができる。そのため、分散サーバの数が少なくても、正確な統合データを求めることができる。
【００５４】
次に本発明の第２の実施の形態について、図面を参照して詳細に説明する。
【００５５】
図４を参照すると、本発明の第２の実施の形態は、図１に示された第１の実施の形態の構成における、ノードN2およびノードN3の処理装置１が、復号化手段１３およびダミー文字列除去手段１４を備えている点で異なる。この場合、全てのノードの機能は等価であるので、ノードのIDを読み替えることによって、任意のノードを集計ノードとして集合演算を行うことができる。
【００５６】
例えば、図５のようにノードN1に２種類の要素集合K_N1 = {K1, K2, K3}とA_N1 = {A1, A2}、ノードN2に２種類の要素集合K_N2 = {K2, K4, K5}とA_N2 = {A1, A3, A4}、ノードN3に２種類の要素集合K_N3 = {K1, K3, K4, K5}とA_N3 = {A1, A2, A5}が格納されている場合、第１の実施の形態と同じ方法で要素集合K_N1、K_N2、K_N3の和集合をノードN1を集計ノードとして求めるのと同時に、要素集合A_N1、A_N2、A_N3の和集合をノードN2を集計ノードとして並列に求めることができる。また、集計ノードをラウンドロビン式に決定したり、乱数により決定することによって、集計処理が特定ノードに集中することを防ぎ、負荷を分散することできる。なお、図５で、E2()は、ノードN2の公開鍵である。
【００５７】
本実施の形態では、データ統合に参加する任意のノードが集計ノードの役割を果たすことができる。そのため、集計処理を並列化させ、負荷を分散させることができる。
【００５８】
次に本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【００５９】
図６を参照すると、本発明の第３の実施の形態におけるノードは、第２の実施の形態におけるノードの処理装置１の構成に、数値秘匿化手段１５と数値ノイズ除去手段１６が加わっている。また、記憶装置２が要素集合記憶部２１の代わりにテーブル記憶部２２を備える。
【００６０】
数値秘匿化手段１５は、各ノードが保持している数値データの合計を演算する際に、各数値データの秘匿化を行う。具体的には、i番目のノードNiは、数値データv_iに対し、十分大きなモジュラー数Xに乱数R_iをかけたものを加え、数値撹乱した上で、加法準同型性を持つ公開鍵暗号方式を用いて、ノードN1の公開鍵を用いて計算結果を暗号化する。すなわち、E1(v_i+X*R_i)を求める。加法準同型性を持つ公開鍵暗号方式には、Paillier暗号、modified-ElGamal暗号などがあり、あらかじめノード間でどの暗号方式を用いるかを定めてあれば、いずれの方式を利用してもかまわない。
【００６１】
ここで、十分大きなモジュラー数Xとは全てのノードの数値データの合計よりも大きな数である必要がある。モジュラー数Xの求め方には、例えば、次のような方法が考えられる。
【００６２】
(1)各ノードの数値データに正の乱数を足した数をお互いブロードキャストする
(2)ブロードキャストされた数値の最大値にノード数をかけて１を足す
これにより、データ統合に参加する分散ノードは自分の数値データを公開することなく、モジュラー数Xを決定することができる。
【００６３】
なお、ここでは、説明を簡単にするために、各ノードの数値データに正の乱数を足した数をお互いブロードキャストし、ブロードキャストされた数値の最大値にノード数をかけて１を足すことによってモジュラー数Xを決定する方法について説明したが、他にも、各ノードの数値データよりも大きな乱数を順に足しこんでいくことによってモジュラー数Xを決定する方法もあり、本実施の形態で述べた方法に限定されない。この場合、ノードN1がノードN1の数値データv_1よりも大きな乱数r_1をノードN2に対して送信し、ノードN2はノードN2の数値データv_2よりも大きな乱数r_2をr_1に加えたr_1+r_2をノードN3に送信し、ノードN3はノードN3の数値データv_3よりも大きな乱数r_2をr_1+r_2に加えたr_1+r_2+r_3をモジュラー数Xとし、ノードN1とN2に通知する。一般的に、ノード数がN台の場合は、r_1+r_2+r_3+...+r_NとN個の乱数を足し合わせたものをモジュラー数Xとすればよい。
【００６４】
数値秘匿化手段１５は、また、自ノードの秘匿化数値データと、他のノードからの秘匿化数値データの積をとり、
E(x1)*E(x2) = E(x1 + x2)
に該当する計算を行う。
【００６５】
数値ノイズ除去手段１６は、復号化された数値データをモジュラー数Xで割った余りを求めることによって、数値撹乱のためにノイズとして加算したモジュラーXと乱数R_iの積X*R_iを除去する。
【００６６】
次に、図６及び図７〜図１１を用いて、本実施の形態の動作について詳細に説明する。
【００６７】
図７は、本実施の形態における動作を表す流れ図である。
【００６８】
まず、データ統合に参加する各ノードは自分が保有するテーブルのキーKを秘匿化した上で、秘匿化和集合演算処理によって、ノード全体でのテーブルのキーKの和集合を求める（図７のステップS101）。図９では、ノードN1のテーブルのキー集合は{K1, K2, K3}、ノードN2のテーブルのキー集合は{K2, K4, K5}、ノードN3のテーブルのキー集合は{K1, K3, K4, K5}の場合の例を示している。また、各テーブルのセルは、単一の要素又は複数の要素からなる要素集合をその構成としている。ノードN1について述べると、セル(K1, A1), (K2, A1), (K3, A1)は、それぞれ要素集合として単一の要素の数値｛12｝,｛4｝,｛7｝を内容としている。セル(K1, A2)は要素集合{a, b}が、セル(K2, A2), (K3, A3)は、それぞれ要素集合として単一要素の文字｛c｝,｛d｝がその内容となっている。
【００６９】
秘匿化和集合演算処理は、第１の実施の形態で述べた図２のステップS111〜S119と同一であるため、ここでは説明を省略する。各ノードのテーブルが図９のようになっている場合、ノードN1〜N3はお互いの保有する属性に関する情報を推測することなく、キーKの和集合として{K1, K2, K3, K4, K5}を得ることができる。
【００７０】
ノード全体でのテーブルのキーKの和集合が求まると、各ノードは自分のノードで、どのキーのデータが欠落しているかを知ることができるので、テーブルに欠落していたキーを追加し、デフォルトの値を設定する。デフォルトの値としては、数値データの場合は０に、文字列データの場合は空文字列に、集合データの場合は空集合に設定すればよい。
【００７１】
次に、データ統合に参加する各ノードは自分が保有するテーブルの属性Aを秘匿化した上で、秘匿化和集合演算処理によって、ノード全体での属性Aの和集合を求める（図２のステップS102）。この場合の秘匿化和集合演算処理も、第１の実施の形態で述べた図２のステップS111〜S119と同一であるため、ここでは説明を省略する。各ノードのテーブルが図９のようになっている場合、ノードN1〜N3はお互いの保有する属性に関する情報を推測することなく、属性Aの和集合として{A1, A2, A3}を得ることができる。この段階で、全てのノードのキーと属性が揃ったことになる。
【００７２】
ノード全体でのテーブルの属性Aの和集合が求まると、各ノードは自分のノードで、どの属性のデータが欠落しているかを知ることができるので、テーブルに欠落していた属性を追加し、デフォルトの値を設定する。デフォルトの値としては、数値データの場合は０に、文字列データの場合は空文字列に、集合データの場合は空集合に設定すればよい。
【００７３】
各ノードの初期のテーブルが図９のようになっていた場合、各ノードが欠落していたキーと属性を追加し、デフォルトの値を設定した例を図１０に示す。図１０を見ると、図９でノードN1に欠落していたキーK4、K5と属性A3が追加され、それぞれの行列に対して、数値データには０が、集合データには空集合が設定されていることが分かる。また、図９でノードN2に欠落していたキーK1とK3の行が追加され、数値データには０が、集合データには空集合が設定されていることが分かる。さらに、図９でノードN3に欠落していたキーK2の行が追加され、数値データには０が、集合データには空集合が設定されていることが分かる。
【００７４】
次に、データ統合に参加する各ノードは、テーブルのスキャンを開始するために、キーポインタKpの値をK1に、属性ポインタApの値をA1に設定する（図７のステップS103）。キーポインタKpと属性ポインタApで指定されるセルの値が数値データであった場合（図７のステップS104）、秘匿化数値合計計算処理によって、そのセルの数値データを秘匿化した上で合計を計算する（図７のステップS105）。
【００７５】
図８は、秘匿化数値合計計算処理の動作を表す流れ図である。
【００７６】
秘匿化数値合計計算処理では、まず、処理対象のノードのポインタiを１に設定する（図８のステップS121）。次に、i+1番目のノードが存在していれば（図８のステップS122）、通信手段１１を使ってノードNiからノードNi+1に対して数値秘匿化手段１５で秘匿化された数値データを送信する（図８のステップS123）。
【００７７】
図１０に、具体的なテーブルとデータの流れの模式図を示す。図１０では、ノードN1のテーブルのセルの値は１２であり、これをV1_11と記述することにする。また、図１０では、ノードN1における数値秘匿化手段１５は、V1_11にモジュラー数Xと乱数R1の積を足したV1_11+X*R1を計算した上で、ノードN1の公開鍵で暗号化し、E1(V1_11+X*R1)をノードN2に送信する。この時、ノードN2はこれらの秘匿化数値データを受け取っても、元データであるV1_11を推測することはできない。
【００７８】
次に、処理対象のノードのポインタiを1増加させ（図８のステップS124）、再度、i+1番目のノードが存在しているかチェックし（図８のステップS122）、存在していれば通信手段１１を使ってノードNiからノードNi+1に対し、ノードNi-1から送信された秘匿化数値データと、ノードNiにおける数値秘匿化手段１５で秘匿化した数値データの積を送信する（図８のステップS123）。図１０では、ノードN2はノードN1から秘匿化数値データE1(V1_11+X*R1)に、さらに、ノードN2におけるセルの数値データV2_11 = 0をノードN2における数値秘匿化手段１５によって秘匿化された数値データE1(V2_11+X*R2)の積をとって、ノードN3に送信している。この時、ノードN3に送信される秘匿化数値データはE1(V1_11+X*R1)*E1(V2_11+X*R2)であるが、これは、E1(V1_11+V2_11+X*(R1+R2))に等しい。この時、ノードN3はこれらの秘匿化数値データを受け取っても、元データであるV1_11やV2_11を推測することはできない。
【００７９】
さらに、処理対象のノードのポインタiを１増加させ（図８のステップS124）、再度、i+1番目のノードが存在しているかチェックする（図8のステップS122）。iが3の場合は、ノードN4は存在しないため、通信手段１１を使ってノードNiからノードN1に対して、ノードNi-1から受け取った秘匿化数値データに、Niにおける数値秘匿化手段１５で秘匿化した数値データの積を送信する（図８のステップS125）。図１０では、ノードN3は、ノード2から受け取った秘匿化数値データE1(V1_11+X*R1)*E1(V2_11+X*R2)に、ノードN3におけるセルの数値データV3_11 = 5を数値秘匿化手段１５によって秘匿化された数値データE1(V3_11+X*R3)を掛けた、E1(V1_11+X*R1)*E1(V2_11+X*R2)*E1(V3_11+X*R3) = E1(V1_11+V2_11+V3_11+X*(R1+R2+R3))をノードN1に送信している。この時、ノードN1はこの秘匿化数値データを受け取っても、ノードN2およびN3のセルの数値データV2_11、V3_11を推測することはできない。
【００８０】
次に、ノードN1は、自分の秘密鍵を用いた復号化D1を行い、秘匿化数値データの復号化データを得る（図８のステップS126）。図１０で、ノードN1はE1(V1_11+V2_11+V3_11+X*(R1+R2+R3))を受け取っているので、復号化すると、復号化数値データとして、V1_11+V2_11+V3_11+X*(R1+R2+R3)を得る。
【００８１】
次に、ノードN1は、得られた復号化数値データから数値撹乱で加えられているノイズを除去する（図８のステップS127）。この処理は、復号化数値データをモジュラー数Xで割った余りを計算することで達成される。図１０の例の場合、この処理により、ノイズ除去後の数値データとしてV1_11+V2_11+V3_11を得る。この時も、ノードN1はこれらの数値データがノードN2とN3のどちらにどれだけ由来しているのかは推測できない。こうして、ノードN1、N2、N3も、自分のデータでないものは、どのノードに由来しているか推測できないまま、全てのノードのセルの数値データの合計を求めることができた。
【００８２】
次に、ノードN1は、得られた数値データの合計を他のノードN2、N3に一斉送信する（図８のステップS128）。これにより、各ノードは自分のノードの該当セルの値を修正する。
【００８３】
次に、データ統合に参加する各ノードはさらに別のセルをスキャンし、未処理のセルがあればそのセルの位置をキーポインタKp、属性ポインタApにセットし（図７のステップS107）、セルが数値データか否かを判定する（図７のステップS104）。例えば、キーポインタKpがK1〜K5まで変化し、属性ポインタApがA1のままだった場合、図１０のテーブルの属性A1の列をスキャンしながら統合することになる。
【００８４】
また、セルが数値データでなかった場合（図７のステップS104）、セルの値を集合として秘匿化データ和集合演算処理によって、セルの値の和集合を求める（図７のステップS106）。この処理の詳細も１1の実施の形態で説明した方法と同じであり、テーブルのキーの和集合や、属性の和集合を求める方法と同様である。各ノードのデータが図１０のようになっている場合、ノードN1〜N3のセルの値の和集合として{a,b}を得ることができる。
【００８５】
さらに、未処理のセルがあればそのセルの位置をキーポインタKp、属性ポインタApにセットして統合処理を続け（図７のステップS107）、未処理のセルがなくなったら統合処理が終了する。この時、ノードN1〜N3で統合されたテーブルは図１１のように全て同じ値を持つ。
【００８６】
なお、ここでは、説明を簡単にするためキーポインタKp、属性ポインタApを個別に設定してセルを１つずつ統合していく方法について説明したが、テーブルの列または行方向をひとまとめとして、１行ずつ、あるいは１列ずつ統合処理する方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８７】
さらに、ここでは、説明を簡単にするため、常にノードN1からデータの送信が開始され、最後にノードN1でデータが復元される方法について説明したが、他にも、ラウンドロビン式にデータの送信開始と復元するノードを割り当て、並列に処理する方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８８】
また、ここでは、各セルについて統合データが得られる度にそのセルを修正する方法について説明したが、他にも、各ノードが初期のテーブルとは独立に統合テーブルを保持し、統合データは統合テーブルに格納するなどの方法も考えられ、本実施の形態に述べた方法に限定されない。
【００８９】
本実施の形態では、データ統合に参加する各ノードがプロトコルにしたがって秘匿化データをやりとりすることによって、各ノードに統合データが構築されるような構成を採用している。そのため、中央集権的な集計サーバは不要であり、データが集中することによるボトルネックの問題を解消できる。
【００９０】
また、本実施の形態では、要素集合秘匿化手段によってデータを秘匿化した状態で和集合を求めることができる。そのため、分散ノード間でデータの集計を行う際にも、他のノードからデータを推測される心配がなくなる。
【００９１】
また、本実施の形態では、データ秘匿化のために、文字列撹乱、要素数撹乱、数値撹乱で加えたノイズを正確に除去することができる。そのため、分散サーバの数が少なくても、正確な統合データを求めることができる。
【００９２】
次に、本発明の第４の実施の形態について、図面を参照して詳細に説明する。
【００９３】
図１２を参照すると本発明の第４の実施の形態は、入力手段５０１、データ処理装置５０２、出力手段５０３、記憶装置５０４を備える。さらに、第１の実施の形態の分散型秘匿化データ統合装置を実現するための分散型秘匿化データ統合プログラム５００を備える。
【００９４】
入力手段５０１は、マウス、キーボード等、操作者からの指示を入力するための装置である。また、出力手段５０３は、表示画面、プリンタ等のデータ処理装置５０２による処理結果を出力する装置である。
【００９５】
分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第１の実施形態におけるノードN1〜N3の処理装置１と同一の処理を実行する。
【００９６】
図１２におけるデータ処理装置５０２は、図１における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４の処理を実行し、図１２における記憶装置５０４には、図１における要素集合記憶部２１、の情報が格納される。
【００９７】
次に、本発明の第５の実施の形態について、図面を参照して詳細に説明する。
【００９８】
第５の実施の形態は、第４の実施の形態と同様に図１２の構成図を用いる。分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第２の実施形態における処理装置２と同一の処理を実行する。
【００９９】
図１２におけるデータ処理装置５０２は、図４における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４の処理を実行し、図１２における記憶装置５０４には、図４における要素集合記憶部２１の情報が格納される。
【０１００】
次に、本発明の第６の実施の形態について、図面を参照して詳細に説明する。
【０１０１】
第６の実施の形態は、第４の実施の形態と同様に図１２の構成図を用いる。分散型秘匿化データ統合プログラム５００は、データ処理装置５０２に読み込まれ、データ処理装置５０２の動作を制御し、記憶装置５０４に入力メモリ５０５とワークメモリ５０６を生成する。データ処理装置５０２は、プログラムの制御により第２の実施形態における処理装置２と同一の処理を実行する。
【０１０２】
図１２におけるデータ処理装置５０２は、図６における通信手段１１、要素集合秘匿化手段１２、復号化手段１３、ダミー文字列除去手段１４、数値秘匿化手段１５、数値ノイズ除去手段１６の処理を実行し、図１２における記憶装置５０４には、図６におけるテーブル記憶部２２の情報が格納される。
【産業上の利用可能性】
【０１０３】
本発明は、異なる企業間における顧客データのデータマイニングや、異なる国における人脈データの統合などに適用が可能である。
【符号の説明】
【０１０４】
１ 処理装置
２ 記憶装置
３ ネットワーク
１１ 通信手段
１２ 要素集合秘匿化手段
１３ 復号化手段
１４ ダミー文字列除去手段
１５ 数値秘匿化手段
１６ 数値ノイズ除去手段
２１ 要素集合記憶部
２２ テーブル記憶部
【特許請求の範囲】
【請求項１】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムであって、
第２のノードは、少なくとも、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段とを備え、
第１のノードは、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えていることを特徴とする分散型データ統合システム。
【請求項２】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを複合化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段とを備え第１のノードとして機能することを特徴とする請求項１記載の分散型データ統合システム。
【請求項３】
複数の第１のノードで異なる要素集合の秘匿化データの集合演算が並列に行われることを特徴とする請求項１又は２に記載の分散型データ統合システム。
【請求項４】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えていることを特徴とするノード。
【請求項５】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、
自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
を備えていることを特徴とするノード。
【請求項６】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムであって、
第２のノードは、少なくとも、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段とを備え、
第１のノードは、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを備えている、
ことを特徴とする分散型データ統合システム。
【請求項７】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを備え、第１のノードとして機能することを特徴とする請求項６記載の分散型データ統合システム。
【請求項８】
請求項７に記載の分散型データ統合システムであって、
複数の第１のノードで異なるセルの数値の秘匿化データの合計計算または要素集合の秘匿化データの集合演算が並列に行われることを特徴とする分散型データ統合システム。
【請求項９】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、
テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、
他のノードから送信されてきた秘匿化データを復号化する復号化手段と、
復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段と、
を備えていることを特徴とするノード。
【請求項１０】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、
テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、
を備えていることを特徴とするノード。
【請求項１１】
請求項１、２、６、又は７記載の分散型データ統合システムであって、
前記第１のノードから送信される前記秘匿化データは、前記第２のノード間で重複しない順番で順次送信され、前記第２のノードのそれぞれにおける秘匿化データが順次合わされた後、前記第１のノードにおいて受信されることを特徴とする分散型データ統合システム。
【請求項１２】
請求項１，２，６、又は７に記載の分散型データ統合システムであって、
前記要素集合秘匿化手段は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱と、のいずれか１つ、もしくは両方を行うことを特徴とする分散型データ統合システム。
【請求項１３】
請求項６又は７記載の分散型データ統合システムであって、
前記数値秘匿化手段は、
前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱を行うことを特徴とする分散型データ統合システム。
【請求項１４】
請求項６又は７記載の分散型データ統合システムであって、
各ノードが格納するテーブルのキーまたは属性の和集合を秘匿化した状態で求めた後、それぞれのノードが格納するテーブルに不足しているキーと属性を追加し、テーブルの初期値を設定することを特徴とする分散型データ統合システム。
【請求項１５】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、
各ノードが格納する要素集合の集合演算を行う分散型データ統合方法であって、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１６】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合方法であって、
各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、
各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、
各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１７】
請求項１６に記載の分散型データ統合方法であって、
前記秘匿化キー和集合演算処理、前記秘匿化属性和集合演算処理、および、前記秘匿化データ和集合演算処理は、
集計ノードが自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードは、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１８】
請求項１５又は１７に記載の分散型データ統合方法であって、
前記要素集合秘匿化処理は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱処理と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱処理とのいずれか１つ、もしくは両方を行うことを特徴とする分散型データ統合方法。
【請求項１９】
請求項１６に記載の分散型データ統合方法であって、
前記秘匿化数値合計計算処理は、
集計ノードが自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化する数値秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードは、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化し、受信した秘匿化データとの積を計算し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの積を送信する処理と、
集計ノードにおいて、秘匿化データの積を復号化する処理と、
集計ノードにおいて、復号化されたデータから数値撹乱の影響を除去する処理と、
集計ノードから他の参加ノードに、数値撹乱の影響を除去した結果を一斉送信する処理と、を含むことを特徴とする分散型データ統合方法。
【請求項２０】
請求項１９に記載の分散型データ統合方法であって、
前記数値秘匿化処理は、前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱処理を行うことを特徴とする分散型データ統合方法。
【請求項２１】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムにおけるノードに実行させるプログラムであって、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理とを実行させることを特徴とするプログラム。
【請求項２２】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させるプログラムであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードから受信する通信処理と、
自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、その和集合を、未受信の他のノードが存在する場合には、秘匿化データをそのノードに送信し、未受信の他のノードが存在しない場合には、集計ノードに送信する処理を実行させることを特徴とするプログラム。
【請求項２３】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させる分散型データ統合プログラムであって、
ノードが集計ノードの場合には、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから送信される秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の他の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の他の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理と、を実行させることを特徴とする分散型データ統合プログラム。
【請求項２４】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおいてノードに実行させる分散型統合プログラムであって、
各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、
各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、
各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、
を実行させることを特徴とする分散型データ統合プログラム。
【請求項２５】
請求項２４に記載の分散型データ統合プログラムであって、
前記秘匿化キー和集合演算処理、前記秘匿化属性和集合演算処理、および、前記秘匿化データ和集合演算処理は、
ノードが集計ノードの場合には、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理と、を実行させる分散型データ統合プログラム。
【請求項２６】
請求項２４に記載の分散型データ統合プログラムであって、
前記秘匿化数値合計計算処理は、
ノードが集計ノードの場合には、
集計ノードにおいて、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化する数値秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの積を受信する処理と、
集計ノードにおいて、秘匿化データの積を復号化する処理と、
集計ノードにおいて、復号化されたデータから数値撹乱の影響を除去する処理と、
集計ノードから他の参加ノードに、数値撹乱の影響を除去した結果を一斉送信する処理と、を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化し、受信した秘匿化データとの積を計算し、未受信の参加ノードが存在する場合には、未受信の参加ノードに秘匿化データを送信し、未受信の別の参加ノードが存在しない場合には、集計ノードに秘匿化データの積を送信する処理と、
を実行させることを特徴とする分散型データ統合プログラム。
【請求項２７】
請求項２３又は２５に記載の分散型データ統合プログラムであって、
前記要素集合秘匿化処理は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱処理と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱処理と、
のいずれか１つ、もしくは両方を含むことを特徴とする分散型データ統合プログラム。
【請求項２８】
請求項２６に記載の分散型データ統合プログラムであって、
前記数値秘匿化処理は、
前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱処理を含むことを特徴とする分散型データ統合プログラム。
【請求項１】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムであって、
第２のノードは、少なくとも、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段とを備え、
第１のノードは、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えていることを特徴とする分散型データ統合システム。
【請求項２】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを複合化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段とを備え第１のノードとして機能することを特徴とする請求項１記載の分散型データ統合システム。
【請求項３】
複数の第１のノードで異なる要素集合の秘匿化データの集合演算が並列に行われることを特徴とする請求項１又は２に記載の分散型データ統合システム。
【請求項４】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
を備えていることを特徴とするノード。
【請求項５】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納される要素集合の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、
自らが格納する要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
を備えていることを特徴とするノード。
【請求項６】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムであって、
第２のノードは、少なくとも、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段とを備え、
第１のノードは、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他のノードから送受信する通信手段と、テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを備えている、
ことを特徴とする分散型データ統合システム。
【請求項７】
前記第２のノードは、何れも、さらに、他のノードから送信されてきた秘匿化データを復号化する復号化手段と、復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段とを備え、第１のノードとして機能することを特徴とする請求項６記載の分散型データ統合システム。
【請求項８】
請求項７に記載の分散型データ統合システムであって、
複数の第１のノードで異なるセルの数値の秘匿化データの合計計算または要素集合の秘匿化データの集合演算が並列に行われることを特徴とする分散型データ統合システム。
【請求項９】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、
テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、
他のノードから送信されてきた秘匿化データを復号化する復号化手段と、
復号化によって得られた要素集合から文字列撹乱または要素数撹乱の影響を取り除くダミー文字列除去手段と、
復号化によって得られた数値から数値撹乱の影響を取り除く数値ノイズ除去手段と、
を備えていることを特徴とするノード。
【請求項１０】
少なくとも１台の第１のノードと少なくとも１台の第２のノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおけるノードであって、
文字列撹乱、要素数撹乱または数値撹乱によって秘匿化された秘匿化データを他ノードに又は他ノードから送受信する通信手段と、
テーブルのキーまたは属性および各セルに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、秘匿化データを出力する要素集合秘匿化手段と、
テーブルの各セルに格納された数値を数値撹乱によって秘匿化し、秘匿化データを出力する数値秘匿化手段と、
を備えていることを特徴とするノード。
【請求項１１】
請求項１、２、６、又は７記載の分散型データ統合システムであって、
前記第１のノードから送信される前記秘匿化データは、前記第２のノード間で重複しない順番で順次送信され、前記第２のノードのそれぞれにおける秘匿化データが順次合わされた後、前記第１のノードにおいて受信されることを特徴とする分散型データ統合システム。
【請求項１２】
請求項１，２，６、又は７に記載の分散型データ統合システムであって、
前記要素集合秘匿化手段は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱と、のいずれか１つ、もしくは両方を行うことを特徴とする分散型データ統合システム。
【請求項１３】
請求項６又は７記載の分散型データ統合システムであって、
前記数値秘匿化手段は、
前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱を行うことを特徴とする分散型データ統合システム。
【請求項１４】
請求項６又は７記載の分散型データ統合システムであって、
各ノードが格納するテーブルのキーまたは属性の和集合を秘匿化した状態で求めた後、それぞれのノードが格納するテーブルに不足しているキーと属性を追加し、テーブルの初期値を設定することを特徴とする分散型データ統合システム。
【請求項１５】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、
各ノードが格納する要素集合の集合演算を行う分散型データ統合方法であって、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１６】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合方法であって、
各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、
各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、
各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１７】
請求項１６に記載の分散型データ統合方法であって、
前記秘匿化キー和集合演算処理、前記秘匿化属性和集合演算処理、および、前記秘匿化データ和集合演算処理は、
集計ノードが自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードは、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの和集合を送信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を含むことを特徴とする分散型データ統合方法。
【請求項１８】
請求項１５又は１７に記載の分散型データ統合方法であって、
前記要素集合秘匿化処理は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱処理と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱処理とのいずれか１つ、もしくは両方を行うことを特徴とする分散型データ統合方法。
【請求項１９】
請求項１６に記載の分散型データ統合方法であって、
前記秘匿化数値合計計算処理は、
集計ノードが自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化する数値秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
秘匿化データを受信した参加ノードは、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化し、受信した秘匿化データとの積を計算し、未受信の参加ノードに秘匿化データを送信する処理と、
未受信の別の参加ノードがなくなった場合は、集計ノードに秘匿化データの積を送信する処理と、
集計ノードにおいて、秘匿化データの積を復号化する処理と、
集計ノードにおいて、復号化されたデータから数値撹乱の影響を除去する処理と、
集計ノードから他の参加ノードに、数値撹乱の影響を除去した結果を一斉送信する処理と、を含むことを特徴とする分散型データ統合方法。
【請求項２０】
請求項１９に記載の分散型データ統合方法であって、
前記数値秘匿化処理は、前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱処理を行うことを特徴とする分散型データ統合方法。
【請求項２１】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムにおけるノードに実行させるプログラムであって、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理とを実行させることを特徴とするプログラム。
【請求項２２】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させるプログラムであって、
文字列撹乱または要素数撹乱によって秘匿化された秘匿化データを他ノードから受信する通信処理と、
自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、その和集合を、未受信の他のノードが存在する場合には、秘匿化データをそのノードに送信し、未受信の他のノードが存在しない場合には、集計ノードに送信する処理を実行させることを特徴とするプログラム。
【請求項２３】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードが格納する要素集合の集合演算を行う分散型データ統合システムのおけるノードに実行させる分散型データ統合プログラムであって、
ノードが集計ノードの場合には、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから送信される秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、
を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の他の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の他の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理と、を実行させることを特徴とする分散型データ統合プログラム。
【請求項２４】
少なくとも１台の集計ノードと少なくとも１台の参加ノードを備え、各ノードに格納されている異なるキーと属性を有するテーブルの各セルの数値の合計と集合要素の集合演算を行う分散型データ統合システムにおいてノードに実行させる分散型統合プログラムであって、
各ノードが格納するテーブルのキーについて、秘匿化した状態で和集合を求める秘匿化キー和集合演算処理と、
各ノードが格納するテーブルの属性について、秘匿化した状態で和集合を求める秘匿化属性和集合演算処理と、
各ノードが格納するテーブルのセルの要素集合について、秘匿化した状態で和集合を求める秘匿化データ和集合演算処理と、
各ノードが格納するテーブルのセルの数値について、秘匿化した状態で合計を求める秘匿化数値合計計算処理と、
を実行させることを特徴とする分散型データ統合プログラム。
【請求項２５】
請求項２４に記載の分散型データ統合プログラムであって、
前記秘匿化キー和集合演算処理、前記秘匿化属性和集合演算処理、および、前記秘匿化データ和集合演算処理は、
ノードが集計ノードの場合には、
集計ノードにおいて自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化する要素集合秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの和集合を受信する処理と、
集計ノードにおいて、秘匿化データの和集合を復号化する処理と、
集計ノードにおいて、復号化されたデータから文字列撹乱または要素数撹乱の影響を除去する処理と、
集計ノードにおいて、文字列撹乱または要素数撹乱の影響を除去したデータの集合演算を行う処理と、
集計ノードから他の参加ノードに、集合演算の結果を一斉送信する処理と、を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードに格納された要素集合を文字列撹乱または要素数撹乱によって秘匿化し、受信した秘匿化データとの和集合を生成し、未受信の参加ノードが存在する場合には、その未受信の参加ノードにその和集合を送信し、未受信の参加ノードが存在しない場合には、集計ノードにその和集合を送信する処理と、を実行させる分散型データ統合プログラム。
【請求項２６】
請求項２４に記載の分散型データ統合プログラムであって、
前記秘匿化数値合計計算処理は、
ノードが集計ノードの場合には、
集計ノードにおいて、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化する数値秘匿化処理と、
集計ノードから一つの参加ノードに秘匿化データを送信する通信処理と、
参加ノードから秘匿化データの積を受信する処理と、
集計ノードにおいて、秘匿化データの積を復号化する処理と、
集計ノードにおいて、復号化されたデータから数値撹乱の影響を除去する処理と、
集計ノードから他の参加ノードに、数値撹乱の影響を除去した結果を一斉送信する処理と、を実行させ、
ノードが参加ノードの場合には、
秘匿化データを受信した参加ノードにおいて、自ノードのテーブルのセルに格納された数値を数値撹乱によって秘匿化し、受信した秘匿化データとの積を計算し、未受信の参加ノードが存在する場合には、未受信の参加ノードに秘匿化データを送信し、未受信の別の参加ノードが存在しない場合には、集計ノードに秘匿化データの積を送信する処理と、
を実行させることを特徴とする分散型データ統合プログラム。
【請求項２７】
請求項２３又は２５に記載の分散型データ統合プログラムであって、
前記要素集合秘匿化処理は、
要素集合の要素を表す文字列にあらかじめ決められたルールによってダミー文字列を付与することによって元の文字列を推測不可能にする文字列撹乱処理と、
ダミー文字列のみを暗号化したダミー要素を生成することによって要素数を推測不可能にする要素数撹乱処理と、
のいずれか１つ、もしくは両方を含むことを特徴とする分散型データ統合プログラム。
【請求項２８】
請求項２６に記載の分散型データ統合プログラムであって、
前記数値秘匿化処理は、
前記セルに格納された数値に、乱数とモジュラーの積を加算することによって元の数値を推測不可能にする数値撹乱処理を含むことを特徴とする分散型データ統合プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１６６２２８（Ｐ２０１０−１６６２２８Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−５８２８（Ｐ２００９−５８２８）
【出願日】平成２１年１月１４日（２００９．１．１４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（５０９０１４８５８）カーネギー メロン ユニバーシティー (2)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１４日（２００９．１．１４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（５０９０１４８５８）カーネギー メロン ユニバーシティー (2)
【Ｆターム（参考）】
[ Back to top ]