(57)【特許請求の範囲】
【請求項１】
テーブルは複数のレコードを含み、Ａを所定の２以上の整数とし、各レコードはレコード識別子及びＡ個の属性値を含み、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数とし、α＝（（ｋ−１）／（Ｎ−１））１／Ｍとして、ｅｓｓ  ｉｎｆ・を・の本質的下限として、上記テーブルに含まれる属性のそれぞれについて、そのそれぞれの属性ａの属性値をｖとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱装置に用いられる上記パラメータｐａを決定するデータベース撹乱パラメータ決定装置において、
下記式を満たすパラメータｐａを決定するパラメータ決定部
【数１０】
0005639094.tif 000011
を含むデータベース撹乱パラメータ決定装置。
【請求項２】
請求項１のデータベース撹乱パラメータ決定装置において、
上記属性ａが数値属性であり、上記関数Ａａ（ｐａ）ｖ，ｖ’が下記式により定義される分散２ｐａ２のラプラス分布である確率密度関数である場合には、||・||１を・のＬ１ノルムとして、
【数１１】
0005639094.tif 000012
上記パラメータ決定部は、下記式を満たすパラメータｐａを決定し、
【数１２】
0005639094.tif 000013
｜Ｖａ｜を集合Ｖａの要素の数として、上記属性ａがカテゴリ属性であり、上記関数Ａａ（ｐａ）ｖ，ｖ’が上記属性値ｖを所定の確率（ｐａ＋（１−ｐａ）／｜Ｖａ｜）で維持し所定の確率（１−ｐａ）／｜Ｖａ｜で上記属性ａの属性値ｖ以外の属性値に置換する関数である場合には、上記パラメータ決定部は、下記式を満たすパラメータｐａを決定する、
【数１３】
0005639094.tif 000014
データベース撹乱パラメータ決定装置。
【請求項３】
請求項１又は２のデータベース撹乱パラメータ決定装置と、
上記データベース撹乱装置と、
を含むデータベース撹乱システム。
【請求項４】
テーブルは複数のレコードを含み、Ａを所定の２以上の整数とし、各レコードはレコード識別子及びＡ個の属性値を含み、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数とし、α＝（（ｋ−１）／（Ｎ−１））１／Ｍとして、ｅｓｓ  ｉｎｆ・を・の本質的下限として、上記テーブルに含まれるＭ以下の個数の属性のそれぞれについて、そのそれぞれの属性ａの属性値をｖとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行う撹乱部を含み、
上記パラメータｐａは、下記式の関係を満たす、
【数１４】
0005639094.tif 000015
データベース撹乱装置。
【請求項５】
テーブルは複数のレコードを含み、Ａを所定の２以上の整数とし、各レコードはレコード識別子及びＡ個の属性値を含み、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数とし、α＝（（ｋ−１）／（Ｎ−１））１／Ｍとして、ｅｓｓ  ｉｎｆ・を・の本質的下限として、上記テーブルに含まれるＭ以下の個数の属性のそれぞれについて、そのそれぞれの属性ａの属性値をｖとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱方法において、
パラメータ決定部が、下記式を満たすパラメータｐａを決定するパラメータ決定ステップと、
【数１５】
0005639094.tif 000016
撹乱部が、上記テーブルに含まれるＭ以下の個数の各属性ａの属性値ｖについて、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とする上記撹乱ステップと、
を含むデータベース撹乱方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プライバシーを保護しながらデータマイニングを行う技術に関する。
【背景技術】
【０００２】
いわゆるＰｋ−匿名性を満たすデータベース撹乱技術及びそのデータベース撹乱技術で用いられるパラメータ決定技術が、非特許文献１で提案されている（例えば、非特許文献１参照。）。具体的には、非特許文献１には、攻撃者がＡ個の属性の全てを見ることができるとした場合にＰｋ−匿名性を実現するためのデータベース撹乱技術及びパラメータ決定技術が記載されている。
【０００３】
Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】五十嵐大、他２名、「数値属性におけるｋ−匿名性を満たすランダム化手法」、ＣＳＳ２０１１、２０１１
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＭをＡ−１以下の整数として、攻撃者がＡ個の属性のうち任意のＭ個の属性を見ることができるとした場合にＰｋ−匿名性を実現するための技術は、非特許文献１には記載されていない。
【０００６】
この発明は、攻撃者がＡ個の属性のうち任意のＭ個の属性を見ることができるとした場合にＰｋ−匿名性を実現するためのデータベース撹乱パラメータ決定装置、データベース撹乱システム及び方法並びにデータベース撹乱装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明の一態様によるデータベース撹乱パラメータ決定装置は、テーブルは複数のレコードを含み、Ａを所定の２以上の整数とし、各レコードはレコード識別子及びＡ個の属性値を含み、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数とし、α＝（（ｋ−１）／（Ｎ−１））１／Ｍとして、ｅｓｓ  ｉｎｆ・を・の本質的下限として、テーブルに含まれる属性のそれぞれについて、そのそれぞれの属性ａの属性値をｖとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行うデータベース撹乱装置に用いられるパラメータｐａを決定するデータベース撹乱パラメータ決定装置において、下記式を満たすパラメータｐａを決定するパラメータ決定部
【０００８】
【数１】
0005639094.tif 000002
【０００９】
を含む。
【００１０】
この発明の一態様によるデータベース撹乱システムは、上記データベース撹乱パラメータ決定装置と、上記データベース撹乱装置と、を含む。
【００１１】
この発明の一態様によるデータベース撹乱装置は、テーブルは複数のレコードを含み、Ａを所定の２以上の整数とし、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数とし、α＝（（ｋ−１）／（Ｎ−１））１／Ｍとして、ｅｓｓ  ｉｎｆ・を・の本質的下限として、テーブルに含まれるＭ以下の個数の属性のそれぞれについて、そのそれぞれの属性ａの属性値をｖとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行う撹乱部を含み、パラメータｐａは、下記式の関係を満たす。
【００１２】
【数２】
0005639094.tif 000003
【発明の効果】
【００１３】
攻撃者がＡ個の属性のうち任意のＭ個の属性を見ることができるとした場合にも、Ｐｋ−匿名性を実現することができる。
【図面の簡単な説明】
【００１４】
【図１】第一実施形態のデータベース撹乱システムを説明するためのブロック図。
【図２】第一実施形態のデータベース撹乱システムを説明するための流れ図。
【図３】撹乱の対象となるデータベースの例を説明するための図。
【図４】撹乱の対象となるデータベースの例を説明するための図。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、この発明の実施形態を説明する。
【００１６】
［第一実施形態］
第一実施形態のデータベース撹乱システムは、図１に例示するように、データ提供者装置２、匿名データサーバ１及び分析ユーザ装置３を備えている。
【００１７】
匿名データサーバ１は、匿名化されたデータを記憶するサーバである。匿名データサーバ１は、パラメータ決定部１１及び記憶部１２を例えば備えている。パラメータ決定部１１が、特許請求の範囲のデータベース撹乱パラメータ決定装置に対応している。
【００１８】
データ提供者装置２は、データを匿名データサーバ１に預けようとする主体である。データ提供者装置２は、例えば、データを匿名データサーバ１に預けようとするユーザが有するＰＣ、携帯情報端末装置等のコンピュータである。データ提供者装置２は、２以上存在していてもよい。データ提供者装置２は、撹乱部２１を例えば備えている。撹乱部２１が、特許請求の範囲のデータベース撹乱装置に対応している。
【００１９】
分析ユーザ装置３は、匿名化されたデータに基づいて集計処理を行う装置である。分析ユーザ装置３も、２以上存在していてもよい。
【００２０】
まず、撹乱の対象となるデータベースについて説明する。撹乱の対象となるデータベースは、図３及び図２に例示するように、複数のレコードから構成されている。
【００２１】
各レコードは、レコード識別子と少なくとも１つの属性値とから構成されている。レコード識別子は、個人を識別する識別子であり、いわゆるレコードＩＤである。レコード識別子は、例えば氏名や氏名に対応するＩＤ番号である。この実施形態では、レコード識別子は、データ提供者又はデータ提供者装置２を識別する識別子である。
【００２２】
各属性値は、ｎ次元実数ベクトルの部分集合Ｖに含まれるベクトルであり、いわゆる数値属性値である。ｎは、１以上の整数である。ｎ＝１であり属性が例えば「中間テストの点数」や「期末テストの点数」である場合には、属性値は０から１００までの何れかの整数である。
【００２３】
また、各属性値は、いわゆるカテゴリ属性値であってもよい。カテゴリ属性値とは、例えば性別等の属性値であり、数値属性値とは異なり属性値の取り得る値がいくつかに制限されている属性値のことである。
【００２４】
図３は、各属性が数値属性である場合のデータベースを例示している。一方、図４は、数値属性の属性とカテゴリ属性の属性との両方を含むデータベースを例示している。
【００２５】
＜ステップＳ１＞
まず、匿名データサーバ１のパラメータ決定部１１は、下記式を満たすパラメータｐａを決定する（ステップＳ１）。決定されたパラメータｐａは、各データ提供者装置２に送信される。属性の種類の数をＡとする。Ａは、２以上の所定の整数である。パラメータ決定部１１は、属性ａ（ａ＝１，２，…，Ａ）のそれぞれについて、パラメータｐａを決定する。パラメータｐａは、例えばいわゆる二分法により計算される。
【００２６】
【数３】
0005639094.tif 000004
【００２７】
ここで、ｋをセキュリティパラメータとし、|Ｎ|をレコードの数とし、ＭをＡ−１以下の所定の自然数として、α＝（（ｋ−１）／（Ｎ−１））１／Ｍである。また、ｅｓｓ  ｉｎｆ・は、・の本質的下限である。
【００２８】
関数ｆ（ｘ）の定義域をχとすると、関数ｆ（ｘ）の本質的下限ｅｓｓ  ｉｎｆ  ｆ（ｘ）は、具体的には以下のように書ける。μ（｛ｆ＜ｂ｝）を、関数ｆ（ｘ）＜ｂとなる領域の測度（例えば、面積又は体積）とする。下記式のＲは実数を意味する。
【００２９】
【数４】
0005639094.tif 000005
【００３０】
Ｖａは属性ａの撹乱前の属性値ｖ，ｕの定義域であり、Ｖ’ａは属性ａの撹乱後の属性値ｖ’，ｕ’の定義域である。Ａａ（ｐａ）ｖ，ｖ’は、所定のパラメータｐａにより定まる関数であり、撹乱前の属性値ｖが撹乱後に属性値ｖ’となる確率を表す。Ａａ（ｐａ）ｕ，ｖ’、Ａａ（ｐａ）ｖ，ｕ’及びＡａ（ｐａ）ｕ，ｕ’についても、Ａａ（ｐａ）ｖ，ｖ’と同様である。
【００３１】
属性ａが数値属性であり、関数Ａａ（ｐａ）ｖ，ｖ’が下記式により定義される分散２ｐａ２のラプラス分布である確率密度関数である場合には、
【００３２】
【数５】
0005639094.tif 000006
【００３３】
パラメータ決定部１１は、具体的には下記式を満たすパラメータｐａを決定する。μは、例えば０である。下記式において、||・||１は・のＬ１ノルムであり、ｌｏｇの底はネイピア数ｅである。
【００３４】
【数６】
0005639094.tif 000007
【００３５】
また、属性ａがカテゴリ属性であり、関数Ａａ（ｐａ）ｖ，ｖ’が、属性値ｖを、所定の確率（ｐａ＋（１−ｐａ）／｜Ｖａ｜）で維持し、所定の確率（１−ｐａ）／｜Ｖａ｜で属性ａの属性値ｖ以外の属性値ｖ’に置換する関数である場合には、パラメータ決定部１１は、下記式を満たすパラメータｐａを決定する。｜Ｖａ｜は、集合Ｖａの要素の数である。
【００３６】
【数７】
0005639094.tif 000008
【００３７】
＜ステップＳ２＞
各データ提供者装置２の撹乱部２１は、撹乱の対象となる各属性の属性値について、パラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱する（ステップＳ２）。この実施形態では、各データ提供者装置２の撹乱部２１が、自身が持つ各属性ａの属性値ｖについて、パラメータｐａにより定まる関数Ａａ（ｐａ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とする。撹乱後の各属性値ｖ’は、匿名データサーバ１に送信される。
【００３８】
撹乱の対象となる属性ａが数値属性である場合には、上記関数Ａａ（ｐａ）ｖ，ｖ’は確率密度関数である。例えば、関数Ａａ（ｐａ）ｖ，ｖ’は、下記式により定義される分散２ｐａ２のラプラス分布である確率密度関数である。||・||１は、・のＬ１ノルムである。例えば、μ＝０とする。
【００３９】
【数８】
0005639094.tif 000009
【００４０】
撹乱の対象となる属性ａが数値属性である場合には、関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱とは、属性ａの撹乱前の属性値ｖ’に確率密度関数Ａａ（ｐ）ｖ，ｖ’に従う値を加算して撹乱後の属性値ｖ’とすることを意味する。すなわち、撹乱後の属性値ｖ’＝撹乱前の属性値ｖ＋確率密度関数Ａａ（ｐ）ｖ，ｖ’に従う値となる。
【００４１】
以下、「確率密度関数ｆに従う値」及び「ラプラス分布に従う値」について説明する。ここでは表記の簡略化のために、確率密度関数ｆと書く。確率密度関数ｆは上記確率密度関数Ａａ（ｐ）ｖ，ｖ’と同じと考えてよい。
【００４２】
１．「確率密度関数ｆに従う値」について
（１）確率密度関数ｆの定義域及び属性値が１次元の場合
（ｉ）累積分布関数Ｆ（ｘ）＝∫−∞ｘｆ（ｘ’）ｄｘ’を求める。
（ｉｉ）累積分布関数Ｆ（ｘ）の逆関数Ｆ−１を求める。
（ｉｉｉ）区間［０，１］上の一様乱数ｒを生成する。
（ｉｖ）Ｆ−１（ｒ）を「確率密度関数ｆに従う値」として出力する。
【００４３】
累積分布関数Ｆ（ｘ）や逆関数Ｆ−１が数式で得られる場合にはその数式に基づいてＦ−１（ｒ）を計算してもよいし、そうでない場合には数値計算によってＦ−１（ｒ）を計算してもよい。
【００４４】
（２）確率密度関数ｆの定義域及び属性値がｎ次元の場合
１．ｉ＝０，…，ｎ−１のそれぞれに対して、以下の（ｉ）（ｉｉ）を行う。
【００４５】
（ｉ）ｘ０からｘｉ−１までを固定し、ｘｉ＋１からｘｎ−１までを積分し、ｘｉだけを変数として残した確率密度関数ｆｉを求める。
【００４６】
【数９】
0005639094.tif 000010
【００４７】
（ｉｉ）確率密度関数ｆｉの定義域は１次元なので、上記「（１）確率密度関数ｆの定義域及び属性値が１次元の場合」で示した方法と同様の方法により、「確率密度関数ｆｉに従う値」を計算する。
【００４８】
ｉ＝０，…，ｎ−１のそれぞれに対して「確率密度関数ｆｉに従う値」を計算することにより、ｎ個の「確率密度関数ｆｉに従う値」が得られる。
【００４９】
なお、確率密度関数がラプラス分布の場合には、以下のようになる。
【００５０】
２．「ラプラス分布に従う値」について
（１）ラプラス分布の定義域及び属性値が１次元の場合
（ｉ）区間［０，１］上の一様乱数ｒ、区間（０，１）上の一様乱数ｂを生成する。
（ｉｉ）（−１）ｂσｌｏｇｒ＋μを「ラプラス分布に従う値」として出力する。
【００５１】
（２）ラプラス分布の定義域及び属性値がｎ次元の場合
（ｉ）上記「（１）ラプラス分布の定義域及び属性値が１次元の場合」で示した方法と同様の方法により、ｎ個の「ラプラス分布に従う値」であるｘ０，ｘ１，…，ｘｎ−１を計算する。
（ｉｉ）これらのｘ０，ｘ１，…，ｘｎ−１を「ラプラス分布に従う値」として出力する。
【００５２】
撹乱の対象となる属性ａがカテゴリ属性である場合には、関数Ａａ（ｐａ）ｖ，ｖ’は、属性値ｖを、所定の確率（ｐａ＋（１−ｐａ）／｜Ｖａ｜）で維持し、所定の確率（１−ｐａ）／｜Ｖａ｜で属性ａの属性値ｖ以外の属性値ｖ’に置換する関数である。属性値ｖを属性ａの属性値ｖ以外の属性値ｖ’に置換するとは、例えば、属性ａが性別であり属性値ｖが「男」である場合には、その属性値「男」を属性値「女」に置換することを意味する。維持確率ρの維持−置換撹乱の詳細については、参考文献１を参照のこと。
〔参考文献〕特開２０１１−１００１１６号公報
【００５３】
このようにして、属性値を撹乱することにより、攻撃者がＡ個の属性のうち任意のＭ個の属性を見ることができるとした場合において、Ｐｋ−匿名性を実現することができる。ここでは、その証明を省略する。
【００５４】
＜ステップＳ３＞
匿名データサーバ１は、各データ提供者装置２から受信した撹乱後の各属性値ｖ’を、その各データ提供者装置２に対応付けて記憶部１２に記憶する（ステップＳ３）。すなわち、データ提供者装置２のレコード識別子とそのデータ提供者装置から受信した撹乱後の各属性値ｖ’との組の複数が、匿名化されたデータベースとして記憶部１２に記憶される。
【００５５】
＜ステップＳ４＞
分析ユーザ装置３は、予め指定されたＭ個の属性についての情報である指定情報を、匿名データサーバ１に送信する（ステップＳ４）。Ｍ個の属性は、分析ユーザ装置３を操作する分析ユーザによって予め指定されていてもよいし、分析ユーザ自身によって予め指定されていてもよい。
【００５６】
＜ステップＳ５＞
匿名データサーバ１は、記憶部１２に記憶されたデータベースの中から、受信した指定情報により特定されるＭ個の属性の属性値の列を取り出して、分析ユーザ装置３に送信する（ステップＳ５）。例えば、データベースが図３に例示するデータベースであり、Ｍ＝２であり、「中間テストの点数」及び「期末テストの点数」という２個の属性が指定されている場合には、属性「中間テストの点数」の属性値により構成される属性値の列ａ１と、属性「期末テストの点数」の属性値により構成される属性値の列ａ２とが、分析ユーザ装置３に送信される。
【００５７】
＜ステップＳ６＞
分析ユーザ装置３の集計部３１は、受信したＭ個の属性値の列を用いて集計処理を行う（ステップＳ６）。集計部３１は、例えば、参考文献２に記載された反復ベイズ手法等を用いて、クロス集計等の集計結果を推定する。
【００５８】
〔参考文献２〕
五十嵐大，外２名，「多値属性に適用可能な効率的プライバシー保護クロス集計」，コンピュータセキュリティシンポジウム２００８
【００５９】
［変形例等］
撹乱部２１は、匿名データサーバ１に備えられていてもよい。すなわち、この場合、各データ提供者装置２から受信した属性値を、匿名データサーバ１に備えられた撹乱部２１が上記と同様に撹乱をして記憶部１２に記憶する。
【００６０】
また、パラメータ決定部１１が、各データ提供者装置２に備えられていてもよい。
【００６１】
また、データ提供者装置２と匿名データサーバ１とが同一の装置に備えられていてもよい。
【００６２】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【００６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６５】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００６６】
１      匿名データサーバ
１１    パラメータ決定部
１２    記憶部
２      データ提供者装置
２１    撹乱部
３      分析ユーザ装置
３１    集計部
【図１】
0005639094.tif 000017
【図２】
0005639094.tif 000018
【図３】
0005639094.tif 000019
【図４】
0005639094.tif 000020