(57)【特許請求の範囲】
【請求項１】
ｎを１以上の所定の整数として、自身が有するテーブルの各属性値を第０装置のみが復号できるように暗号化することにより上記自身が有するテーブルを暗号化する暗号部を含む上記第０装置から第ｎ−１装置を含む名寄せシステムにおいて、
上記第ｎ−１装置は、上記第０装置から上記ｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、上記第０装置が有するテーブルの属性の集合A0として、上記名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを上記第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを上記名寄せテーブルの各属性a∈A0の属性値に加算することにより上記名寄せテーブルの撹乱を行う撹乱部と、上記撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替部を更に含み、
上記第０装置は、上記並替後テーブルの各属性値を復号する復号部を更に含む、
名寄せシステム。
【請求項２】
請求項１の名寄せシステムであって、
上記第１装置から第ｎ−１装置は、自身が有するテーブルの各レコードの各属性ａの属性値に対して所定のパラメータbaに従い有界ノイズ加算を行う有界ノイズ加算部を更に含み、上記暗号部は有界ノイズ加算後の属性値を上記第０装置のみが復号できるように暗号化することにより上記自身が有するテーブルを暗号化する、
名寄せシステム。
【請求項３】
請求項１の名寄せシステムであって、
kをセキュリティパラメータとし、Rを匿名化前のレコードの集合とし、Vaiを匿名化前の属性aiの取り得る属性値の集合として、上記パラメータbaは、以下の式により定義されるbaである、
【数１３】
0006437416.tif 000014
名寄せシステム。
【請求項４】
請求項１又は２の名寄せシステムであって、
kをセキュリティパラメータとし、Rを匿名化前のレコードの集合とし、Vaiを匿名化前の属性aiの取り得る属性値の集合とし、Aを上記第０装置から上記第ｎ−１装置が有するテーブルの属性の集合Aとして、上記パラメータbaは、以下の式により定義されるbaである、    
【数１４】
0006437416.tif 000015
名寄せシステム。
【請求項５】
第０装置から第ｎ−１装置は、ｎを１以上の所定の整数として、自身が有するテーブルの各属性値を上記第０装置のみが復号できるように暗号化することにより上記自身が有するテーブルを暗号化する暗号部を含むとして、
上記第０装置から上記ｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、上記第０装置が有するテーブルの属性の集合A0として、上記名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを上記第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを上記名寄せテーブルの各属性a∈A0の属性値に加算することにより上記名寄せテーブルの撹乱を行う撹乱部と、上記撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替部を更に含む上記第ｎ−１装置である名寄せ装置。
【請求項６】
ｎを１以上の所定の整数として、第０装置から第ｎ−１装置の暗号部が、自身が有するテーブルの各属性値を上記第０装置のみが復号できるように暗号化することにより上記自身が有するテーブルを暗号化する暗号ステップと、
上記第ｎ−１装置の撹乱部が、上記第０装置から上記ｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、上記第０装置が有するテーブルの属性の集合A0として、上記名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを上記第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを上記名寄せテーブルの各属性a∈A0の属性値に加算することにより上記名寄せテーブルの撹乱を行う撹乱ステップと、
上記第ｎ−１装置の並替部が、上記撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替ステップと、
上記第０装置の復号部が、上記並替後テーブルの各属性値を復号する復号ステップと、
を含む名寄せ方法。
【請求項７】
第０装置から第ｎ−１装置は、ｎを１以上の所定の整数として、自身が有するテーブルの各属性値を上記第０装置のみが復号できるように暗号化することにより上記自身が有するテーブルを暗号化する暗号部を含むとして、
上記第０装置から上記ｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、上記第０装置が有するテーブルの属性の集合A0として、上記名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを上記第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを上記名寄せテーブルの各属性a∈A0の属性値に加算することにより上記名寄せテーブルの撹乱を行う撹乱部と、上記撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替部を更に含む名寄せ装置の上記暗号部、上記撹乱部及び上記並替部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、異なる複数の主体が有するテーブルを名寄せする技術に関する。
【背景技術】
【０００２】
まず、本技術が想定するモデルについて説明する。n人のパーティP0,・・・,Pn−1が互いにテーブルτ0,・・・,τn-1を持っており、それぞれのテーブルは同じIDであるr∈Rを持つが、あるパーティのテーブルには年齢、ある異なるパーティのテーブルには年収など、テーブル毎に属性が異なる。
【０００３】
このようなテーブルを、互いに不必要な情報はできるだけ与えず、結合することを考える。そうすることで、年齢と年収の相関などといった分析が可能になる。
【０００４】
なお、本資料での説明では簡単のため、結合したテーブルを得るパーティをP0とするが、結合したテーブルを得るパーティはP0以外のどのパーティでも良い。
【０００５】
例えば以下の1.から3.により、P0が結合したテーブルを得ることができる。
【０００６】
1.決定的な（同じ値を暗号化した場合、同じ暗号文になる）暗号を用いて、ID及びテーブルを、P0のみが復号できるように暗号化し、P0に送る。
2.P0は暗号化されたIDを見て、同じ値のレコードを結合させる。
3.P0は全ての値を復号する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、P0は元々持っていたテーブルと突き合わせることによって、元々のテーブルのある個人Iと、結合したテーブルの個人Iを突き合わせることができる。すると、相関関係のような分析には本来不必要な個人に関する情報が、P0に渡ってしまう。例えば、「年齢が30歳の時に年収がぐっと上がる」という分析結果を得るために、P0は「Iさんは30歳になっても全然年収が上がっていない」といった情報を得てしまっており、プライバシーの問題が生じる可能性がある。
【０００８】
この発明の目的は、復元する主体に対しプライバシーを保護することができる名寄せシステム、装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００９】
この発明の一態様による名寄せシステムは、ｎを１以上の所定の整数として、自身が有するテーブルの各属性値を第０装置のみが復号できるように暗号化することにより自身が有するテーブルを暗号化する暗号部を含む第０装置から第ｎ−１装置を備えている名寄せシステムにおいて、第ｎ−１装置は、第０装置からｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、第０装置が有するテーブルの属性の集合A0として、名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを名寄せテーブルの各属性a∈A0の属性値に加算することにより名寄せテーブルの撹乱を行う撹乱部と、撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替部を更に備えており、第０装置は、並替後テーブルの各属性値を復号する復号部を更に備えている。
【００１０】
この発明の一態様による名寄せ装置は、第０装置から第ｎ−１装置は、ｎを１以上の所定の整数として、自身が有するテーブルの各属性値を第０装置のみが復号できるように暗号化することにより自身が有するテーブルを暗号化する暗号部を含むとして、第０装置からｎ−１装置が暗号化したテーブルを名寄せしたテーブルを名寄せテーブルとし、第０装置が有するテーブルの属性の集合A0として、名寄せテーブルの各属性a∈A0の属性値について所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを名寄せテーブルの各属性a∈A0の属性値に加算することにより名寄せテーブルの撹乱を行う撹乱部と、撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する並替部を更に含む第ｎ−１装置である。
【発明の効果】
【００１１】
復元する主体に対しプライバシーを保護することができる。
【図面の簡単な説明】
【００１２】
【図１】名寄せ装置の例を説明するためのブロック図。
【図２】名寄せ方法の例を説明するための流れ図。
【図３】名寄せプロトコルの例を示す図。
【発明を実施するための形態】
【００１３】
まず、この発明の基礎となる事柄を説明する。
【００１４】
［記法］
abs(x)はxの絶対値を指し、集合Aに対し|A|は集合の要素数を表し、gは群を意味する。またx←Bは、Bが集合ならばBから一様ランダムに要素を選びxに代入することを指し、BがアルゴリズムならばBの出力をxに代入することを指す。
【００１５】
［データ形式と記法］
匿名化前後のデータは、各行が一個人のデータを表し（これをレコードと呼ぶ）、各列には属性と呼ばれる年齢、年収等の値が入力されているようなテーブルであるとする。
【００１６】
テーブルに対する匿名化を形式的に議論するための定義を与える。
【００１７】
・Τ,τ:匿名化前のテーブルの確率変数及びそのインスタンス
・Τ’,τ’:匿名化テーブルの確率変数及びそのインスタンス
・R,R’:匿名化前/後のテーブルのレコード集合
・A,A’:匿名化前/後の属性の集合
・Va,V a’:匿名化前/後の属性a∈Aの取りうる属性値の集合
・V,V’:匿名化前/後のレコードが取りうる属性値の組み合わせの集合。すなわちΠで直積を表すとV=Πa∈AVaである。
・va:あるレコードの属性a∈Aの属性値のインスタンス。
・Δ,δ:プライバシー保護処理の確率変数及びそのインスタンス
・fX:確率変数Xに関する確率密度関数
・Π,π:R→R’であるようなランダム置換の確率変数及びそのインスタンス
τ,τ’,δはそれぞれτ:R→V,τ’:R’→V’,δ:(R→V)→(R→V’)であるような関数であり、π,δ,τ,τ’の間にはδ(τ)=τ’・πが成り立つ。また、τ(r)(a)をτ’(r’)(a’)をそれぞれレコードrの属性aの属性値、レコードr’の属性a’の属性値とする。
【００１８】
［Pk-匿名性］
Pk-匿名性は、参考文献１，２で提案されたプライバシー保護指標である。あるτ’,r∈R,r’∈R,Δ(Τ)=Τ’・Πについて、Pr[Π(r)=r’|Τ’=τ’]を攻撃成功の確率とし、Pk-匿名性は以下のように定義される。
【００１９】
〔参考文献１〕Dai Ikarashi, Ryo Kikuchi, Koji Chida, and Katsumi Takahashi, "k-anonymous microdata release via post randomisation method", In IWSEC 2015 (to appear), 2015.
【００２０】
〔参考文献２〕五十嵐大, 千田浩司, 高橋克巳, "k-匿名性の確率的指標への拡張とその適用例", In CSS, 2009.
【００２１】
実数k≧1について、あるプライバシー保護処理Δと匿名化テーブルτ’が、背景知識fΤを持つ攻撃者、任意のテーブルΤ、レコードr∈R、レコードr’∈R’について、
【００２２】
【数１】
0006437416.tif 000002
【００２３】
であるならば、(Δ,τ’)は背景知識fΤを持つ攻撃者に対してPk-匿名性を満たすという。
【００２４】
なお、この定義は参考文献１の定義から、弱い背景知識を持つ攻撃者も想定できるように拡張した定義となっている。
【００２５】
［Pk-匿名化］
Pk-匿名化とは、Pk-匿名性を満たすための処理であり、ここでは数値属性に対する有界ノイズ加算を扱う（例えば、参考文献３参照。）。
【００２６】
有界ノイズ付加では、ある値域に区切られたノイズを加算することにより、Pk-匿名性を満たすことができる。
【００２７】
ここでは、確率密度関数
【００２８】
【数２】
0006437416.tif 000003
【００２９】
に従うラプラスノイズを基とした有界ノイズを用いる。ある数値属性a∈Aの値域が[vmin,vmax]で、
【００３０】
【数３】
0006437416.tif 000004
【００３１】
としたとき、flap,b(x)のパラメータbを、
【００３２】
【数４】
0006437416.tif 000005
【００３３】
と設定し、さらに、
【００３４】
【数５】
0006437416.tif 000006
【００３５】
としたときv∈Vaに対して確率密度関数
【００３６】
【数６】
0006437416.tif 000007
【００３７】
に従うノイズを加えることで、Pk-匿名性を満たすことができる（例えば、参考文献３参照。）。
【００３８】
［実数を暗号化できる準同型暗号］
ここでは、平文の空間が実数(固定小数点)であり、準同型性を持つ公開鍵暗号を用いる。また、パラメータparamsはSetup以外のアルゴリズム全てに必要なため省略する。
【００３９】
・Setup(1λ):セキュリティパラメータ1λを入力として、パラメータparamsを出力する。
・KGen():paramsを入力として、公開鍵と秘密鍵のペア(pk,sk)を出力する。
・Enc(pk,m)pkとメッセージmを入力として、暗号文cを出力する。
・Dec(sk,c)skと暗号文cを入力として、mを出力する。
正当性として、任意のparams←Setup(1λ),任意の(pk,sk)←KGen(params)についてm＝Dec(sk,Enc(pk,m))が成り立つ。また、準同形演算(＋)が存在し、Enc(pk,m0＋m1)=Enc(pk,m0)(＋)Enc(pk,m1)が成り立つ。
【００４０】
ここでは、再乱数化可能な公開鍵暗号はIND−CPA安全性を持つと仮定する。すなわち、任意の多項式時間で動くチューリング機械Aに対し、
【００４１】
【数７】
0006437416.tif 000008
【００４２】
が成り立つ。
【００４３】
具体的には、青野らの方式などがある（例えば、参考文献４参照。）。
【００４４】
［名寄せシステム、装置及び方法］
以下、図面を参照して、名寄せシステム、装置及び方法の一実施形態について説明する。名寄せシステムは、図１に示すように、第０装置、第１装置、・・・、第ｎ−１装置を例えば備えている。第０装置、第１装置、・・・、第ｎ−１装置のそれぞれが名寄せ装置である。第０装置は、暗号部２及び復号部５を例えば備えている。第１装置から第ｎ−２装置は、有界ノイズ加算部６及び暗号部２を例えば備えている。第ｎ−１装置は、維持置換撹乱部１、暗号部２、撹乱部３及び並替部４を例えば備えている。名寄せ装置の各部が、図２の各ステップの処理を行うことにより、名寄せ方法が実現される。
【００４５】
ｎを１以上の所定の整数として、第０装置から第ｎ−１装置はそれぞれパーティP0,・・・,Pn−1である。P0,・・・,Pn−1はそれぞれτ0,・・・,τn−1を有している。τiはA=∪i<nAiであるようなAiを属性として持ち、
【００４６】
【数８】
0006437416.tif 000009
【００４７】
としたときτi:R→Viとする。ここで、Rはiによらず一定であるということは、あるIDとなる属性が存在し、その属性値がどのテーブルでも同一だということである。なお、P0は準同型性を持つ公開鍵暗号の鍵生成をあらかじめ行い、公開鍵は配布済であるとする。
また、簡単のため暗号の平文空間と属性の値域が同一であるとする。このとき、名寄せプロトコルの例は、図３に示される。
【００４８】
＜ステップＳ１＞
第１装置から第ｎ−１装置のそれぞれは、自身が有するテーブルの各レコードの各属性ａの属性値に対して所定のパラメータbaに従い有界ノイズ加算を行う（ステップＳ１）。この処理は、第１装置から第ｎ−１装置のそれぞれに備えられた有界ノイズ加算部１により行われる。有界ノイズ加算後の属性値は、暗号部２に出力される。
【００４９】
ステップＳ１の処理は、図３の名寄せプロトコルの「１：」から「４：」に対応している。
【００５０】
＜ステップＳ２＞
第０装置から第ｎ−１装置のそれぞれは、有界ノイズ加算後の属性値を第０装置のみが復号できるように暗号化することにより自身が有するテーブルを暗号化する（ステップＳ２）。この処理は、第１装置から第ｎ−１装置のそれぞれに備えられた暗号部２により行われる。暗号化は、例えば、第０装置の、準同型性を持つ公開鍵暗号方式における公開鍵を用いて行われる。暗号化されたテーブルは、第ｎ−１装置に出力される。
【００５１】
ステップＳ２の処理は、図３の名寄せプロトコルの「５：」から「７：」に対応している。
【００５２】
＜ステップＳ３＞
第ｎ−１装置は、第０装置からｎ−１装置が暗号化したテーブルを名寄せする。この名寄せしたテーブルを「名寄せテーブル」とする。
【００５３】
第ｎ−１装置の撹乱部３は、第０装置が有するテーブルの属性の集合A0として、名寄せテーブルの各属性a∈A0の属性値に対して所定のパラメータbaに従い有界ノイズを発生させ、発生させた有界ノイズを上記第０装置のみが復号できるように暗号化し、暗号化された有界ノイズを名寄せテーブルの各属性a∈A0の属性値に加算することにより名寄せテーブルの撹乱を行う（ステップＳ３）。撹乱後の名寄せテーブルは、並替部４に出力される。
【００５４】
ステップＳ３の処理は、図３の名寄せプロトコルの「８：」から「１２：」に対応している。
【００５５】
＜ステップＳ４＞
第ｎ−１装置の並替部４は、撹乱後の名寄せテーブルのレコードを並び替えることにより並替後テーブルを作成する（ステップＳ４）。例えば、並替部４は、レコードをランダムにシャッフルする。並替後テーブルは、第０装置に送信される。
【００５６】
ステップＳ４の処理は、図３の名寄せプロトコルの「１３：」から「１４：」に対応している。
【００５７】
＜ステップＳ５＞
第０装置の復号部５は、並替後テーブルの各属性値を復号する（ステップＳ５）。復号は、例えば、第０装置の、準同型性を持つ公開鍵暗号方式における秘密鍵を用いて行われる。
【００５８】
ステップＳ５の処理は、図３の名寄せプロトコルの「１５：」から「１６：」に対応している。
【００５９】
このように、暗号化したまま有界ノイズ加算によるPk-匿名化をすることにより、復元する主体である第０装置（P0）に対しプライバシーを保護することができる。
【００６０】
以下、有界ノイズ加算における所定のパラメータbaの設定の例について説明する。
【００６１】
背景知識を持たないP0に対して個人識別を防ぐためには、a∈A0については、kをセキュリティパラメータとして、
【００６２】
【数９】
0006437416.tif 000010
【００６３】
としたとき、baを
【００６４】
【数１０】
0006437416.tif 000011
【００６５】
と設定する。この場合には、名寄せプロトコルの「２：」から「４：」の処理は行われない。すなわち、ステップＳ１の処理は行われない。
【００６６】
背景知識を持つP0に対して個人識別を防ぐためには、a∈Aについて、kをセキュリティパラメータとして、
【００６７】
【数１１】
0006437416.tif 000012
【００６８】
としたとき、baを
【００６９】
【数１２】
0006437416.tif 000013
【００７０】
と設定する。
【００７１】
[プログラム及び記録媒体]
名寄せシステム、装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７２】
また、名寄せ装置における各処理をコンピュータによって実現する場合、名寄せ装置又はモデル作成装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００７３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７４】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００７５】
［変形例］
第１装置から第ｎ−１装置における維持置換撹乱部１によるステップＳ１の処理は行われなくてもよい。この場合、第０装置から第ｎ−１装置のそれぞれは、自身が有するテーブルの各属性値を第０装置のみが復号できるように暗号化することにより自身が有するテーブルを暗号化する（ステップＳ２）
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００７６】
２      暗号部
３      撹乱部
４      並替部
５      復号部
６      有界ノイズ加算部
【図１】
0006437416.tif 000016
【図２】
0006437416.tif 000017
【図３】
0006437416.tif 000018