(57)【要約】【課題】許容できる個人識別リスクに応じてサンプリングまたはPRAMで必要なパラメータを適切に決定する匿名化テーブル生成技術を提供する。【解決手段】許容可能個人識別リスクξallowableに対して所定の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部１１０と、匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAM部１２０と、PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより匿名化テーブルτ’を生成するサンプリング部１３０とを含む。【選択図】図２
2018055613.tif 000002
【特許請求の範囲】
【請求項１】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、Aiを属性iの遷移確率行列 (i∈{0,..,m-1})、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、
前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部と、
【数２８】
2018055613.tif 000030
前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAM部と、
前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部と
を含む匿名化テーブル生成装置。
【請求項２】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、p<1を満たす実数pをサンプリング割合、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、
前記許容可能個人識別リスクξallowableに対して以下の式を満たす属性iの遷移確率行列 Ai(i∈{0,..,m-1})を生成する遷移確率行列生成部と、
【数２９】
2018055613.tif 000031
前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAM部と、
前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部と
を含む匿名化テーブル生成装置。
【請求項３】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、Aiを属性iの遷移確率行列 (i∈{0,..,m-1})、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
匿名化テーブル生成装置が、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成方法であって、
前記匿名化テーブル生成装置が、前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成ステップと、
【数３０】
2018055613.tif 000032
前記匿名化テーブル生成装置が、前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAMステップと、
前記匿名化テーブル生成装置が、前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリングステップと
を含む匿名化テーブル生成方法。
【請求項４】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、p<1を満たす実数pをサンプリング割合、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
匿名化テーブル生成装置が、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成方法であって、
前記匿名化テーブル生成装置が、前記許容可能個人識別リスクξallowableに対して以下の式を満たす属性iの遷移確率行列 Ai(i∈{0,..,m-1})を生成する遷移確率行列生成ステップと、
【数３１】
2018055613.tif 000033
前記匿名化テーブル生成装置が、前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAMステップと、
前記匿名化テーブル生成装置が、前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリングステップと
を含む匿名化テーブル生成方法。
【請求項５】
請求項１または２に記載の匿名化テーブル生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、個人のプライバシを保護するための匿名化技術に関し、特にノイズ付加とサンプリングを組み合わせた技術に関する。
【背景技術】
【０００２】
様々な主体からデータを集約し分析する場合を考える。このとき、データには個人のプライバシ情報が含まれることもあるため、データをそのまま他者に渡すと個人のプライバシ情報が漏えいする危険性がある。そのため、プライバシ情報が漏えいする危険が低減するようにデータを加工する方法として、匿名化技術の研究が進められている。
【０００３】
匿名化技術の安全性を測定する基準として、「攻撃者が個人を特定する確率が1/kである」というPk-匿名性がある（非特許文献１）。また、具体的なデータ加工方法としてPRAM(Post RAndomization Method)と呼ばれる、パラメータに基づき決定される確率に従い個人の属性値を異なる属性値に変更する手法がある（非特許文献１）。PRAMはノイズを付加することにより匿名化する方法に相当するものであり、このPRAMを適切なパラメータで実行することによりPk-匿名性を満たすようにできることが知られている。
【０００４】
また、その他の匿名化技術として、サンプリングと呼ばれる、レコードを抽出する方法がある（非特許文献２）。サンプリングでは、レコードの集合であるテーブルの公開範囲を一部のレコードに限定することによりプライバシを保護する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】D. Ikarashi, R. Kikuchi, K. Chida, and K. Takahashi, “k-anonymous Microdata Release via Post Randomisation Method”, Advances in Information and Computer Security-10th International Workshop on Security, IWSEC 2015, Volume 9241 of the series Lecture Notes in Computer Science, pp.225-241, 2015.
【非特許文献２】“匿名化技術の現状について”，［online］，［平成28年9月14日検索］，インターネット<URL:http://www.kantei.go.jp/jp/singi/it2/pd/wg/dai1/siryou2_3.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述の通り、Pk-匿名性を満たす匿名化方法としてPRAMがあるが、PRAMのみを用いて匿名化する場合、攻撃者が個人を識別できる確率を低くしようとすると、テーブルとして表現されるデータに付加するノイズの量が大きくなり、匿名化後のデータの有用性が低くなってしまうということがある。このため、匿名化後のデータの有用性低下を抑制しようとすると、個人識別リスクを十分に低減することができない場合がある。
【０００７】
そこで本発明は、許容できる個人識別リスクに応じてサンプリングまたはPRAMで必要なパラメータを適切に決定する匿名化テーブル生成技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、Aiを属性iの遷移確率行列 (i∈{0,..,m-1})、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部と、
【０００９】
【数１】
2018055613.tif 000003
【００１０】
前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAM部と、前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部とを含む。
【００１１】
本発明の一態様は、τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、mを前記匿名化前テーブルτのレコードを構成する属性の数、前記匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、p<1を満たす実数pをサンプリング割合、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、前記許容可能個人識別リスクξallowableに対して以下の式を満たす属性iの遷移確率行列 Ai(i∈{0,..,m-1})を生成する遷移確率行列生成部と、
【００１２】
【数２】
2018055613.tif 000004
【００１３】
前記匿名化前テーブルτからPRAMによりPRAM適用後匿名化テーブルを生成するPRAM部と、前記PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部とを含む。
【発明の効果】
【００１４】
本発明によれば、PRAMにサンプリングを組み合わせて匿名化テーブルを生成する際、許容可能個人識別リスクに応じてサンプリングまたはPRAMで必要なパラメータを適切に決定することができるようになる。
【図面の簡単な説明】
【００１５】
【図１】匿名化前テーブルとPRAM適用後匿名化テーブルの一例を示す図。
【図２】匿名化テーブル生成装置１００の構成を示すブロック図。
【図３】匿名化テーブル生成装置１００の動作を示すフローチャート。
【図４】匿名化テーブル生成装置２００の構成を示すブロック図。
【図５】匿名化テーブル生成装置２００の動作を示すフローチャート。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１７】
＜定義と記法＞
集合Aに対して、|A|は集合Aの要素数を表すものとする。また、実数xに対して、[x]はxを超えない最大の整数を表すものとする。
【００１８】
データはレコード形式で表現され、レコードの集合をテーブルという。また、サンプリング割合p(ただし、pはp<1を満たす実数)でのサンプリングとは、テーブルがn個のレコードから構成されるとき、一様ランダムに[pn]個のレコードを抜き出すものである。
【００１９】
以下、テーブルに対する匿名化を議論するための定義等について説明する。
【００２０】
Τ, τをそれぞれ匿名化前のテーブル（以下、匿名化前テーブルという）の確率変数及びそのインスタンスとする。つまり、τは匿名化前テーブルである。
【００２１】
Τ’, τ’をそれぞれ匿名化後のテーブル（以下、匿名化テーブルという）の確率変数及びそのインスタンスとする。つまり、τ’は匿名化テーブルである。
【００２２】
R, R’をそれぞれ匿名化前テーブルのレコード集合、匿名化テーブルのレコード集合とする。つまり、Rは匿名化前テーブルτのすべてのレコードからなる集合、R’は匿名化テーブルτ’のすべてのレコードからなる集合である。
【００２３】
V, V’をそれぞれ匿名化前テーブルのレコードが取りうる属性値の組み合わせの集合、匿名化テーブルのレコードが取りうる属性値の組み合わせの集合とする。
【００２４】
Δ, δをそれぞれ匿名化処理（匿名化アルゴリズム）の確率変数及びそのインスタンスとする。
【００２５】
Π, πをそれぞれ定義域をR、値域をR’∪{φ}（ただし、|R’|≦|R|、φはサンプリングされなかったことを示す特別な記号）とするサンプリングの確率変数及びそのインスタンスとする。つまり、πはR→R’∪{φ}のサンプリングである。
【００２６】
ここで、匿名化前テーブルτ, 匿名化テーブルτ’, 匿名化処理δは、それぞれτ:R→V, τ’: R’→V’, δ: (R→V)→(R→V’) である関数とみなすこともできる。
【００２７】
δが匿名化処理であるとは、サンプリングπ:R→R’に対して、τを任意の匿名化前テーブル、τ’を任意の匿名化テーブルとして、δ(τ)= τ’・πが成り立つことをいう。この式は匿名化前テーブルにデータ保護処理を施してレコードのシャッフルを行ったものが匿名化テーブルであることを示している。
【００２８】
以下では、Τ, Π, Δが確率事象として互いに独立である場合に、同様の式Δ(Τ)=Τ’・Πが成り立つ場合について考えていくことにする。
【００２９】
fXを確率変数Xに関する確率密度関数とする。なお、確率変数が離散型である場合は、fXを確率関数ということもある。
【００３０】
以下、PRAMとPk-匿名性について説明する。なお、通常、レコードは複数の属性の値の組として表現されるが、ここでは、簡単のため、複数の属性をまとめて1つの属性とみなし、議論を進めることとする（図１参照）。
【００３１】
＜PRAM＞
PRAMとは、遷移確率行列と呼ばれる行列に基づき各レコードの値を確率的に書きかえる方法である。例えば、遷移確率行列をAとすると、要素Av,v’は匿名化前テーブルで属性値がv∈Vであったときにv’∈V’に変化する確率を表しており、この確率に従ってテーブルの値を1つずつ書き換えていく。
【００３２】
＜Pk-匿名性＞
Pk-匿名性とは、k-匿名性をランダム化にも適用できるよう確率空間に拡張したものであり、“匿名化テーブルの任意のレコードが誰のものか1/k以上の確率で当てることができない”ことを保証する。
【００３３】
まず、攻撃者による攻撃成功の確率（個人が識別される確率）を定義する。攻撃者fTとは、Tを匿名化前テーブルの集合として、定義域をT、値域を[0, 1]とする確率関数のことをいう。つまり、匿名化前テーブルの候補τ0, τ1,…について、攻撃者は匿名化前テーブルτiである確率がfT(τi)であると考えていることをモデル化している。
【００３４】
攻撃成功の確率とは、ある匿名化テーブルτ’、匿名化前テーブルτのレコードr∈R、匿名化テーブルτ’のレコードr’∈R、Δ(Τ)=Τ’・Πについて、以下の式で表現される確率をいう。
【００３５】
【数３】
2018055613.tif 000005
【００３６】
この確率が直観的に表しているのは、どのレコードが選択されたのかは知らない攻撃者に対して、匿名化前テーブルτのレコードrが匿名化されて匿名化テーブルτ’のレコードr’となる確率である。
【００３７】
この攻撃成功の確率を用いて、Pk-匿名性は以下のように定義される（非特許文献１）。
【００３８】
匿名化処理Δと匿名化テーブルτ’が、任意の背景知識を有する攻撃者fT、任意の匿名化前テーブルτ、匿名化テーブルτの任意のレコードr∈R、匿名化テーブルτ’の任意のレコードr’∈R について、
【００３９】
【数４】
2018055613.tif 000006
【００４０】
であるならば、匿名化処理と匿名化テーブルの組(Δ, τ’)はPk-匿名性を満たすという。
【００４１】
＜第一実施形態＞
以下、任意の背景知識を有する攻撃者fTに対して、PRAMとサンプリングを組み合わせることにより、どの程度個人識別リスクが低減できるのかを評価する。簡単のため、pn=[pn]として説明をするが、一般性は失わない。
【００４２】
［個人識別リスクの評価］
n個のレコードから構成される匿名化前テーブルτに対して、遷移確率行列Aに基づきPRAMを適用した後、pn個のレコードをサンプリングすることにより、匿名化テーブルτ’を生成した場合、次式で評価されるkを用いたPk-匿名性を満たす。
【００４３】
【数５】
2018055613.tif 000007
【００４４】
式(1)及び式(2)より、任意の攻撃者fTに対して以下の式が成り立つ。
【００４５】
【数６】
2018055613.tif 000008
【００４６】
そこで、この式の右辺のことを最大個人識別リスクξmaxということにする。
【００４７】
以下、式(2)の導出について説明する。Pk-匿名性の定義から攻撃成功の確率を見ていく。
【００４８】
【数７】
2018055613.tif 000009
【００４９】
【数８】
2018055613.tif 000010
【００５０】
最後の等式はTがΠ, Δと独立であることにより導出される。
【００５１】
非特許文献１の補題３より、式(a)が最大値を取るのは、匿名化前テーブルτを知っているような攻撃者である。すなわち、fT(τ)=1かつτ~∈Ts-{τ}（ただし、Tsは匿名化前テーブルの集合）についてf(τ~)=0となる場合、最大となる。よって、
【００５２】
【数９】
2018055613.tif 000011
【００５３】
【数１０】
2018055613.tif 000012
【００５４】
ただし、Pはサンプリングの集合を表す。
【００５５】
計算を簡単にするため、逆数をとると、
【００５６】
【数１１】
2018055613.tif 000013
【００５７】
ここで、サンプリングπによって抽出されるレコードの集合を
【００５８】
【数１２】
2018055613.tif 000014
【００５９】
と定義する。また、サンプリングπ、匿名化前テーブルτのレコードs∈R、匿名化テーブルτ’のレコードs’∈R’について
【００６０】
【数１３】
2018055613.tif 000015
【００６１】
と定義する。ただし、便宜上
【００６２】
【数１４】
2018055613.tif 000016
とする。
【００６３】
このとき、PRAMの処理はレコード毎であることに注意すると、式(b)は、
【００６４】
【数１５】
2018055613.tif 000017
【００６５】
【数１６】
2018055613.tif 000018
【００６６】
【数１７】
2018055613.tif 000019
【００６７】
【数１８】
2018055613.tif 000020
【００６８】
ここで非特許文献１の補題４より、π(r)=r’を満たす任意のサンプリングπについて、
【００６９】
【数１９】
2018055613.tif 000021
【００７０】
を最小化するようなAτ,τ’が存在すれば、
【００７１】
【数２０】
2018055613.tif 000022
【００７２】
は式(c)で最小となる。ここで、Aτ,τ’は、Aτ,τ’i,jを並べた行列を意味する。
【００７３】
そのようなAτ,τ’は任意のs≠rについてτ(s)=v, v≠τ(r)であり、任意のs’≠r’についてτ(s’)=v’, v’≠τ(r’)である。
【００７４】
また、πはサンプリングであるため、pn個のみサンプリングされることに注意すると、式(2)が導出される。
【００７５】
【数２１】
2018055613.tif 000023
【００７６】
［個人識別リスクの比較］
上述の通り、n個のレコードから構成される匿名化前テーブルτに対して、遷移確率行列Aに基づきPRAMを適用した後、pn個のレコードをサンプリングすることにより、匿名化テーブルτ’を生成した場合における最大個人識別リスクはξmax（具体的には式(2)の右辺の逆数）となる。
【００７７】
一方、PRAMを匿名化技術として用いた場合、つまり、n個のレコードから構成される匿名化前テーブルτに対して、遷移確率行列Aに基づきPRAMを適用することにより、匿名化テーブルτ’を生成した場合におけるのPk-匿名性のkは、非特許文献１より、
【００７８】
【数２２】
2018055613.tif 000024
となる。ここで、
【００７９】
【数２３】
2018055613.tif 000025
【００８０】
が成り立つため、PRAMにサンプリングを組み合わせて匿名化テーブルを生成することにより、最大個人識別リスクが低減されることがわかる。
【００８１】
［レコードが複数の属性から構成される場合］
ここまで、簡単のため、複数の属性をまとめて1つの属性として扱い、議論を進めてきたが、複数の属性がある場合も同様の結論が導かれる。ここでは、[pn]のまま扱う。
【００８２】
レコードを構成する属性がm個であり、匿名化前テーブルのレコードが取り得る属性の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後の匿名化テーブルであるPRAM適用後匿名化テーブルのレコードが取り得る属性の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）とする。
【００８３】
n個のレコードから構成される匿名化前テーブルτに対して、属性iの遷移確率行列Ai(i∈{0,..,m-1})に基づきPRAMを適用した後、[pn]個のレコードをサンプリングすることにより、匿名化テーブルτ’を生成した場合、次式で評価されるkを用いたPk-匿名性を満たす。
【００８４】
【数２４】
2018055613.tif 000026
【００８５】
したがって、最大個人識別リスクξmaxは、以下の式で表現される。
【００８６】
【数２５】
2018055613.tif 000027
【００８７】
［匿名化テーブル生成装置］
以下、図２〜図３を参照して第一実施形態の匿名化テーブル生成装置１００について説明する。図２は、匿名化テーブル生成装置１００の構成を示すブロック図である。図３は、匿名化テーブル生成装置１００の動作を示すフローチャートである。
【００８８】
図２に示すように匿名化テーブル生成装置１００は、サンプリング割合生成部１１０と、PRAM部１２０と、サンプリング部１３０と、記録部１９０を含む。記録部１９０は、匿名化テーブル生成装置１００の処理に必要な情報を記録する構成部である。
【００８９】
匿名化テーブル生成装置１００は、n個のレコードから構成される匿名化前テーブルτ（ただし、レコードを構成する属性の数をmとする）と、PRAM実行に必要な属性iの遷移確率行列Ai(i∈{0,..,m-1})、許容することができる個人識別リスク（以下、許容可能個人識別リスクという）ξallowableを入力とし、匿名化テーブルτ’を生成する。匿名化前テーブルτのレコードが取り得る属性値の組をV=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組をV’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）、属性iの遷移確率行列Ai(i∈{0,..,m-1})として、要素(Ai)v,v’は匿名化前テーブルで属性値がv∈Vであったときにv’∈V’に変化する確率を表している。
【００９０】
なお、遷移確率行列Ai(i∈{0,..,m-1})と、許容可能個人識別リスクξallowableは事前に与えておき、記録部１９０に記録しておくのでもよい。
【００９１】
以下、図２に従い匿名化テーブル生成装置１００の動作について説明する。
【００９２】
サンプリング割合生成部１１０は、匿名化前テーブルτのレコード数nと、遷移確率行列Ai(i∈{0,..,m-1})と、許容可能個人識別リスクξallowableから次の式を満たす実数p(ただし、p<1)をサンプリング割合として生成する（Ｓ１１０）。
【００９３】
【数２６】
2018055613.tif 000028
【００９４】
PRAM部１２０は、遷移確率行列Ai(i∈{0,..,m-1})用いて匿名化前テーブルτからPRAM適用後匿名化テーブルを生成する（Ｓ１２０）。具体的なPRAM実行方法については、非特許文献１、参考非特許文献１〜３にある方法を用いればよい。
（参考非特許文献１）五十嵐大, 千田浩司, 高橋克巳, “ランダム化データベース上のk-匿名性の一般的算出法”, In CSS, 2011.
（参考非特許文献２）五十嵐大, 千田浩司, 高橋克巳, “数値属性における, k-匿名性を満たすランダム化手法”, In CSS, 2011.
（参考非特許文献３）五十嵐大, 長谷川聡, 納竜也, 菊池亮, 千田浩司, “数値属性に適用可能な, ランダム化によりk-匿名性を保証するプライバシー保護クロス集計”, In CSS, 2012.
【００９５】
サンプリング部１３０は、Ｓ１１０で生成したサンプリング割合pを用いて[pn]を計算し、PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより匿名化テーブルτ’を生成する（Ｓ１３０）。
【００９６】
本実施形態の発明によれば、PRAMにサンプリングを組み合わせて匿名化テーブルを生成する際、許容可能個人識別リスクに応じてサンプリング割合を適切に決定することができる。また、PRAM単独で実行する場合に比して、PRAM実行後にサンプリングを実行する場合の方が攻撃成功の確率をより小さくすることができる。
【００９７】
＜第二実施形態＞
第一実施形態では、遷移確率行列Ai(i∈{0,..,m-1})を入力として、許容可能個人識別リスクξallowableに応じたサンプリング割合pを生成したが、逆でもよい。つまり、サンプリング割合pを入力として、許容可能個人識別リスクξallowableに応じた遷移確率行列Ai(i∈{0,..,m-1})を生成するのでもよい。
【００９８】
［匿名化テーブル生成装置］
以下、図４〜図５を参照して第二実施形態の匿名化テーブル生成装置２００について説明する。図４は、匿名化テーブル生成装置２００の構成を示すブロック図である。図５は、匿名化テーブル生成装置２００の動作を示すフローチャートである。
【００９９】
図４に示すように匿名化テーブル生成装置２００は、遷移確率行列生成部２１０と、PRAM部１２０と、サンプリング部１３０と、記録部１９０を含む。
【０１００】
匿名化テーブル生成装置２００は、n個のレコードから構成される匿名化前テーブルτ（ただし、レコードを構成する属性の数をmとする）と、サンプリング割合p(ただし、pはp<1を満たす実数)、許容可能個人識別リスクξallowableを入力とし、匿名化テーブルτ’を生成する。
【０１０１】
なお、サンプリング割合pと、許容可能個人識別リスクξallowableは事前に与えておき、記録部１９０に記録しておくのでもよい。
【０１０２】
以下、図４に従い匿名化テーブル生成装置２００の動作について説明する。
【０１０３】
遷移確率行列生成部２１０は、匿名化前テーブルτのレコード数nと、サンプリング割合pと、許容可能個人識別リスクξallowableから、次の式を満たすPRAM実行に必要な属性iの遷移確率行列Ai(i∈{0,..,m-1})を生成する（Ｓ２１０）。匿名化前テーブルτのレコードが取り得る属性値の組V=V0×V1×..×Vm-1（ただし、Viは属性iの値域(i∈{0,..,m-1})）、PRAM適用後匿名化テーブルのレコードが取り得る属性値の組V’=V0’×V1’×..×Vm-1’（ただし、Vi’は匿名化後の属性iの値域(i∈{0,..,m-1})）として、属性iの遷移確率行列Ai(i∈{0,..,m-1})の要素(Ai)v,v’は匿名化前テーブルで属性値がv∈Vであったときにv’∈V’に変化する確率を表すものである。具体的な遷移確率行列Aiの計算方法については、非特許文献１、参考非特許文献１〜３にある方法を用いればよい。
【０１０４】
【数２７】
2018055613.tif 000029
【０１０５】
PRAM部１２０は、Ｓ２１０で求めた遷移確率行列Ai(i∈{0,..,m-1})用いて匿名化前テーブルτからPRAM適用後匿名化テーブルを生成する（Ｓ１２０）。
【０１０６】
サンプリング部１３０は、サンプリング割合pを用いて[pn]を計算し、PRAM適用後匿名化テーブルから[pn]個のレコードを一様ランダムに抜き出すことにより匿名化テーブルτ’を生成する（Ｓ１３０）。
【０１０７】
本実施形態の発明によれば、PRAMにサンプリングを組み合わせて匿名化テーブルを生成する際、許容可能個人識別リスクに応じて遷移確率行列を適切に決定することができる。また、PRAM単独で実行する場合に比して、PRAM実行後にサンプリングを実行する場合の方が攻撃成功の確率をより小さくすることができる。
【０１０８】
＜変形例＞
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１０９】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１１０】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１１１】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１１２】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１１３】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１１４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１１５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１１８】
１００  匿名化テーブル生成装置
１１０  サンプリング割合生成部
１２０  PRAM部
１３０  サンプリング部
１９０  記録部
２００  匿名化テーブル生成装置
２１０  遷移確率行列生成部
【図１】
2018055613.tif 000034
【図２】
2018055613.tif 000035
【図３】
2018055613.tif 000036
【図４】
2018055613.tif 000037
【図５】
2018055613.tif 000038