JP6973636B2 - 安全性評価装置、安全性評価方法、およびプログラム - Google Patents

Description

この発明は、データベースに対して決定的手法もしくは確率的手法により個別データを秘匿したデータベースの安全性を評価する技術に関する。

データベース（以下、「元データベース」と呼ぶ）に対して決定的手法により個別データを秘匿する技術として、k-匿名法（非特許文献１および２参照）がある。また、確率的手法により秘匿する技術として、Pk-匿名法（非特許文献３および４参照）がある。これらの秘匿処理を施したデータベース（以下、「秘匿データベース」と呼ぶ）の安全性を評価するために、レコードリンケージと呼ばれる手法（非特許文５および６参照）が用いられる。レコードリンケージとは、あるレコードを再特定しようとすることで、どれだけそのレコードが秘匿できているかを測定する方法である。従来技術では、再特定を試みる秘匿データベースの対象レコードと元データベースの全レコードとの距離を計算し、最近傍レコードと対象レコードとが一致したら再特定できたとして、最近傍レコード数の逆数を対象レコードの再識別率とする。これを秘匿データベースの全レコードについて実施し、各レコードの再識別率を合計した値をデータベースの再識別率として評価する。

Kristen LeFevre, David J DeWitt, and Raghu Ramakrishnan, "Incognito: Efficient full-domain k-anonymity", Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 49-60, 2005. Florian Kohlmayer, Fabian Prasser, Claudia Eckert, Alfons Kemper, and Klaus A Kuhn, "Flash: efficient, stable and optimal k-anonymity", Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Conference on Social Computing (SocialCom), pp. 708-717, 2012. 五十嵐大，千田浩司，高橋克巳，"数値属性における, k-匿名性を満たすランダム化手法"，コンピュータセキュリティシンポジウム2011，pp. 450-455，2011年 五十嵐大，千田浩司，高橋克巳，"k-匿名性の確率的指標への拡張とその適用例"，コンピュータセキュリティシンポジウム2009，pp. 1-6，2009年 Vicenc Torra, John M Abowd, and Josep Domingo-Ferrer, "Using mahalanobis distance-based record linkage for disclosure risk assessment", International Conference on Privacy in Statistical Databases, pp. 233-242, 2006. Josep Domingo-Ferrer and Vicenc Torra, "Distance-based and probabilistic record linkage for re-identification of records with categorical variables", Butlleti de IACIA, Associacio Catalana dIntelligencia Artificial, pp. 243-250, 2002.

近年ビッグデータの利活用が注目されており、匿名化の対象となるデータも大規模データとなることが想定される。従来技術では、レコードリンケージの際に、レコード数が増えるに連れて処理時間が増えることが問題であった。より具体的には、レコード数の線形な増加に伴い、処理時間が２乗で増えてしまう。したがって、大規模なデータに対し、実用的な処理時間でレコードリンケージを行うことが課題であった。

この発明は、上記のような技術的課題に鑑みて、大規模なデータを秘匿したデータベースの安全性を効率的に評価することを目的とする。

上記の課題を解決するために、この発明の一態様の安全性評価装置は、複数のレコードからなる元データベースと元データベースを秘匿した秘匿データベースとを記憶するデータベース記憶部と、秘匿データベースの各レコードについて、元データベースに対する近傍探索により所定の近傍数の近傍レコード集合を取得する近傍レコード探索部と、秘匿データベースの各レコードについて近傍レコード集合の各レコードとの距離を計算し、当該レコードとの距離に基づいて最近傍レコードを取得する最近傍レコード計算部と、秘匿データベースの各レコードについて、当該レコードに対応する元データベースのレコードが最近傍レコードと一致するか否かに基づいて当該レコードの再識別率を計算する再特定判定部と、秘匿データベースの各レコードについて計算した再識別率に基づいて秘匿データベースの再識別率を計算する再識別率計算部と、を含む。

この発明によれば、レコードリンケージを行う際に、従来技術ではO(N²)の計算量を要する処理が、近傍数をlog Nとした場合にはO(N log N)の計算量となる。そのため、大規模なデータに対し、実用的な処理時間でレコードリンケージを行うことができる。したがって、大規模なデータを秘匿したデータベースの安全性を効率的に評価することができる。

図１は、本発明で対象とするデータベースの定義を説明するための図である。 図２は、従来のレコードリンケージを説明するための概念図である。 図３は、本発明のレコードリンケージを説明するための概念図である。 図４は、実施形態の安全性評価装置の機能構成を例示する図である。 図５は、実施形態の安全性評価方法の処理手続きを例示する図である。

以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

［記号］
ある属性の集合を大文字Xと表現し、属性Xの値を小文字x∈Xと表現する。

データベースの１レコードを横ベクトルとして表現する。例えば、M属性あるデータベースのi番目のレコードは、x^→ _i={x_i1, …, x_ij, …, x_iM}とする。

複数のレコードからなる集合をデータベースX^→とする。例えば、レコード数Nのデータベースは、X^→={x^→ ₁, …, x^→ _N}とする。

データベースX^→の各レコードを決定的手法もしくは確率的手法により秘匿したレコードからなる集合を秘匿データベースY^→とする。例えば、レコード数Nの秘匿データベースは、Y^→={y^→ ₁, …, y^→ _N}とする。

秘匿データベースY^→はレコードの順番がシャッフルされている場合もある。そこで、秘匿データベースY^→の行番号と元データベースX^→の行番号（以下、「真の行番号」と呼ぶこともある）とを対応付ける行番号対応関数f_y:R→Rを定義する。

図１に、元データベースX^→、秘匿データベースY^→、および行番号対応関数f_yの例を示す。元データベースX^→は、M属性からなる平文のレコードをNレコード含むデータベースである。秘匿データベースY^→は、元データベースの各レコードが秘匿され、かつ、順番がシャフルされたデータベースである。行番号対応関数f_yは、元データベースの行番号と秘匿データベースの行番号との対応が表された参照表である。

［処理の概要］
本発明の安全性評価技術では、元データベースX^→と秘匿データベースY^→と行番号対応関数f_yとを用いて、データベース全体の再識別率を計算し、安全性の評価を行う。本発明では、あるレコードの再識別率を計算するにあたり、大まかに以下の２つの処理を行う。

処理１．近傍探索の対象となるレコードの近傍レコードを、指定した近傍数分取得する。近傍レコードの探索は、木構造を用いたもの（参考文献１参照）や、ハッシングを用いたもの（参考文献２参照）があり、それらを用いて近傍レコードを取得する。木構造としては、例えばkd木等が挙げられる。

〔参考文献１〕Jon Louis Bentley, "Multidimensional binary search trees used for associative searching", Communications of the ACM, Vol. 18, No. 9, pp. 509-517, 1975.
〔参考文献２〕Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni, "Locality-sensitive hashing scheme based on p-stable distributions", In Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262, 2004.

処理２．近傍レコードに基づくレコードリンケージの対象レコードと近傍レコードとの距離を計算し、最も距離が近い近傍レコードの行番号とレコードリンケージの対象レコードの真の行番号とが一致したら再特定できたとする。計算する距離としては、例えば、ユークリッド距離、ハミング距離、マンハッタン距離等、適切な距離を用いることができる。レコードの属性値が重複している場合、近傍探索で指定した近傍数以上の近傍レコードが取得される。その場合には、近傍レコード中の重複レコードを排除した上で、近傍レコードとの距離を計算する。

上記処理１，２を秘匿データベースの各レコードについて行い、各レコードの再識別率の合計値をデータベースの再識別率とし、秘匿データベース全体の安全性を評価する。

図２は、従来技術によるレコードリンケージを表す概念図であり、図３は、本発明によるレコードリンケージを表す概念図である。従来技術は秘匿データベースのあるレコードについて元データベースの全レコードとの距離を計算し、最も近いレコードの行番号がそのレコードの真の行番号と一致した場合に、再特定できたものと判定する。一方、本発明は秘匿データベースのあるレコードについて元データベースから近傍探索により取得した所定の近傍数の近傍レコードとの距離を計算し、最も近いレコードの行番号がそのレコードの真の行番号と一致した場合に、再特定できたものと判定する。

本発明では、木構造を用いた近傍探索もしくはハッシングを用いた近傍探索のどちらかを用いることとする。本発明の具体的な処理を<Algorithm 1>に示す。上記の処理１（近傍探索）は２〜７行目に対応し、処理２（近傍レコードに基づくレコードリンケージ）は８〜22行目に対応する。なお、|・|は集合・の要素数を表す。

<Algorithm 1>近傍探索を用いたレコードリンケージ
Input: レコード数Nの元データベースX^→={x^→ ₁, …, x^→ _N}, レコード数Nの秘匿データベースY^→={y^→ ₁, …, y^→ _N}, 行番号対応関数f_y:R→R, 近傍数K（1<K<N）, 許容範囲ε（ε>1）
Output: 再識別率r
1: r←0
2: for i=1 to N do
3: y^→ _iに対する元データベースX^→の近傍レコード集合X^→ _i ^near={x^→ _j}（ただし、|X^→ _i ^near|≧K）を近傍探索により取得する
4: end for
5: if |X^→ _i ^near|>εKとなるiが存在する場合 then
6: |X^→ _i ^near|>εKとなるiに対して、X^→ _i ^nearのうち重複を除いたレコード集合X^→ _i ^uniq={x^→ _j}とし、各x^→ _jに対応する重複レコードの行番号集合を返す関数fⁱ _dupを保持する
7: end if
8: for i=1 to N do
9: if |X^→ _i ^near|>εKとなる場合 then
10: y^→ _iとX^→ _i ^uniqの各レコードとの距離を求め、y^→ _iに最も距離の近いレコードを最近傍レコードZ^→とする
11: if Z^→にf_y(k)=i（ただしk:x^→ _k∈Z^→）となるレコードが存在する場合 then
12: for x^→ _j∈Z^→ do
13: r←r+1/(|fⁱ _dup(j)||Z^→|)
14: end for
15: end if
16: else
17: y^→ _iとX^→ _i ^nearの各レコードとの距離を求め、y^→ _iに最も距離の近いレコードを最近傍レコードZ^→とする
18: if Z^→にf_y(k)=i（ただしk:x^→ _k∈Z^→）となるレコードが存在する場合 then
19: r←r+1/|Z^→|
20: end if
21: end if
22: end for

まず、秘匿データベースY^→のレコードy^→ _iごとに近傍探索を用いて近傍レコード集合X^→ _i ^nearを取得する（２〜４行目に対応）。元データベースX^→中に重複したレコードが少なければ、取得した近傍レコード集合X^→ _i ^nearが指定した近傍数K以下となる。しかしながら、元データベースX^→中に重複するレコードが多い場合、取得した近傍レコード集合X^→ _i ^nearが指定した近傍数Kを超えることがあり、近傍探索した効果がなくなってしまう。そこで、近傍レコード集合X^→ _i ^nearがεK件を超えた場合は、近傍レコード集合X^→ _i ^near中の重複するレコードを排除したレコード集合X^→ _i ^uniqを生成し、重複するレコードの行番号を返す関数fⁱ _dupを保持する（５〜７行目に対応）。なお、許容範囲εと近傍数Kは、例えば、ε=2.0, K=log Nなどに設定するとよい。

次に、秘匿データベースY^→のレコードy^→ _iごとに近傍レコード集合の各レコードとの距離を計算し、最も距離が近いレコードの真の行番号（すなわち、元データベース上の行番号）が現在のレコードの真の行番号（すなわち、現在のレコードの秘匿データベース上の行番号に対応付けられた元データベース上の行番号）と一致した場合、再識別成功として再識別率rを加算する。

より具体的には、近傍レコード集合X^→ _i ^nearのレコード数がεK件を超えていた場合は、まず重複を排除した近傍レコード集合X^→ _i ^uniqの各レコードとの距離計算を行う。そして、最も距離が近いレコードの重複するレコードの真の行番号を探索し、現在のレコードの行番号と一致した場合、重複レコード間で平均して再識別できたとして、1/重複レコード数（1/|fⁱ _dup|）を再識別率として加算する。その際、最近傍レコードが複数ある場合は、それらも平均して（1/|Z^→|）再識別できたとして加算する（９〜15行目に対応）。

もし近傍レコード集合X^→ _i ^nearのレコード数がεK件以下であった場合は、まず近傍レコード集合X^→ _i ^nearの各レコードとの距離計算を行う。そして、最も距離が近いレコードの重複するレコードの真の行番号を探索し、現在のレコードの行番号と一致した場合、１を再識別率として加算する。その際、最近傍レコードが複数ある場合は、それらを平均して（1/|Z^→|）再識別できたとして加算する（16〜21行目に対応）。

［実施形態］
実施形態の安全性評価装置および方法は、上記<Algorithm 1>を実行して秘匿データベースの安全性を評価する。実施形態の安全性評価装置１は、図４に例示するように、データベース記憶部１０、近傍レコード探索部１１、重複排除部１２、最近傍レコード計算部１３、再特定判定部１４、および再識別率計算部１５を備える。この安全性評価装置１が、図５に例示する各ステップの処理を行うことにより実施形態の安全性評価方法が実現される。

安全性評価装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。安全性評価装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。安全性評価装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。安全性評価装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。安全性評価装置１が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。

以下、図５を参照して、実施形態の安全性評価装置１が実行する安全性評価方法について説明する。

データベース記憶部１０には、平文のレコードx^→ _i（i=1, …, N、N≧2）からなる元データベースX^→={x^→ ₁, …, x^→ _N}と、元データベースX^→を秘匿した秘匿データベースY^→={y^→ ₁, …, y^→ _N}と、元データベースX^→の行番号と秘匿データベースY^→の行番号とを対応付ける行番号対応関数f_yが記憶されている。

ステップＳ１１において、近傍レコード探索部１１は、秘匿データベースY^→の各レコードy^→ _iについて、元データベースX^→に対する近傍探索により所定の近傍数Kの近傍レコード集合X^→ _i ^near={x^→ _j}（j∈{1, …, N}）を取得する。このとき、近傍数Kは、例えば、元データベースX^→のレコード件数Nの対数log Nとする。近傍探索は、木構造もしくはハッシングを用いた近傍探索のどちらかを用い、例えば、kd木を用いる手法を用いる。近傍レコード探索部１１は、取得した近傍レコード集合X^→ _i ^nearを重複排除部１２へ出力する。

ステップＳ１２において、重複排除部１２は、近傍レコード集合X^→ _i ^nearのレコード数が所定の閾値εKよりも多い場合に、近傍レコード集合X^→ _i ^near中の重複レコードを排除して、重複排除済み近傍レコード集合X^→ _i ^uniqを生成する。このとき、閾値εKは、例えば、近傍数の２倍（すなわち、許容範囲ε=2.0）とする。重複排除部１２は、重複排除済み近傍レコード集合X^→ _i ^uniqを最近傍レコード計算部１３へ出力する。近傍レコード集合X^→ _i ^nearのレコード数が閾値εK以下だった場合は、近傍レコード集合X^→ _i ^nearを最近傍レコード計算部１３へ出力する。

ステップＳ１３において、最近傍レコード計算部１３は、秘匿データベースY^→の各レコードy^→ _iについて、近傍レコード集合X^→ _i ^nearのレコード数が閾値εKよりも多かった場合には、重複排除済み近傍レコード集合X^→ _i ^uniqの各レコードとの距離を計算し、近傍レコード集合X^→ _i ^nearのレコード数が閾値εK以下だった場合には、近傍レコード集合X^→ _i ^nearの各レコードとの距離を計算し、当該レコードy^→ _iとの距離が最も近い最近傍レコードZ^→={x^→ _k}（k∈{1, …, N}）を取得する。最近傍レコード計算部１３は、取得した最近傍レコードZ^→を再特定判定部１４へ出力する。

ステップＳ１４において、再特定判定部１４は、秘匿データベースY^→の各レコードy^→ _iについて、当該レコードy^→ _iに対応付けられた元データベースX^→のレコードx^→ _jが最近傍レコードZ^→中に存在するか否かに基づいて当該レコードy^→ _iの再識別率r_iを計算する。レコードy^→ _iに対応付けられたレコードx^→ _jは行番号対応関数f_yを用いて求めることができる。再特定判定部１４は、計算したレコードy^→ _iの再識別率r_iを再識別率計算部１５へ出力する。

ステップＳ１５において、再識別率計算部１５は、秘匿データベースY^→の各レコードy^→ _iについて計算した再識別率r_iに基づいて秘匿データベースY^→の再識別率rを計算する。例えば、秘匿データベースY^→の各レコードy^→ _iの再識別率r_iの総和Σ_i=1 ^Nr_iを秘匿データベースY^→の再識別率rとする。再識別率計算部１５は、秘匿データベースY^→の再識別率rを安全性評価装置１の出力とする。

本形態のポイントは、レコードリンケージに対して近傍探索を単に組み合わせただけでは解決できない課題、すなわち、近傍レコードが大量に出現した場合の問題を解決したことである。具体的には、大量の近傍レコードに対して重複排除処理を加えることで、処理時間を抑えたことである。近傍レコードを取得する際に属性値が重複等している場合、指定した近傍数以上の近傍レコードを取得するため、そのまま処理を行うと実行時間が長くなる。最悪の場合、近傍レコードがデータベース中のレコード数分出力されてしまい、結果として近傍レコードを探索した効果がなくなってしまう。本形態では、近傍レコードを取得する際に重複排除の処理を加えていることから、上記問題を回避でき、高速な実行が可能となっている。

以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (6)

1. 複数のレコードからなる元データベースと上記元データベースを秘匿した秘匿データベースとを記憶するデータベース記憶部と、
   上記秘匿データベースの各レコードについて、上記元データベースに対する近傍探索により所定の近傍数の近傍レコード集合を取得する近傍レコード探索部と、
   上記秘匿データベースの各レコードについて上記近傍レコード集合の各レコードとの距離を計算し、当該レコードとの距離に基づいて最近傍レコードを取得する最近傍レコード計算部と、
   上記秘匿データベースの各レコードについて、当該レコードに対応する上記元データベースのレコードが上記最近傍レコードと一致するか否かに基づいて当該レコードの再識別率を計算する再特定判定部と、
   上記秘匿データベースの各レコードについて計算した再識別率に基づいて上記秘匿データベースの再識別率を計算する再識別率計算部と、
   を含む安全性評価装置。
2. 請求項１に記載の安全性評価装置であって、
   上記近傍レコード集合のレコード数が所定の閾値よりも多い場合に上記近傍レコード集合中の重複レコードを排除する重複排除部をさらに含む、
   安全性評価装置。
3. 請求項２に記載の安全性評価装置であって、
   上記近傍レコード探索部は、上記近傍数を上記元データベースのレコード件数の対数として上記近傍レコード集合を取得するものであり、
   上記重複排除部は、上記閾値を上記近傍数の２倍として上記近傍レコード集合中の重複レコードを排除するものである、
   安全性評価装置。
4. 請求項１から３のいずれかに記載の安全性評価装置であって、
   上記近傍レコード探索部は、kd木を用いる近傍探索により上記近傍レコード集合を取得するものである、
   安全性評価装置。
5. データベース記憶部に、複数のレコードからなる元データベースと上記元データベースを秘匿した秘匿データベースとが記憶されており、
   近傍レコード探索部が、上記秘匿データベースの各レコードについて、上記元データベースに対する近傍探索により所定の近傍数の近傍レコード集合を取得し、
   最近傍レコード計算部が、上記秘匿データベースの各レコードについて上記近傍レコード集合の各レコードとの距離を計算し、当該レコードとの距離に基づいて最近傍レコードを取得し、
   再特定判定部が、上記秘匿データベースの各レコードについて、当該レコードに対応する上記元データベースのレコードが上記最近傍レコードと一致するか否かに基づいて当該レコードの再識別率を計算し、
   再識別率計算部が、上記秘匿データベースの各レコードについて計算した再識別率に基づいて上記秘匿データベースの再識別率を計算する、
   安全性評価方法。
6. 請求項１から４のいずれかに記載の安全性評価装置としてコンピュータを機能させるためのプログラム。

Images