(57)【要約】【課題】許容できる個人識別リスクに応じてサンプリング割合を適切に決定する匿名化テーブル生成技術を提供する。【解決手段】許容可能個人識別リスクξallowableに対して所定の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部１１０と、匿名化前テーブルτから[pn]個（ただし、nは匿名化前テーブルτのレコード数）のレコードを一様ランダムに抜き出すことにより匿名化テーブルτ’を生成するサンプリング部１２０とを含む。【選択図】図１
2018055612.tif 000002
【特許請求の範囲】
【請求項１】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、n0を攻撃者が前記匿名化前テーブルτについて知っていると考えられるレコード数、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、
前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部と、
【数１６】
2018055612.tif 000018
前記匿名化前テーブルτから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部と
を含む匿名化テーブル生成装置。
【請求項２】
請求項１に記載の匿名化テーブル生成装置であって、
前記サンプリング割合生成部は、二分法を用いて前記サンプリング割合pを求める匿名化テーブル生成装置。
【請求項３】
τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、n0を攻撃者が前記匿名化前テーブルτについて知っていると考えられるレコード数、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、
匿名化テーブル生成装置が、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成方法であって、
前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成ステップと、
【数１７】
2018055612.tif 000019
前記匿名化前テーブルτから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリングステップと
を含む匿名化テーブル生成方法。
【請求項４】
請求項１または２に記載の匿名化テーブル生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、個人のプライバシ情報を保護するための匿名化技術に関し、特にサンプリングに関する。
【背景技術】
【０００２】
様々な主体からデータを集約し分析する場合を考える。このとき、データには個人のプライバシ情報が含まれることもあるため、データをそのまま他者に渡すと個人のプライバシ情報が漏えいする危険性がある。そのため、プライバシ情報が漏えいする危険が低減するようにデータを加工する方法として、匿名化技術の研究が進められている。
【０００３】
従来からある匿名化技術の一手法として、サンプリングと呼ばれるレコードを抽出する方法がある（非特許文献１）。サンプリングでは、レコードの集合であるテーブルの公開範囲を一部のレコードに限定することによりプライバシを保護する。例えば、各種センサスデータの匿名化では、英国、カナダ、アメリカ等でサンプリング割合（データ全体に対する公開範囲の割合）として0.01や0.03が用いられている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“匿名化技術の現状について”，［online］，［平成28年9月14日検索］，インターネット<URL:http://www.kantei.go.jp/jp/singi/it2/pd/wg/dai1/siryou2_3.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の通り、公的統計では、経験的に0.01、0.03、0.05などの値がサンプリング割合として用いられてきた。しかし、これらの値は主に経験則から求められたものにすぎず、これらの値を用いてサンプリングすることにより、どの程度個人が識別されてしまうリスク（以下、個人識別リスクという）が低減できているのかはよくわからないのが現状である。
【０００６】
また、サンプリングの効果を測る研究として母集団一意性を評価することが行われているが、母集団一意性の評価は必ずしも個人識別リスクの低減を意味するわけではなく、個人識別リスクが具体的にどの程度低減しているかは自明ではない。
【０００７】
そこで本発明は、許容できる個人識別リスクに応じてサンプリング割合を適切に決定する匿名化テーブル生成技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、τを匿名化前テーブル、nを前記匿名化前テーブルτのレコード数、n0を攻撃者が前記匿名化前テーブルτについて知っていると考えられるレコード数、ξallowableを許容可能個人識別リスク、[x]を実数xに対してxを超えない最大の整数を表すものとし、前記匿名化前テーブルτから匿名化テーブルτ’を生成する匿名化テーブル生成装置であって、前記許容可能個人識別リスクξallowableに対して以下の式を満たす実数p(p<1)をサンプリング割合として生成するサンプリング割合生成部と、
【０００９】
【数１】
2018055612.tif 000003
【００１０】
前記匿名化前テーブルτから[pn]個のレコードを一様ランダムに抜き出すことにより前記匿名化テーブルτ’を生成するサンプリング部とを含む。
【発明の効果】
【００１１】
本発明によれば、サンプリングにより匿名化テーブルを生成する際、許容可能個人識別リスクに応じてサンプリング割合を適切に決定することができるようになる。
【図面の簡単な説明】
【００１２】
【図１】匿名化テーブル生成装置１００の構成を示すブロック図。
【図２】匿名化テーブル生成装置１００の動作を示すフローチャート。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
＜定義と記法＞
集合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’に対して、τを任意の匿名化前テーブル、τ’を任意の匿名化テーブルとして、δ(τ)= τ’・πが成り立つことをいう。この式は匿名化前テーブルにデータ保護処理を施してレコードのシャッフルを行ったものが匿名化テーブルであることを示している。
【００２５】
以下では、Τ, Π, Δが確率事象として互いに独立である場合に、同様の式Δ(Τ)=Τ’・Πが成り立つ場合について考えていくことにする。
【００２６】
＜背景知識の意義＞
攻撃者が有する匿名化前テーブルについての背景知識とサンプリングによる個人識別リスクの低減との関係について考察する。
【００２７】
まず、攻撃者がある個人のレコードの属性値（の一部）を知っていて、その個人を匿名化テーブルから特定しようとする場合について考える。このとき、もしサンプリングされた後の匿名化テーブルに攻撃者の知っている属性値を持つレコードが1つしかなかったとしても、そのレコードは匿名化前テーブルに複数存在している可能性がある。そのため、攻撃者にとって、サンプリングした場合はサンプリングしていない場合と比較して、その1つしかないレコードが攻撃者が特定しようとしている個人のものであるかどうかがわかりづらくなっている。つまり、サンプリングにより個人識別リスクが低減しているといえる。
【００２８】
次に、攻撃者が匿名化前テーブルの値すべてを知っている場合について考える。このような攻撃者が例えば匿名化前テーブルに1つしかない属性値を持つ個人を特定したい場合、その個人がサンプリングされると、確実に匿名化テーブルのうちどのレコードが当該の個人であるか特定できてしまう。そのため、サンプリングにより個人識別リスクが低減できていない。
【００２９】
以上の考察をまとめると、サンプリングが個人識別リスクを低減できる場合は、攻撃者にとってサンプリングする匿名化前テーブルに不確実性がある場合と考えられる。言い換えれば、サンプリングする匿名化前テーブルに不確実性があれば、匿名化テーブルにある属性値を持つレコードが1つしかなかったとしても、匿名化前テーブルには複数あった可能性があるため、個人識別は難しくなる。このような不確実性が生じる状況として以下の2つケースが考えられる。
ケース(1)：攻撃者の匿名化前テーブルに関する背景知識が制限されているケース。
ケース(2)：サンプリングをする前に（攻撃者の知らない）処理が行われるケース。
【００３０】
以下説明していく第一実施形態では、ケース(1)を扱う。つまり、攻撃者の匿名化前テーブルに関する背景知識が制限されている場合において、サンプリング割合と個人識別リスクの関係を導出する。
【００３１】
＜第一実施形態＞
以下、個人識別リスクの指標、攻撃者についての仮定（攻撃者モデル）、個人識別リスクの評価について順に説明していく。
【００３２】
［個人識別リスクの指標］
確率的な匿名化を行った際の個人識別リスクの評価指標として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 Scienc, pp.225-241, 2015.
【００３３】
しかし、Pk-匿名性は任意の攻撃者を想定している（つまり、背景知識に制限がない攻撃者も想定している）ため、上述した通り、ケース(1)を前提とする場合、Pk-匿名性を用いて議論を進めることはできない。そこで、ここではPk-匿名性にならった新たなリスク指標を、背景知識を制限した攻撃者に対する個人識別リスクの指標として定義する。
【００３４】
匿名化処理Δと匿名化テーブルτ’が、任意の匿名化前テーブルτ、匿名化前テーブルτに含まれる任意のレコードr∈R、匿名化テーブルτ’に含まれる任意のレコードr’∈Rがある背景知識を有する攻撃者fTに対して次式を満たす場合、攻撃者fTに対して個人識別リスクがξであるという。
【００３５】
【数２】
2018055612.tif 000004
【００３６】
［攻撃者についての仮定（攻撃者モデル）］
攻撃者が匿名化前テーブルの一部について知識がある場合を考える。例えば、各都道府県の患者情報を集めて匿名化する場合、神奈川県の病院の勤務者は神奈川県の患者情報については知っているが、神奈川県以外の全国各都道府県の情報については未知であるというような場合が相当する。
【００３７】
そこで、以下のような攻撃者を仮定する。
仮定(1)：n個のレコードから構成される匿名化前テーブルτのうち、その一部であるn0個のレコードから構成される部分匿名化前テーブルτ0の値を知っている。
仮定(2)：攻撃者は自分自身が知らないレコードの値の分布を現在自身が知っているレコードの分布と同じであると推測する。
【００３８】
攻撃者はn0個のレコードから構成される部分匿名化前テーブルτ0以外の知識はないため、知らないレコードの値を一様であると推定することに比べても、仮定(2)は現実的なものであると考えられる。
【００３９】
［個人識別リスクの評価］
匿名化手法としてサンプリングを考える。つまり、匿名化前テーブルを構成するレコード数をnとしたとき、サンプリングした後のレコード数が[pn]（pはサンプリング割合）となるように匿名化前テーブルのレコードの中から一様ランダムに抜き出すことを考える。
【００４０】
以下、攻撃者モデルで定義した背景知識を持つ攻撃者（仮定(1）及び仮定(2)を満たす攻撃者）に対して、サンプリングによりどの程度個人識別リスクが低減されるかを評価する。簡単のため、pn=[pn]として説明をするが、一般性は失わない。
【００４１】
n^=n-n0-(pn-1)とする。また、匿名化前テーブルτのうち属性値vであるレコード数を#τ(v)と表すことにする。つまり、#τ(v)=|τ-1({v})|となる。
【００４２】
上記攻撃者モデルを満たす任意の攻撃者に対して式(1)を満たす個人識別リスクξ、つまり個人識別リスクξの最大値を最大個人識別リスクξmaxという。
【００４３】
このとき、レコード数がnであるような匿名化前テーブルτに対してpn個のレコードをサンプリングした場合、任意の部分匿名化前テーブルτ0（レコード数はn0）、匿名化テーブルτ’について、最大個人識別リスクξmaxは以下の式で表される。
【００４４】
【数３】
2018055612.tif 000005
【００４５】
ただし、i, jは１以上の整数であり、
【００４６】
【数４】
2018055612.tif 000006
とする。
【００４７】
以下、最大個人識別リスクξmaxの式(2)の導出について説明する。
【００４８】
個人が識別される確率の最大値である最大個人識別リスクξmaxを得るために、まず上記攻撃モデルを満たす攻撃者にとっての最適な匿名化前テーブルについての背景知識である部分匿名化前テーブルτ0と、匿名化テーブルτ’について考える。あるレコードrの特定を行うときに攻撃者にとって最も有利になる部分匿名化前テーブルτ0、匿名化テーブルτ’として、
【００４９】
【数５】
2018055612.tif 000007
【００５０】
が成り立つ場合、すなわち、部分匿名化前テーブルτ0でユニークだったレコードrが匿名化テーブルτ’でもユニークなレコードとなる場合で、
【００５１】
【数６】
2018055612.tif 000008
【００５２】
（ただし、R0は部分匿名化前テーブルτ0のすべてのレコードからなる集合）が成り立つ場合、すなわち、匿名化テーブルτ’のユニークなレコード以外は部分匿名化前テーブルτ0に含まれないという場合を考える。式(4)はレコードrがユニークであれば匿名化テーブルへの出現確率が小さくなること、式(5)は攻撃者にとって未知なレコードの個数を最小化することに由来する条件である。このとき、攻撃者にとって未知なレコード数がn^であることに注意すると、式(4)及び(5)を満たす攻撃者について、
【００５３】
【数７】
2018055612.tif 000009
【００５４】
【数８】
2018055612.tif 000010
【００５５】
【数９】
2018055612.tif 000011
【００５６】
【数１０】
2018055612.tif 000012
【００５７】
【数１１】
2018055612.tif 000013
【００５８】
【数１２】
2018055612.tif 000014
【００５９】
【数１３】
2018055612.tif 000015
【００６０】
ここで式(a)中のΤiはi番目の部分匿名化前テーブルの確率変数を示す。
【００６１】
以上より、式(2)が成り立つことがわかる。
【００６２】
また、式(2)を一般化した以下の式(2)’も成り立つ。レコード数がnであるような匿名化前テーブルτに対して[pn]個のレコードをサンプリングした場合、任意の部分匿名化前テーブルτ0（レコード数はn0）、匿名化テーブルτ’について、最大個人識別リスクξmaxは以下の式で表される。
【００６３】
【数１４】
2018055612.tif 000016
【００６４】
［匿名化テーブル生成装置］
以下、図１〜図２を参照して第一実施形態の匿名化テーブル生成装置１００について説明する。図１は、匿名化テーブル生成装置１００の構成を示すブロック図である。図２は、匿名化テーブル生成装置１００の動作を示すフローチャートである。
【００６５】
図１に示すように匿名化テーブル生成装置１００は、サンプリング割合生成部１１０と、サンプリング部１２０と、記録部１９０を含む。記録部１９０は、匿名化テーブル生成装置１００の処理に必要な情報を記録する構成部である。
【００６６】
匿名化テーブル生成装置１００は、n個のレコードから構成される匿名化前テーブルτと、攻撃者が匿名化前テーブルτについて知っていると考えられるレコード数n0と、許容することができる個人識別リスク（以下、許容可能個人識別リスクという）ξallowableを入力とし、匿名化テーブルτ’を生成する。なお、攻撃者が知っているレコード数n0と、許容可能個人識別リスクξallowableは事前に与えておき、記録部１９０に記録しておくのでもよい。
【００６７】
以下、図２に従い匿名化テーブル生成装置１００の動作について説明する。
【００６８】
サンプリング割合生成部１１０は、匿名化前テーブルτのレコード数nと、攻撃者が匿名化前テーブルτについて知っていると考えられるレコード数n0と、許容可能個人識別リスクξallowableから、次の式を満たす実数p(ただし、p<1)をサンプリング割合として生成する（Ｓ１１０）。
【００６９】
【数１５】
2018055612.tif 000017
【００７０】
上記式の右辺の値はpについて単調増加であるため、二分法を用いると、効率的に計算することができる。
【００７１】
サンプリング部１２０は、Ｓ１１０で生成したサンプリング割合pを用いて[pn]を計算し、匿名化前テーブルτから[pn]個のレコードを一様ランダムに抜き出すことにより匿名化テーブルτ’を生成する（Ｓ１２０）。
【００７２】
本実施形態の発明によれば、匿名化前テーブルτの一部のレコードの値を知っている攻撃者が存在する場合において、サンプリングにより匿名化テーブルを生成する際、許容可能個人識別リスクに応じて適切なサンプリング割合を決定することができる。その結果、許容可能個人識別リスクを考慮してサンプリングによる匿名化を実行することができる。
【００７３】
＜変形例＞
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７４】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００８３】
１００  匿名化テーブル生成装置
１１０  サンプリング割合生成部
１２０  サンプリング部
１９０  記録部
【図１】
2018055612.tif 000020
【図２】
2018055612.tif 000021