(57)【特許請求の範囲】
【請求項１】
複数のレコードを含む第１の個票データの入力を受け、第２の個票データを出力するプライバシー保護装置であって、
前記第１の個票データの入力を受け付ける入力手段と、
前記入力手段によって受け付けられた前記第１の個票データを集計することにより第１の集計データを生成する集計手段と、
前記第１の集計データに対して予め定められた強度の乱数を付与することにより第２の集計データを生成する乱数付与手段と、
前記第２の集計データから、各要素が負の値ではない整数であり、且つ、全ての要素の総和が前記第２の集計データの全ての要素の総和と等しい、第３の集計データを生成する精緻化手段と、
前記第３の集計データから前記第２の個票データを生成する個票生成手段と、
前記第２の個票データを出力する出力手段と、を備えるプライバシー保護装置。
【請求項２】
前記精緻化手段は、前記第２の集計データの要素に関する最近傍探索を行うことにより前記第３の集計データを生成する、請求項１記載のプライバシー保護装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プライバシー保護装置に関する。
【背景技術】
【０００２】
近年、情報セキュリティ分野及びデータベース処理分野等において、プライバシーを保護しつつ有用なデータを公開するための様々な新しい基準及び手法が提案されている。これらの技術は、プライバシー保護データ公開（ＰＰＤＰ：Privacy-Preserving Data Publishing）技術等と呼ばれている。しかし、これらのＰＰＤＰ技術は、それぞれ攻撃者が持つ目的、能力及び背景知識に関する前提が異なり、その安全性について一概に議論することが困難であることから、実際のデータ活用に適用することは容易ではない。すなわち、これらの技術を実際に適用する上では、扱うデータの性質及び応用ごとに、「どのプライバシー保護基準に基づいて、どの手法によりプライバシーを保護するべきか」を適切に判断することが求められるが、この判断を全てのデータ活用において行うことは現実的には難しい。
【０００３】
そこで、差分プライバシー基準（differential privacy）が注目されている（特許文献１、特許文献２、非特許文献１〜３参照）。この差分プライバシー基準は、「加工データを作成する上での元データとなるデータベースに、ある人が含まれるか否かの、加工データからの判別困難性」を安全性の根拠とするプライバシー保護基準である。差分プライバシー基準は、他の多くのプライバシー保護基準とは異なり、任意の背景知識を持つ攻撃者及び未知の攻撃に対して数学的な安全性が与えられているという優れた性質を有する。差分プライバシー基準を満たす手段は「メカニズム（mechanism）」と呼ばれる。代表的な差分プライバシーのメカニズムとしてラプラス（Laplace）メカニズムが挙げられる。ラプラスメカニズムは「問い合わせ結果に対してラプラスノイズを加える」という簡単な手段によって実現することができる。
【０００４】
ラプラスメカニズムは、差分プライバシー基準を満たす集計データを簡単かつ高速に作成することができる。しかし、集計する前の元データ、すなわち個票データを、差分プライバシー基準を満たすように匿名化する用途に直接用いることはできない。個票データを、差分プライバシー基準を満たすように匿名化するための手段として、ＰＲＡＭ(Post Randomization)に基づく手法、すなわち個票データに含まれる各レコードの値を、予め定められた確率で別の値に変化させる手法がある。ＰＲＡＭに基づき差分プライバシー基準を満たす手法においては、この手法の適用により得られる差分プライバシーの強度(安全性)は、値を変化させる確率によって変化する。（非特許文献４参照）
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２−１３３３２０号公報
【特許文献２】特開２０１６−０１２０７４号公報
【非特許文献】
【０００６】
【非特許文献１】Cynthia Dwork. Differential Privacy. In Michele Bugliesi, BartPreneel, Vladimiro Sassone, and Ingo Wegener, editors, Proc. 33rd intl.conf.Autom ata, Languages and Programming - Volume Part II, Vol.4052 of LectureNotesin Com puter Science, pp.1-12. Springer, 2006.
【非特許文献２】Cynthia Dwork. Differential privacy: a survey of results. In Proc.5th intl. conf. Theory and applications of models of computation, pp.1-19.Springer-Verlag,April 2008.
【非特許文献３】寺田 雅之、外３名、大規模集計データへの差分プライバシの適用、情報処理学会論文誌、第56巻9号、pp. 1801-1816、2015年9月．
【非特許文献４】Dai Ikarashi et al., k-anonymous microdata release via postrandomisation method, eprint arXiv, Vol. 1504.05353, pp. 1-22, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、ＰＲＡＭに基づく手法で、十分な安全性を持つ匿名化個票データを生成しようとすると、著しく高い確率でレコードの値を変化させる必要がある。そのため、十分な安全性を持たせるためにはデータの有用性が大きく損なわれることになる。
【０００８】
本発明は、上記問題点に鑑みてなされたものであり、差分プライバシー基準を満たすと共に有用性の高い個票データを提供可能なプライバシー保護装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一態様に係るプライバシー保護装置は、複数のレコードを含む第１の個票データの入力を受け、第２の個票データを出力するプライバシー保護装置であって、第１の個票データの入力を受け付ける入力手段と、入力手段によって受け付けられた第１の個票データを集計することにより第１の集計データを生成する集計手段と、第１の集計データに対して予め定められた強度の乱数を付与することにより第２の集計データを生成する乱数付与手段と、第２の集計データから、各要素が負の値ではない整数であり、且つ、全ての要素の総和が第２の集計データの全ての要素の総和と等しい、第３の集計データを生成する精緻化手段と、第３の集計データから第２の個票データを生成する個票生成手段と、第２の個票データを出力する出力手段と、を備える。
【００１０】
このプライバシー保護装置では、第１の集計データに対して乱数が付与されて第２の集計データが生成される。このように、例えばＰＲＡＭ等により個票データのレコードの値が直接変更されるのではなく集計データに対して乱数が付与されることにより、データの有用性を大きく損なうことなく、差分プライバシー基準を満たす集計データを生成することができる。ここで、乱数が付与された第２の集計データには、負の値や少数の要素が含まれ得る。当該要素が含まれていることにより、乱数付与後の集計データから個票データを生成することができない場合がある。この点、各要素が負の値ではない整数であり且つ要素の総和が第２の集計データの全ての要素の総和と等しい第３の集計データが生成されることにより、該第３の集計データに対応する第２の個票データを生成することが可能となる。第２の個票データは、第２の集計データから生成された第３の集計データに基づくものであるので、第２の集計データと同様、差分プライバシー基準を満たし、有用性も高い。以上より、本発明によれば、差分プライバシー基準を満たすと共に有用性の高い個票データを提供することができる。
【００１１】
上記プライバシー保護装置において、精緻化手段は、第２の集計データの要素に関する最近傍探索を行うことにより第３の集計データを生成してもよい。これにより、第２の個票データを、第１の個票データと似たレコード構成とすることができる。このことで、第２の個票データの有用性を向上させることができる。
【発明の効果】
【００１２】
本発明によれば、差分プライバシー基準を満たすと共に有用性の高い個票データを提供することができる。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態に係るプライバシー保護装置の構成を概略的に示す図である。
【図２】図１のプライバシー保護装置のハードウェア構成図である。
【図３】図１のプライバシー保護装置によって実行されるプライバシー保護方法の一連の処理を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。図面の説明において、同一又は同等の要素には同一符号を用い、重複する説明を省略する。
【００１５】
［第１実施形態］
図１は、第１実施形態に係るプライバシー保護装置の構成を概略的に示す図である。図１に示されるように、プライバシー保護装置１０は、複数のレコードを含む第１の個票データDを入力し、第２の個票データD+を出力する装置であり、例えば、サーバ装置等の情報処理装置によって構成されている。プライバシー保護装置１０は、個票データを公開するにあたって、データベースに含まれる人々のプライバシーに関する情報（個人情報）の漏洩を防止するためのプライバシー保護処理を第１の個票データDに施す。例えば、プライバシー保護装置１０は、商店における売上履歴やGPSによる位置情報などの提供及び開示におけるプライバシーを保護する。
【００１６】
第１の個票データDは、プライバシー保護装置１０によるプライバシー保護処理の処理対象である。第１の個票データDは、それぞれが個人に対応づけられた１つ以上のレコードから構成されたデータベースであり、各レコードは１つ以上の属性値を持つ。すなわち、各レコードを元とした多重集合(multiset)として表現される。
【００１７】
以下、詳細に説明する。ある個人iに対応づけられたレコードをx_iとする。x_iは、その個人に関する何らかの情報を表す、d個の属性値x_{ij}の組(順序対)から構成される。任意のレコードにおける、j番目の属性値は集合A_jに属する。ここで、A_jを属性と呼び、全ての属性の直積A=A_1×A_2×…×A_dを属性空間と呼ぶ。
【００１８】
このとき、n個のレコードから構成される個票データDは、属性空間Aを台集合(underlyingset)とする、以下のn元の多重集合として表される。なお、{{・}}は多重集合、(・)は順序対、{}は集合をそれぞれ表す記号とする。D、x_i、及びAは、下記の（１）〜（３）式により示される。
D   = {{ x_1, x_2, ..., x_n }}・・・（１）
x_i  = (x_{i1}, x_{i2},... , x_{id} )・・・（２）
A   = A_1 × A_2 × … × A_d・・・（３）
【００１９】
ここで、個票データDを(集合もしくは順序対ではなく)多重集合として表現する理由は、個票データには同一の属性値の組み合わせを持つレコードが複数存在しうること、及びレコードの並び順のみが異なる個票データは同値とみなすべきことによる。
【００２０】
プライバシー保護装置１０は、機能的には、入力部１１(入力手段)と、集計部１２(集計手段)と、乱数付与部１３(乱数付与手段)と、精緻化部１４(精緻化手段)と、個票生成部１５(個票生成手段)と、出力部１６(出力手段)と、を備える。プライバシー保護装置１０は、図２に示されるハードウェアによって構成される。
【００２１】
図２は、プライバシー保護装置１０のハードウェア構成図である。図２に示されるように、プライバシー保護装置１０は、物理的には、１又は複数のＣＰＵ（Central Processi ng Unit）１０１、主記憶装置であるＲＡＭ（RandomAccessMemory）１０２及びＲＯＭ（Read Only Memory)１０３、データ送受信デバイスである通信モジュール１０４、ハードディスク装置等の補助記憶装置１０５、キーボード等のユーザの入力を受け付ける入力装置１０６、並びに、ディスプレイ等の出力装置１０７等のハードウェアを備えるコンピュータとして構成される。図１におけるプライバシー保護装置１０の各機能は、ＣＰＵ１０１、ＲＡＭ１０２等のハードウェア上に１又は複数の所定のコンピュータソフトウェアを読み込ませることにより、ＣＰＵ１０１の制御のもとで通信モジュール１０４、入力装置１０６及び出力装置１０７を動作させるとともに、ＲＡＭ１０２及び補助記憶装置１０５におけるデータの読み出し及び書き込みを行うことで実現される。
【００２２】
図１に戻って、プライバシー保護装置１０の機能構成について詳細に説明する。入力部１１は、第１の個票データDの入力を受け付ける入力手段として機能する。入力部１１は、プライバシー保護装置１０の外部から第１の個票データDを受信し、受信した第１の個票データDを集計部１２に出力する。
【００２３】
集計部１２は、入力部１１によって受け付けられた第１の個票データDを集計することによって第１の集計データVを生成する集計手段として機能する。第１の集計データVは、第１の個票データDにおいて、ある定められた条件を満たす属性値(もしくは属性値の組み合わせ)を持つレコードの個数を数えあげた値の集合である。
【００２４】
AをDの属性空間とするとき、Aの部分空間C_kに属するレコードの個数をCount(D, C_k)=とする。これを計数問い合わせ(count query)結果と呼ぶ。このとき、任意のC_kからなる順序対である集計条件C=(C_1, C_2, ...,C_p)に対して、第1の集計データVは、Cの各元に対応する計数問い合わせ結果Count(D, C_k)からなる順序対として以下の（４）式により示される。
V(D, C) = (v_1,v_2, ..., v_p), v_k = Count(D, C_k)・・・（４）
【００２５】
第１の集計データVの作成において、一般的には各属性の値域A_jの互いに素な部分集合の直積が集計条件Cとして用いられる。このとき、集計データは分割表(contingency table)と呼ばれる。分割表におけるそれぞれの値v_jを、セル(cell)もしくはセル値と呼ぶ。
【００２６】
さらに、A={a_1,a_2, ..., a_p}を属性空間とする第１の集計データVにおいて、c_i={a_i}、すなわち集計条件の各要素c_iは、属性空間のいずれかの元のみを含む集合であり、重複なく全ての元に対応づけられる(一対一の対応関係を持つ)とする。この第１の集計データVは分割表であり、これ以上に集計条件を細かくした分割表は作れないことから、以下ではこれを完全分割表と呼ぶ。完全分割表のセル数|V|は、Aの濃度|A|と等しい。
【００２７】
このとき、完全分割表Vにおける各要素v_iは，多重集合である第１の個票データDにおける、その台集合である属性空間Aの元a_iの多重度(multiplicity) m_D(a_i)に他ならない。任意の多重集合は、台集合と、その各元の多重度により一意に定義されるため、(V, A)の組が与えられればDは一意に定まる。このことから、以下の定理が成立する。
【００２８】
(定理１)属性空間Aを持つ第１の個票データDから第１の集計データである完全分割表Vを生成する写像をf_Aとする(V = f_A(D))。このとき、f_Aは、D = f^{-1}_A(V)となる逆写像f^{-1}_Aを持つ。
【００２９】
集計部１２が生成する第１の集計データVは、第１の個票データから生成される任意の分割表であるが、上記の定理から特に完全分割表であることが望ましい。
【００３０】
乱数付与部１３は、第１の集計データVに対して予め定められた強度の乱数を付与することによって、第２の集計データV*を生成する乱数付与手段として機能する。ここで、第２の集計データV*は差分プライバシー基準を満たす。また、乱数は、加算により差分プライバシー基準を満たすことができる乱数である。このような乱数として、例えば、ラプラス分布に従う乱数であるラプラスノイズ（ラプラス乱数）、幾何分布に従う乱数である幾何ノイズ（幾何乱数）等が用いられる。ラプラスノイズを付与することにより差分プライバシー基準を満たす手段はラプラスメカニズムと呼ばれ、幾何ノイズを付与することにより差分プライバシー基準を満たす手段は幾何メカニズムと呼ばれる。
【００３１】
乱数としてラプラスノイズを用いて説明を行う。ここで、ラプラスノイズとは、確率分布の一種であるラプラス分布から独立に抽出された乱数である。平均０、スケールλのラプラス分布に従って発生させたラプラスノイズをＬａｐ（λ）とする。具体的には、第１の集計データVに含まれる全ての要素に対して、それぞれ独立に生成されたＬａｐ（1/ε）を加算することによって第２の集計データV*を生成することにより、第２の集計データV*はε-差分プライバシーという安全性強度を満たすことが保証される。
【００３２】
乱数として幾何ノイズを用いる場合は、上記のラプラスノイズを幾何ノイズに置きかえればよい。この場合も、用いる幾何ノイズのスケールに応じた安全性強度を持つ、差分プライバシーを満たした第２の集計データV*を得ることができる。
【００３３】
このように、ラプラス分布に従う乱数であるラプラスノイズ（ラプラス乱数）、幾何分布に従う乱数である幾何ノイズ（幾何乱数）を用いることにより、第２の集計データV*が差分プライバシー基準を満たすことが保証される。
【００３４】
精緻化部１４は、第２の集計データV*から、各要素が負の値ではない整数であり、且つ、全ての要素が第２の集計データV*の全ての要素の総和と等しい、第３の集計データV+を生成する精緻化手段として機能する。すなわち、精緻化部１４は、第２の集計データV*から、各要素が負の値でなく、各要素が整数であり、且つ、全ての要素の総和が第２の集計データV*に含まれる全ての要素の総和と等しいという制約条件を全て満たす、第３の集計データV+を生成する。
【００３５】
第３の集計データV+を生成するための方法は、V+が上記の制約条件を全て満たすようなものであれば任意である。簡単には、たとえば、V* に含まれる負の値を持つ要素を全て０にするとともに、小数以下を切り捨て、総計が合うように均等にV*の要素に対して定数を加算もしくは減算することにより、上記の制約条件を全て満たす、第３の集計データV+を生成することができる。ただし、精緻化部１４において第３の集計データV+を生成するための方法はこの方法に限られない。
【００３６】
個票生成部１５は、第３の集計データV+から、予め定められた手順により第２の個票データD+を生成する個票生成手段として機能する。上述の通り、第３の集計データV+が完全分割表であれば、V+の各要素は第１の個票データDの台集合Aにおいて対応する要素の多重度を表現する。たとえば、あるV+の要素v_iについて、v_iはAの要素a_i = (男性、３０代)に対応しており、さらにv_i = ３であったとする。このとき、第２の個票データD+は、(男性、３０代)というレコードを３個含むことを意味する。
【００３７】
出力部１６は、個票生成部１５によって生成された第２の個票データD+を出力する出力手段として機能する。出力部１６は、個票生成部１５から第２の個票データD+を受信し、受信した第２の個票データD+をプライバシー保護装置１０の外部に出力する。出力部１６は、たとえば、第２の個票データD+を公開用のデータベースに出力し、プライバシーが保護された個票データを備えるデータベースを作成する。
【００３８】
次に、上述したプライバシー保護装置１０によって実行されるプライバシー保護方法の処理について、図３を参照して説明する。図３は、図１のプライバシー保護装置１０によって実行されるプライバシー保護方法の一連の処理を示すフローチャートである。
【００３９】
図３に示されるように、まず、入力部１１によって第１の個票データDの入力が受け付けられる（ステップＳ１）。そして、入力部１１によって集計部１２に第１の個票データDが出力され、集計部１２によって、第１の個票データDが集計されて第１の集計データVが生成される（ステップＳ２）。
【００４０】
つづいて、乱数付与部１３によって、第１の集計データVに対して予め定められた強度の乱数が付与され、第２の集計データV*が生成される（ステップＳ３）。そして、精緻化部１４により、第２の集計データV*から、各要素が負の値ではない整数であり、且つ、全ての要素が第２の集計データV*の全ての要素の総和と等しい、第３の集計データV+が生成される（ステップＳ４）。
【００４１】
つづいて、個票生成部１５により、第３の集計データV+から、予め定められた手順により第２の個票データD+が生成される（ステップＳ５）。最後に、出力部１６により、個票生成部１５によって生成された第２の個票データD+が外部に出力される（ステップＳ６）。以上が、プライバシー保護装置１０によって実行されるプライバシー保護方法の処理である。
【００４２】
次に、プライバシー保護装置１０の作用効果について説明する。
【００４３】
上述したように、プライバシー保護装置１０は、複数のレコードを含む第１の個票データDの入力を受け、第２の個票データD+を出力するプライバシー保護装置であって、第１の個票データDの入力を受け付ける入力部１１と、入力部１１によって受け付けられた第１の個票データDを集計することにより第１の集計データVを生成する集計部１２と、第１の集計データVに対して予め定められた強度の乱数を付与することにより第２の集計データV*を生成する乱数付与部１３と、第２の集計データV*から、各要素が負の値ではない整数であり、且つ、全ての要素の総和が第２の集計データV*の全ての要素の総和と等しい、第３の集計データV+を生成する精緻化部１４と、第３の集計データV+から第２の個票データD+を生成する個票生成部１５と、第２の個票データD+を出力する出力部１６と、を備える。
【００４４】
このプライバシー保護装置１０では、第１の集計データVに対して乱数が付与されて第２の集計データV*が生成される。このように、例えばＰＲＡＭ等により個票データのレコードの値が直接変更されるのではなく集計データに対して乱数が付与されることにより、データの有用性を大きく損なうことなく、差分プライバシー基準を満たす集計データを生成することができる。ここで、乱数が付与された第２の集計データV*には、負の値や少数の要素が含まれ得る。当該要素が含まれていることにより、乱数付与後の集計データから個票データを生成することができない場合がある。この点、各要素が負の値ではない整数であり且つ要素の総和が第２の集計データV*の全ての要素の総和と等しい第３の集計データV+が生成されることにより、該第３の集計データV+に対応する第２の個票データD+を生成することが可能となる。第２の個票データD+は、第２の集計データV*から生成された第３の集計データV+に基づくものであるので、第２の集計データV*と同様、差分プライバシー基準を満たし、有用性も高い。以上より、本発明によれば、差分プライバシー基準を満たすと共に有用性の高い個票データを提供することができる。
【００４５】
［第２実施形態］
次に、本発明の第２実施形態に係るプライバシー保護装置１０について説明する。第１実施形態において説明したように、プライバシー保護装置１０では、精緻化部１４が、第２の集計データV*から、各要素が負の値でなく、各要素が整数であり、且つ、全ての要素の総和が第２の集計データV*に含まれる全ての要素の総和と等しいという制約条件を全て満たす、第３の集計データV+を生成している。ここで、個票生成部１５において、第１の個票データDの性質をより良く保持する、有用性が高い第２の個票データD+を得るためには、第２の集計データV*と第３の集計データV+とが互いに近い値をとることが望ましい。
【００４６】
そこで、第２実施形態に係るプライバシー保護装置１０では、精緻化部１４が、第２の集計データV*から、第３の集計データV+を、制約条件を満たすデータからの最近傍探索により生成する精緻化手段として機能する。その他の構成については、第１実施形態と同様である。
【００４７】
すなわち、第２実施形態における精緻化部１４は、第２の集計データV*の要素に関する最近傍探索を行うことにより第３の集計データV+を生成する。精緻化部１４における最近傍探索は、第２の集計データV*をn次元のベクトル空間上の点とみなしたとき、上記の制約条件を満たすn-1次元の超平面Z上の非負整数格子点のうち、V*と最も近い点を探索することに相当する。この超平面Zは、第１の集計データVを含み、Zの任意の点において、その原点からの１次ノルムは、Vの原点からの１次ノルムと等しい。
【００４８】
この探索は、単純には、上述した制約条件を満たす格子点を全て数え上げ、第２の集計データV*との間で最も短い距離を持つデータを選択することにより得ることができる。この距離の定義は様々なものが考えられる。たとえばL1ノルム、L2ノルム(ユークリッド距離)などの各種のノルムや、KS-距離などの標本間の統計量に基づく距離などを用いることが考えられるが、これらに限定されるものではない。
【００４９】
また、上述した制約条件を満たすデータを全て数え上げることが計算量的に困難な場合は、効率的に最近傍探索を行うためのデータ構造を用いて、最近傍探索を実施することも望ましい。このようなデータ構造としては、たとえばkd木などを例として挙げることができるが、これに限定されるものではない。
【００５０】
このようなプライバシー保護装置１０によれば、第２の個票データD+を、第１の個票データDと似たレコード構成とすることができる。このことで、第２の個票データD+の有用性を向上させることができる。
【符号の説明】
【００５１】
１０…プライバシー保護装置、１１…入力部（入力手段）、１２…集計部（集計手段）、１３…乱数付与部（乱数付与手段）、１４…精緻化部（精緻化手段）、１５…個票生成部（個票生成手段）、１６…出力部（出力手段）、D…第１の個票データ、D+…第２の個票データ、V…第１の集計データ、V*…第２の集計データ、V+…第３の集計データ。
【図１】
0006711689.tif 000002
【図２】
0006711689.tif 000003
【図３】
0006711689.tif 000004