DEIM Forum 2019 I6-3

道路ネットワークにおける位置情報プライバシ
高木

駿†

曹

洋††

浅野 泰仁††

吉川 正俊††† 京都大学工学部情報学科 〒 606–8501 京都府京都市左京区吉田本町 36-1†† 京都大学情報学研究科 〒 606–8501 京都府京都市左京区吉田本町 36-1
E-mail: †takagi.shun.45a@st.kyoto-u.ac.jp, ††{yang,asano,yoshikawa}@i.kyoto-u.ac.jp
あらまし 近年，位置情報の保護に，差分プライバシの概念を応用した Geo-I(Geo-Indistinguishability) を用いた方法が注目されている．Geo-I は，摂動法と呼ばれる自分の位置情報に雑音を加える際のプライバシ基準であるが，ユーク
リッド平面上で定義されており，道路ネットワークを考慮していない．そこで私たちは，それが原因で，近くのレストランを探すなどの近傍検索などの道路ネットワークを用いる LBS（位置情報サービス）に，単純な Geo-I の適用をすると，プライバシ保護の保証の不十分さ，有用性の低下という弱点が生じ得ることを明らかにした．さらに，それらの弱点を解決することのできるグラフ上の摂動法と，その満たすべきプライバシ基準 GGI(Geo-Graph-Indistinguishability)を提案した．次に，具体的なグラフ上の摂動法を提案し, それが GGI を満たすことを証明した．最後に，グラフ上でのプライバシ保護の度合いと有用性の定式化を提案し，日本の二つの都市の道路ネットワーク上で実験を行うことで，そのトレードオフに関してそのメカニズムが Geo-I を満たすあるメカニズムよりも優れていることを示した．
キーワード 位置情報の保護，Geo-Indistinguishability，差分プライバシ
攻撃者の前知識に強く，アルゴリズム，計算が簡単であるとい

1 はじめに近年，スマートフォンなどのモバイルデバイスの普及と GPS
システムの発達により，LBS（位置情報サービス）が急激に増加している．それらの使用は便利である一方，それらによる正確な位置情報の漏洩が，自宅や，職場などの個人情報の漏洩に繋がり，個人の特定などのプライバシに関する問題を起こしている．それを解決するために，位置情報の保護に関する研究が盛んに行われている．その保護の方法の一つに，この論文で扱う，摂動法と呼ばれる自分の位置情報にランダムな雑音を加える方法がある．摂動法では，ユーザが LBS 提供者に自分の位置情報を送る前に，メカニズムと呼ばれる確率分布を返す関数
に従ってランダムな雑音を加えることでプライバシを保護する．
そのため，雑音を自身の計算機のみで計算ができ，信頼できるサーバを必要としないが，LBS 提供者は雑音の加わった位置情報を基にサービスを提供する必要があるため，有用性（サービスの質）は雑音の大きさに依存する．有用性を上げるためにはユーザは雑音を小さくする必要があるが，その場合，プライバ
シ保護の度合いが低下する．つまり，有用性とプライバシの保護の度合いはトレードオフの関係にあり，摂動法の最も重要で，
難しい課題がこのトレードオフの良いバランスを実現することである．摂動法の中でも特に有名なのが，プライバシ基準である Geo-I(Geo-Indistinguishability) [1] を用いる方法である．
この基準は数学的に厳密なプライバシ基準である差分プライバ
シという広く受け入れられている強力な概念を位置情報に応用したものであり，この基準を満たすことでプライバシ保護を保証することができる．Andrés ら [1] はこの基準を満たすことでプライバシ保護の保証を得ると同時に，高い有用性を示す摂動法 PL を提案した．また，それは信頼できるサーバが必要なく，う利点を持ち，優れたものとして一般的に認められている．

Geo-I が発表されてから，Geo-I の弱点に関して様々な研究がされてきた．Yu ら [2] は Geo-I が最適化攻撃と呼ばれる攻撃に弱いことを示し，Geo-I に Geo-I と相補的な関係にある

Expected Inferece Error [3] の概念を取り入れて，弱点を補い合うような枠組みを作った．Chatzikokolakis ら [4] は Geo-I がプライバシの意味的な部分を捉えられていないことに着目し，人口密度や地域情報などの意味的なプライバシを保護できるメ
カニズムを構築した．Oya ら [5] は，プライバシ保護の度合いを [1] とは別の観点で定式化し，攻撃者がある事前分布を持つ
場合には Geo-I の満たすメカニズムのプライバシ保護の度合いがその観点で低いことを示した．
近くのレストランを探すなどの近傍検索の LBS は，道路ネッ
トワークを用いた方が近傍が正確に表されることから，より良いサービスを提供可能である．この研究では，こういった

LBS において，単純な Geo-I の道路ネットワークへの適用では，Geo-I が道路ネットワークを考慮せずに平面上で定義されていることが原因で，プライバシ保護の保証の不十分さ，有用性の低下という弱点が生じ得ることを明らかにした．例えば

PL を用いると，雑音を加えることによって，海の上などの人のいるはずのない場所を出力する可能性がある．この出力を見ると，その場所が本当の位置でないことは明らかであり，プラ
イバシ保護の度合いが低下している可能性がある．また，近くに橋のない大きな川がある場合，ユーザは対岸を遠いと感じる
が，Geo-I はユークリッド平面上で定義されているため近いと判断してしまい，有用性の低い場所を出力する可能性が上がってしまう．
そ こ で 私 た ち は ，グ ラ フ 上 で の 摂 動 法 と そ の 満 た す べ
き 道 路 ネット ワ ー ク 上 の プ ラ イ バ シ 基 準 GGI(Geo-Graph-Indistinguishability) を提案する．グラフ上での摂動法を用

ング距離) で表し，dh (D, D ′ ) = 1 のとき，D, D ′ は隣接していいることで，人がいるはずのない場所に曖昧化することを防ぐるという．このとき，ϵ ∈ R+ について差分プライバシは以下ことができ，上で述べたプライバシに関する弱点を解決するこのように定義される．

とができる．さらにこの摂動法が差分プライバシに基づく基準

GGI を満たすことで，強力な道路ネットワーク上のプライバシ
保護の保証を得ると同時に，道路ネットワーク上に合わせた基準であることから，近傍検索やミーティングポイントの決定などのサービスにおいて，Geo-I を用いた摂動法よりも高い有用性とプライバシ保護の度合いを期待できる．実際に，実験を行

定義 1. ϵ-差分プライバシ

クエリ q ∈ Q において，隣接している任意のデータベースの組 D, D ′ ∈ D ，および任意の出力の部分集合 S ⊆ Y について，

P r(m(q, D) ∈ S) < ϵeP r(m(q, D′ ) ∈ S) =(1)

うことで，GGI を満たす一つのメカニズム GE を提案し，そならば，計算機構 m の従う確率分布は ϵ-差分プライバシを満れが PL と PL をグラフ上のメカニズムへと拡張したメカニズ

たすという．

ムよりも，その観点で優れていることを示した．

直感的には，m が従う確率分布が ϵ-差分プライバシを満たす
とき，m(D) を観測されたとしても，隣接するデータベースに

2 関連研究対する出力 m(D′ ) が似ていることが保証されているため，あ

この章では，差分プライバシとその一般的なデータへの拡張，

Geo-I と位置情報のプライバシ保護に関する研究を紹介する．

る一つのレコード，すなわち個人のレコードが何であるかを推測できないことを表している．従って，データベースの統計量を ϵ-差分プライバシを満たす確率分布によってランダムな雑音

2. 1 ϵ-差分プライバシを加えることによって，個人のプライバシを保護しつつ有用性

この節では Geo-I の枠組みである Dwork [6] の差分プライバの高い出力をすることができるのである．

シを説明する．差分プライバシはデータベースにおける個人の2. 1. 2 一般的なデータへの拡張

データのプライバシ保護を目的としたプライバシ基準である．

Chatzikokolakis ら [7] はデータベース上でのみ定義されていあるデータベースから母集団に関する統計的な知識を提供す

た差分プライバシを一般的なデータへの拡張を行った．差分プる目的で統計量が公開されたとする．実はこのとき，個人の情

ライバシにおいて，データベース間のハミング距離 dh を用い報を知りたい攻撃者にこの統計量を見られると，個人の情報がて以下が導出される．

高い精度で推測されてしまう恐れがある．例えば，ある疾患に関する調査のデータベースがあったときに，”個人が疾患にかかっているかどうか”という情報は個人が知られたくない情報である．そこで，”全国の 30 代で疾患を持つ人の人数”・”東京
都在住で疾患を持つ人の人数”・”東京都在住の 30 代で疾患を持つ人の人数”という三つのクエリを発行したとする．このとき，東京都在住の 30 代の A さんが疾患を持つかどうかを攻撃者は推測できてしまうのだろうか．それは，攻撃者の事前知識や，データベースの内容に依って，できる可能性もあるし，でP r(m(q, D) ∈ S) < ϵdh (D,D′ )eP r(m(q, D′ ) ∈ S) =(2)

[7] はこの不等式が表す概念を，データベースからデータへの一般化を行った．ここで，あるドメイン Z 上の確率分布を与えるあるドメイン X 上のメカニズム K : X → P(Z) を考える．

P(Z) は，Z 上の確率分布を表す．このとき，X 上の”距離”を表す dX を用いて，ある ϵ ∈ R+ について，差分プライバシを一般化したものである ϵdX -privacy は以下のように定義される．

きない可能性もあるとしか言えなく，プライバシが保護されて定義 2. メカニズム K が任意の x, x′ ∈ X , Z ⊆ Z について，いる保証はない状態なのである．そこで，Dwork は差分プライ以下の不等式バシと呼ばれるデータベースから個人のプライバシを保護するために満たされるべき基準を提案し，今やその基準はあらゆる攻撃者やデータベースに対してプライバシの保護ができる，強力な基準であることが広く認められている．

2. 1. 1 定K(x)(Z) <ϵdX (x, x′ )K(x′ )(Z) =(3)を満たすとき，K は ϵdX -privacy を満たすという．
この定義は二つのデータベースが似ているほど，生成される義

ここではその定義を述べる．そのためにまず，記法を導入す分布は似ているべきであるという差分プライバシの概念を一る．X をレコードのドメイン，レコード x ∈ X を個人の情報を般化したものと言える．これに従えば，差分プライバシの場合含むデータ，レコードの集合をデータベース D = {xi }ni=1 とす((2) 式) は x ∈ X はデータベースを，dX はハミング距離 dh をる．データベース D ∈ D とクエリ q ∈ Q を受け取り，クエリの表している．[7] ではメカニズム K が ϵdX -privacy を満たすと応答値 q(D) にランダムな雑音を加えた応答値 y ∈ Y を返す計

き，一般的に，以下の二つの性質を満たすことを示している．

算機構を m と置く．ここで取りうるデータベースの集合を D，a ) hiding function

クエリ応答値に雑音を加えた結果得られる値の集合を Y ，取り

一つ目の性質は任意の関数 hiding function ϕ : X → X のうるクエリの集合を Q とした．2 つの同じサイズのデータベー概念を用いて示される．一般的に，任意の攻撃者が任意の′′

ス D, D において，同一でないレコードの数を dh (D, D )(ハミz ∼ K(x),z ′ ∼ K(ϕ(x)) のそれぞれを観測したときに得る事後分布間の multiplicative distance は以下の不等式を満たす．

dP (p(x|z), p(x|z ′ )) <= 2ϵdX (ϕ)

ataccker に関する保証（2. 1. 2 節）を持つ．2. 1. 2 節で説明し(4)

たように，これらは任意の攻撃者に対する，ある程度のプライ
ここで dX (ϕ) を supx∈X dX (x, ϕ(x)) と定義する．この式は，ある似ている二つの入力に対するメカニズムの出力を観測したとき，攻撃者の二つの事後分布が似ていることを保証しており，
本当のデータ x が何であるかについてあまり情報を得ることができないことを表している．ここで，攻撃者を仮定していない
ため，dX -privacy を満たすメカニズムは任意の攻撃者に対してある程度のプライバシ保護を保証していることがわかる．

バシ保護の保証を示している．
この論文 [1] が発表されてから，様々な応用が研究されてきた．To ら [8] はプライバシを保護した時空間クラウドソーシ
ングサービスのフレームワークを Geo-I を使って構築した．

Bordenabe ら [9] は位置情報を簡略化し，位置情報を減らすことで最適化の計算を可能にし，Geo-I を満たすメカニズムの中で 2. 4 節で述べる有用性の観点で最適なものを導出した．他にb ) informed attacker

も様々な応用の研究がされており，位置情報のプライバシ保護

もう一つの性質は攻撃者の持つ事前分布と事後分布の距離をの研究の中で最も注目されていると言える．

用いて示される．この距離を測ることで攻撃者が出力を観測したときに，どれだけデータについて知ることができるかを測

2. 3 複数の位置情報の曖昧化ることができる．ここで保護したいデータ x ∈ X がある集合

ここで複数の位置情報プライバシを保護する場合を考える．[1]N ⊆ X に含まれていると知っている攻撃者 informed attacker

でも述べられているように，このプライバシの保護の方法としを仮定する．このとき，その攻撃者の持つ任意の X 上の事前て，一つ一つの位置情報に Geo-I を適用する単純な方法が考え

分布 π と任意の z ∼ K(x) を観測したその事後分布に対して，られる．しかし，この方法は，差分プライバシに由来する合成

全ての N ∈ N について以下の不等式が成り立つ．

定理と呼ばれる定理によって，プライバシ保護の度合いが低下

dP (π|N , p|N (x|z)) <= ϵdX (N )してしまう．例えば相関性のある k 個の位置情報を ϵ-Geo-I を(5)満たすメカニズムで曖昧化する場合，そのプライバシ保護の保

ここで π|N (x) = π(x|N ), p|N (x|z) = p(x|z, N )，dX (N ) =証は kϵ-Geo-I となり，k 倍低下する．これは差分プライバシの

maxx,x′ ∈N dX (x, x ) とする．これは，dX (N ) が小さいほど事分野でも未解決問題であり，これを解決するための方法は盛ん

前分布と事後分布が似ている，つまり攻撃者が x について詳しに研究されている．

′

く知っているほど新たな情報を得られないというを表している．

ここではそれに関する新しい研究の一部を紹介する．Kairouz
ら [10] は合成定理をナイーブな場合だとプライバシの保護の2. 2 Geo-Indistinguishability

度合いが O(k) 倍まで低下していたのを O(k 1/2 ) 倍まで抑える

ここでは，差分プライバシの概念を応用した位置情報のプラメカニズムを提案した．Chatzikokolakis ら [11] は Geo-I を用

イバシ基準 Geo-I を説明する．X をユーザの存在しうる位置のいて，相関を持つ位置情報に対応する方法を提案した．Xiao

集合，Z をメカニズムによって曖昧化した結果得られる位置のら [12] は移動しているユーザが位置情報を送信する際の差分プ集合とする．直感的には，メカニズム K が Geo-I を満たすとは，

ライバシに基づくメカニズムを提案した．

′′

任意の似ている位置 x, x ∈ X について確率分布 K(x), K(x )が似ているということを表している．これはユーザが確率分布

2. 4 有用性，プライバシ保護の度合いの定式化

K(x) に従って位置 z ∈ Z を出力したときに，攻撃者が z を観

Shokri ら [3], [13] はメカニズムを用いた位置情報を保護する

測しても K(x) から出力されたのか，K(x′ ) から出力されたの方法で曖昧化した際の，有用性とプライバシ保護の度合いの定か見分けがつかない状態を表し，そうすることによってユーザ

式化，攻撃者のモデル化を行った．

の位置情報 x を保護している．ϵ ∈ R+ について Geo-I は以下

2. 4. 1 有 用 性
LBS がユーザに提供するサービスの質（有用性）SQL(Serviceのように定義される．

Quality Loss) はユーザの曖昧化した位置とサービスの種類に
定義 3. (ϵ-Geo-Indistinguishability) メカニズム K が任意の依存する．つまり，ユーザが自分の位置を受けるサービスの観x, x′ ∈ X について以下の不等式

点で似ている位置に曖昧化したなら受けるサービスの質は良い′
dP (K(x), K(x′ )) <= ϵd(x, x )(6)を満たすとき，K は ϵ-Geo-Indistinguishability を満たすという．

d(x, x′ ) はユークリッド距離を表す．この定義は ∀x, x′ ∈ϵd(x,x′ )<X , Z ⊆ Z, K(x)(Z)と書き換えることができ，Geo′=e

し，似ていない位置に曖昧化したなら受けるサービスの質は悪くなると考えられる．このことからメカニズム K による有用性は以下のように定式化することができる．

SQL(πu , K, dq ) =∑πu (r)K(r)(r′ )dq (r, r′ )

(7)

r,r ′

K(x )(Z)I は (3) 式 (ϵdX -privacy の定義式) において，データを位置情

πu はユーザがいる位置の確率分布を表し，ユーザの事前分布と報，距離 dX をユークリッド距離 d にしたものであることがわ

呼ぶ．dq (r, r ′ ) は使用される LBS によって異なる r と r′ の非かる．

類似度を表し，(7) 式はメカニズム K で曖昧化した位置 r′ と本

Geo-I は ϵdX -privacy の一つであるから，ϵdX -privacy の持当の位置 r の非類似度 dq (r, r ′ ) の期待値を表している．Shokri

つプライバシ保護の保証，つまり，hiding function と informed

らは dq (r, r ′ ) として，r と r′ のユークリッド距離を用いている．

2. 4. 2 プライバシ保護の度合い
プライバシの保護の度合い (Location Privacy) はメカニズム
によって曖昧化された位置を攻撃者が見たときに，どれくらいの精度でユーザの本当の位置を予測できるかで測ることができる．よって，以下のように定式化することができる．
∑
LP (πu , K, h, dq ) =πu (r)K(r)(r′ )h(r′ )(r̂)dq (r̂, r)
r̂,r ′ ,rh は攻撃者の予測関数であり，h(r′ )(r̂) は攻撃者が r′ を観測したときにユーザの位置を r̂ と予測する確率を示す．つまり LP
は攻撃者が予測するユーザの位置 r̂ と，ユーザの本当の位置 rの非類似度 dq (r̂, r) の期待値を表す．有用性と同様に，Shokri

図 1 仮想的なマップ．

らは dq としてユークリッド距離を用いている．

3. 1 プライバシ保護の保証の不十分さ

2. 4. 3 攻撃者モデル
攻撃者は曖昧化された位置を観測して，本当の位置を推測しここでは，攻撃者が道路ネットワークを考慮することで，ユーようとする．このとき，攻撃者はユーザの位置の事前知識を表ザの位置情報の予測の精度を上げることができる可能性がある

す確率分布 πa を持ち，ユーザの使ったメカニズム K を知ってことを実験を行うことで示す．ここで，Geo-I を満たすメカニいるとする．攻撃者は曖昧化された位置を観測したときに，最ズムとして PL [1] を使用する．これは平面ラプラス分布を利用

適化攻撃 [13] を使ってユーザの位置を推測する．最適化攻撃でϵしたもので，P Lϵ (x)(z) = 2πe−ϵd(x,z) と表される．メカニズ

は，攻撃者は以下の線形計画問題を解いて予測関数 h を導出し，ムによるプライバシ保護の度合いとして LP（2. 4. 2 節）を用

この予測関数 h に基づきユーザの位置を推測する．

いることとする．この LP として，[1], [3] で用いられたメトリッ

minimizehsubject toクにユークリッド距離を適用した以下の LPe を用いる．

∑

′

′

πa (r)K(r)(r )h(r )(r̂)dp (r, r̂)r̂,r ′ ,r∑2h(r′ )(r̂) = 1, ∀r′ ,(8)LPe (πu , K, h) = LP (πu , K, h, d)∑=πu (r)K(r)(r′ )h(r′ )(r̂)d(r̂, r)

r̂

∑

′
h(r′ )(r̂) >= 0, ∀r , r̂

r̂

(9)

r̂,r ′ ,r

これはユーザの事前分布に対する，メカニズム K を用いたと
きの，ユーザの本当の位置と予測関数 h を用いる攻撃者の予測する位置の間のユークリッド距離の期待値を表している．ここ

表 1 記号の意味

からは，実際に PLϵ を用いて曖昧化を行った場合，攻撃者が道

記号

意味

LBS

位置情報サービス (location based service)u, a

ユーザ，攻撃者X

二次元平面上の座標の集合

持つ 100m*100m で分割されている 4000m*4000m の仮想的なG

重み付き無向連結グラフ (V, E)

空間上 (図 1) で行なった．

V

二次元平面上のグラフの頂点集合

E

辺集合．重みは頂点間の最短の道路上の距離

内の一様分布とする．道路ネットワークを考慮しない攻撃者は

πu (r)

ユーザ u が r にいる確率

黒枠内の一様分布を事前分布として持ち，道路ネットワークを

πa (r)

攻撃者 a が持つユーザが r にいる確率

路ネットワークを考慮すると，LPe を下げることができる可能性があることを実験を行うことで示す．実験は格子点に座標を

中央の赤線を道路とし，ユーザの事前分布を内側にある黒枠

考慮する攻撃者はユーザは黒枠内の赤線上の一様分布を事前分K(r)(r′ )メカニズム．位置 r を r ′ に曖昧化する確率d(x, x′ )x と x′ のユークリッド距離

ds (v, v ′ )頂点 v, v ′ 間のグラフ上の最短距離

る LP を図 2 に示した．攻撃者は道路情報を考慮することによSQL(πu , K, dq )曖昧化した位置と u の位置の dq の期待値

り，LPe を下げる，つまり予測の精度をかなり上げることがでLP (πa , K, h, dp )a が推測する位置と実際の位置の dq の期待値

きていることがわかる．これは PL が平面上で定義されたメカ

3 道路ネットワークにおける
Geo-Indistinguishability の弱点
この章では 1 章で述べた，道路ネットワークを考慮することで生じる Geo-I の弱点について詳しく述べる．

布としてを持つとする．このときの ϵ に対する各攻撃者に対すニズムであり，道路以外の人の存在し得ない場所に曖昧化してしまうために，道路情報を持つ攻撃者がそれによって曖昧化された位置をみると，精度の高い予測ができる可能性があることを表している．
平面上で定義された Geo-I を満たすメカニズムは，道路ネッ

ここで，道路ネットワークを無向連結グラフ G = (V, E) とトワークを考慮しない平面上の一定の事前分布を持つ攻撃者

して定義する．V は平面上の頂点集合，E は重み付きの辺集合に対しては，LPe は一定の値を取り，強いプライバシ保護の保である．e = (v1 , v2 , we ) ∈ E において，重み we は頂点 v1 , v2証を持つ．しかし，この実験で示したように，全ての攻撃者は間の道路の最短の距離を表している．

道路ネットワークを考慮することができ，平面上の点によって

これは ϵdX -privacy の概念を道路ネットワークを表すグラフ

LP(m)

700

に適用したものであり，(3) 式のデータ x ∈ X をグラフの頂

not_knowing_road
knowing_road

600

点 v ∈ V ，距離 dX を頂点間の最短経路長 ds にしたものであ500

るから，道路ネットワークに対する ϵdX -privacy の自然な適用と考えられる．直感的に，この定義は任意の v, v ′ ∈ V に対し

400て v と v ′ の間の最短経路長 ds が近いほど，K(v), K(v ′ ) が似300ていることを意味しており，摂動後の頂点を観測した攻撃者が200

v から出力されたのか，v ′ から出力されたのかが見分けがつか100ないことを保証している．ϵ がその保証の度合いを表しており，
0.00250.00500.00750.0100 0.0125
epsilon0.01500.0175ϵ を調整することでユーザは，任意のプライバシーレベルを得

0.0200

ることができる．また，ϵ-GGI は ϵdX -privacy の一つであるか

図 2 道路情報を持つ攻撃者と持たない攻撃者の LP．
（人工データ）ら，2. 1. 2 節で説明した ϵdX -privacy の持つプライバシ保護の保証 [7] を持つ．

様々な LPe （場合によってはかなり低い）を取り得ることがわ
かる．これは，道路ネットワークを用いた LBS における Geo-I

4. 2 ϵ の 解 釈
ϵ-GGI を満たすメカニズムが 2. 1. 2 節で述べたプライバシ保のプライバシ保護の保証の不十分さを表している．

護の保証を持つことがわかったが，結局，ϵ の取る値によって，

3. 2 近傍検索における有用性の低下

どの程度のプライバシ保護を保証しているかは理解し難い．そ近くのレストランを探すなどの近傍検索において，有用性はこで，この節では，ϵ の値によるメカニズムのプライバシの保

ユークリッド距離ではなく，道路ネットワーク上の最短経路長

護の度合いを定式化する方法として LPs を用いることを提案

で測られると考えられる．そのことから，道路ネットワークをする．LPs は LP(2. 4. 2 節) を道路ネットワークに適用したも用いる LBS における有用性として，メトリックにグラフ上のので，ユーザの事前分布 πu と攻撃者の予測関数 h に関して，

最短経路長 ds を用いた SQLs を提案する．

以下のように表される．予測関数 h は, 一例として最適化攻撃

SQLs (πu , K) = SQL(πu , K, ds )∑=πu (v)K(v)(v ′ )ds (v, v ′ )（2. 4. 3 節）によるものが考えられる．

(10)

v,v ′

LPs (πu , K, h) = LP (πu , K, h, ds )∑=πu (r)K(r)(r′ )h(r′ )(r̂)ds (r̂, r) (12)r̂,r ′ ,rGeo-I はユークリッド距離を用いて定義されているために，
Geo-I を満たすメカニズムは上の有用性が低くなると予測でき

これは，メカニズム K を用いたときの，ユーザの事前分布 πuる．例えば，横断できない大きな川があるとき，対岸に曖昧化に対する，本当の頂点と予測関数 h を用いる攻撃者の予測するされるのは有用性が低いと考えられるが，Geo-I はそれを考慮

頂点の間の最短経路長の期待値を表している．

することはできない．これについては 5 章で詳しく述べる．

さらに，各ユーザが自分のいる位置 r でメカニズム K を用いた場合のプライバシ保護の度合いの定式化 LPrs を提案する．
∑
LP rs (r, K, h) =K(r)(r′ )h(r′ )(r̂)ds (r̂, r)

4 Geo-Graph-Indistinguishabilityr ′ ,r

本章では前章で述べた Geo-I の弱点を解決することのできる，
道路ネットワークを考慮したプライバシ定義である GGI(Geo-

これは頂点 r でメカニズム K を用いた場合の，ユーザの本当

Graph-Indistinguishability) の定義を提案し，そのプライバシの頂点 r と予測関数 h を用いる攻撃者の予測する頂点の間の最保護の保証を説明する．最後に，それを満たすメカニズムを提短経路長の期待値を表している．各頂点の各 ϵ に対する LPrs

案する．

の値をユーザに与えておくことで，各頂点 r にいるユーザはプ
ライバシ保護の度合いを解釈し，調整することができる．例え

4. 1 定義

ば LPrs が 100 m であるなら，このメカニズムを用いることで，グラフ上のメカニズム K は V 上の頂点に対して頂点集合

W ⊆ V 上の確率分布を与える関数 K : V → P(W ) で与えられる．ここで，ϵ ∈ R+ に対して ϵ-GGI を以下のように定義する．
定義 4. (ϵ-Geo-Graph-Indistinguishability) グラフ上のメカニ
ズム K が任意の頂点 v, v ′ ∈ V について以下の不等式′
dP (K(v), K(v ′ )) <= ϵds (v, v )示す．

4. 3 GGI を満たすメカニズム
ここでは GGI を満たすメカニズムを提案し，その証明を与える．ϵ ∈ R+ ，頂点 v ∈ V が与えられたとき，W 上の確率分(11)を満たすとき，K は ϵ-Geo-Graph-Indistinguishability を満たすという．

ユーザは平均的に 100 m の範囲で位置情報を保護できることを布を与えるグラフ上のメカニズム GE を以下のように定義する．
定義 5. GEϵ (Graph-Exponential-Mechanism)ϵGE(v)(w) = α(v)e− 2 ds (v,w)(13)

α は正規化係数で以下のように表される．
1α(v) = ∑

500

(14)

ϵ d (v,w)
−2
s

w∈V e

PL_not_knowing_road
PL_knowing_road
GE_knowing_road

400
LPe(m)

このメカニズムは差分プライバシの指数メカニズム [14] に対応
している．

300
200

定理 1. GEϵ は ϵ-Geo-Graph-Indistinguishability を満たす．

100

Proof. 任意の二点 v, v ′ ∈ V で以下が成り立つことを示せば

200

300

400

よい．

′

の比の最大値を調べれば良い．任意の v, v ∈ V, w ∈ W について以下が成り立つ．

800

5. 1 プライバシ保護の保証
ここでは，GE が PL よりプライバシ保護の保証の観点で優れていることを示すために，3. 1 節で行なった実験を GE を用

ϵ d (v,w)−2s

GE(v)(w)α(v)ea(v) 2ϵ (ds (v′ ,w)−ds (v,w))=eϵ d (v ′ ,w) =′−′s
GE(v )(w)a(v ′ )
α(v )e 2
これが最大値を取るのは，頂点 w ∈ W に対して ds (v ′ , w) −ds (v, w) が最大値をとるときである．G は無向連結グラフである
から，任意の頂点を経由でき (三角不等式)，∀w ∈ V, −ds (v, w)+′′

いて行い，PL とプライバシの保護の度合い LPe を比較する．
比較を公平にするために，有用性が同じ値のときの LPe を比較することを考える．ここで，有用性として以下式で表される
ユークリッド距離に関する SQLe を使用する．

SQLe (πu , K) = SQLe (πu , K, d) =′ds (v , w) <= −ds (v, w) + ds (v , v) + ds (v, w) = ds (v, v ) が成∑

πu (r)K(r)(r′ )d(r, r′ )

r,r ′

(18)

り立つ．よって以下の不等式が成り立つ．

GE(v) < α(v) 2ϵ ds (v,v′ )eGE(v ′ ) = α(v ′ )(16)

これはユーザの事前分布に関する，本当の位置と曖昧化された
位置の間のユークリッド距離の期待値を表している．GE と PLの SQLe に対する LP を図 3 に示す．それぞれの SQLe が等し

ここで以下が成り立つことを示す．

いときの，道路情報を持つ攻撃者に対する LPe を比較すると，

′
ϵ
α(v)
< e 2 ds (v,v )α(v ′ )

(17)(14) より，任意のグラフ G の任意の頂点 v, v ′ ∈ V, w ∈ W に
∑
′
′ ∑
ϵ
ϵ
ϵ
ついて， w∈V e− 2 ds (v ,w) − e 2 ds (v,v ) w∈V e− 2 ds (v,w) < 0
を示せば良い．三角不等式より，∀w ∈ W, d(v, w) − d(v, v ′ ) <
=
′

ϵ

ϵ

′

− (ds (v,w)−ds (v,v ))ds (v ′ , w) が成り立つから， e− 2 ds (v ,w) <=e 2が成り立つ．よって，
ϵ

700

(15)

つまり，任意の二点 v, v ′ ∈ V が生成する分布 GE(v) と GE(v ′ )∑600

図 3 PL と GE の SQL に対する LP．
（人工データ）′dp (K(v), K(v ′ )) <= ϵds (v, v )(与式) <=

500
SQLe(m)′ϵ′(e− 2 ds (v ,w) − e− 2 ds (v ,w) ) < 0w∈V(16),(17) より，(15) が成り立つ．

GE の方が LPe が高いことが読み取れる．これは GE を用いた場合，攻撃者が攻撃の精度を大きく上げられていないこと示しており，GE が道路情報を持つ攻撃者に対してより強い位置
情報の保護ができていることを表している．このことから，プ
ライバシの保護の度合いに関して，GE の方が優れていると言える．

5. 2 有 用 性
ここでは，有用性として 3. 2 節で定義した道路ネットワークを用いた LBS における有用性 SQLs を用いて，Geo-I を満たすメカニズムと GGI を満たすメカニズムの有用性を比較する．

PL はグラフ上のメカニズムではなく，平面上のメカニズムであるため ds が定義されていなく，SQLs が計算できない．そこ5 評価実験
この章では，実験を行うことで，GE が Geo-I を満たすあるメカニズムよりも，プライバシ保護の度合いと 3. 2 節で定義した有用性の観点で優れていることを示す．まず，プライバシ保で，PL の自然な拡張であり，かつ Geo-I を満たすグラフ上のメカニズムとして，下のようなメカニズム PLG を導入する．
∫
P LG(v)(w) =P Lϵ (xv )(z)dz(19)
Sw

護の観点で優れていることを示すために，3. 1 節で行った実験

Sw はグラフの頂点に関する平面上のボロノイ図を考えたときを GE を用いて行い，LPe の値を PL と比較する．次に有用性の w のボロノイセル，xv は頂点 v の座標を表す．PLG(v) は，の観点で優れていることを示すために，日本の二つの都市でグ

直感的には PL(xv ) に従って頂点 v を平面上の点 z に曖昧化しラフを取得し，そのグラフ上で GE と以下で提案する Geo-I をて，z からユークリッド距離で一番近いグラフ上の頂点にリマッ

満たすグラフ上のメカニズム PLG で実験を行い，それぞれのピングをすることを考えたときにできる W 上の確率分布を意

SQLs を比較した．

味している．つまり，PLG(v)(w) は PL が v を w のボロノイ

セル上に曖昧化する確率を表しており，Geo-I を満たすナイー
ブなグラフ上のメカニズムと言える．
命題 1. PLG は ϵ-Geo-Indistinguishability を満たす．

Proof. 任意の二点 v, v ′ ∈ V で以下が成り立つことを示す．
′
dp (P LG(v), P LG(v ′ )) <= ϵd(v, v )(20)∀v, v ′ ∈ V, w ∈ W について，以下を示せば良い．
′

ϵd(v,v )P LG(v)(w) <P LG(v ′ )(w)
=e

図4

(21)

PLϵ は ϵ-Geo-I を満たすから，任意の z ∈ Z で以下を満たす．
ϵd(xv ,xv ′ )P Lϵ (xv )(z) <=e

P Lϵ (xv′ )(z)(22)

取得したグラフ．
（左が東京，右が秋田）′
dP (K(xv ), K(xv′ )) <= ϵd(xv , xv′ ) <= ϵds (v, v )(24)

逆に，全ての GGI を満たすメカニズムは Geo-I を満すわけではないことがわかる．これは，GGI がユークリッド距離に関して，プライバシ保護の保証を持たないことを意味している．つ積分不等式の基礎定理より以下が成り立つ．
∫∫<
P Lϵ (xv )(z)dz =eϵd(xv ,xv′ ) P Lϵ (xv′ )(z)dz
Sw

Sw

= e

∫

ϵd(xv ,xv ′ )P Lϵ (xv′ )(z)dz (23)Sw(19),(23) より，(21) が成り立つ．

まり，GGI を満たすメカニズムで位置を曖昧化したとき，ユー
クリッド距離に関して近い位置でも，攻撃者からは簡単に識別することができてしまう可能性がある．このことを以下で示す．
攻撃者がメカニズム K を用いるユーザの位置を識別できる確率は以下のように表すことができる．

T P (πu , K, h) =∑πu (v)K(v)(w)h(w)(v̂)δ(v̂, w) (25)v̂,v,w以上より SQLs を計算することのできる Geo-I を満たすメ
カニズム PLG を導出できた．ここから，Geo-I と GGI の有用δ(v̂, w) は v̂ = w が成り立つときに 1 を，成り立たないときに性を比較するために，PLG と GE の SQLs を比較する．公平

0 を返す関数とする．TP は攻撃者が最適化攻撃によって，曖に比較をするために，PLG と GE のプライバシ保護の度合い昧化された位置を正しい位置にリマッピングができる確率の期

LPs（4. 2 節）が等しいのときの SQLs を比較する．PLG の分待値を表している．ここで，ユークリッド距離が一定の二つの布は FORTRAN の数値積分ライブラリを用いて近似的に求め頂点のみを持つグラフを考える．このグラフの最短経路長が変た．そのため，確率に誤差があるが，適応 Gaus-Kronrod 積分化するときに，PLG と GE で曖昧化を行った際に TP がどのを用いているため誤差は十分に小さく，理想的な PLG と比べように変化するかを示すグラフを図 7 に示す．ユークリッド距てもプライバシ保護の度合いの低下は無視できる．

離が一定であり，ユークリッド距離に関してプライバシ保護の比較実験のために使用したデータセットについて説明す保証を持つ PLG は TP は上がらないが，GE はユークリッド

る ．OpenStreetMap を 利 用 し て ，東 京 と 秋 田 の 二 箇 所 で距離に関する保証を持たないため，ユークリッド距離が一定で4000m*4000m の範囲のグラフを取得した (図 4)．ユーザのあっても最短経路長が大きくなると，攻撃者の攻撃の精度が大事前分布，攻撃者の持つ事前分布を共に中央から最短経路長できく上がるのである．

1

2000m の範囲としたときに，PLG と GE の各 LPs での SQLsGGI の考え方は，ユークリッド距離の代わりにグラフ上の最をプロットするとそれぞれ図 5, 図 6 のようになった．これらを短経路長に関してプライバシを保証することで，Geo-I と比べ見ると，二つのマップにおいて，PLG よりも GE の方が常にて有用性を上げることができるというものである．その考えのSQLs が低いことがわかる．つまり，GE の方が有用性が高い

根底にはプライバシをどう捉えるかがあり，多くの LBS では，ことを読み取ることができる．また，東京と秋田の結果を比べ有用性やプライバシをグラフ上の最短経路長で考えるほうが妥

ると，同じ LP のとき，SQL の差が秋田のグラフの方が大きい

当と考えられる．一方で例えば，天気を取得する場合など，広ことがわかる．これは，秋田のグラフの方がグラフ上の最短経範囲でのプライバシ保護が必要な場合は，プライバシをグラフ

路長とユークリッド距離の差が大きいことが理由の一つに考えを考えるより地域，つまりユークリッド距離で考える方が自然られる．

であり，GGI は適していないと考えられる．また，この論文では GGI にグラフ上の最短経路長を使用したが，プライバシの

6 議論

道路ネットワークの定義より，任意の頂点 v, v ′ について′d(xv , xv′ ) <= ds (v, v ) が成り立ち，Geo-I を満たす任意のメカ

ニズム K は GGI を満たすことがわかる．

捉え方を変えることで，移動にかかる時間で距離を表す時間距
離などの他の距離への応用が簡単にできると信じている．

7 おわりに
本研究では，Geo-I が道路ネットワークを考慮できていない

1：https://openstreetmap.jp/

ことに着目し，道路ネットワークを考慮した新しいプライバシ

600

plg
ge

SQL(m)

500

400

300

200

100

150

図5

200

250
LP(m)

300

350

400

データ「東京」に対する結果．

図6

データ「秋田」に対する結果．

18H04093, (C) No. 18K11314 の助成を受けたものです．

文

図 7 GE と PLG の TP の変化

定義 GGI を提案し，これを満たすメカニズム GE が，差分プライバシの利点を得ると共に，Andrés らが提案した Geo-I を満たすメカニズム PL よりも，プライバシの観点で優れている
ことを示し，PL のグラフ上への拡張である PLG よりも，有用性の観点でも優れていることを日本の二つの都市で示した．
しかし，GGI にも考えられる課題が三つある．一つは道路
ネットワークを無向グラフで扱っていることである．実世界には一方通行があり，道路ネットワークは有向グラフで表される．
このことにより，有用性が低下していると想定される．二つ目が意味的なプライバシを捉えられていないことである．GGI の定義では，グラフ上の距離 r の範囲で ϵr-privacy を保証しているが，今回使用した東京の地図でグラフ上の距離 r で ϵr-privacyが保証されていることと，秋田の地図で同じことが保証されていることは，GGI のプライバシの定義的には同じことであるが，意味的なプライバシでは異なっている．同じ最短経路長 rの範囲であっても，ユーザは頂点や辺（つまり，道路）が少な
い方がプライバシを低く感じるのであろう．例えば，秋田の地図を見ると，ある距離 r の範囲には道路の数が少なく，GE を用いる場合，その道路にいることは安易に推測されてしまうだ
ろう．最後が 2. 3 節でも述べたように，複数の位置情報を曖昧化した際に相関性がある場合，プライバシが大きく低下してしまうことであり，Geo-I や差分プライバシでも未解決問題である．今後はこれらの課題を解決する方法を考えていきたい．

8 謝

辞本研究は JSPS 科研費基盤研究 (S) No. 17H06099, (A) No.

献[1] K. Chatzikokolakis M. E. Andrs, N. E. Bordenabe andC. Palamidessi. Geo-indistinguishability: Diﬀerential privacy for location-based systems.
[2] Calton Pu Lei Yu, Ling Liu. Dynamic diﬀerential location
privacy with personalized error bounds.
[3] C. Troncoso J.-P. Hubaux R. Shokri, G. Theodorakopoulos
and J.-Y. Le Boudec. Protecting location privacy: Optimal
strategy against localization attacks.
[4] C. Palamidessi K. Chatzikokolakis and M. Stronati. Constructing elastic distinguishability metrics for location privacy.
[5] C. Troncoso S. Oya and F. Prez-Gonzlez.
Is geoindistinguishability what you are looking for?
[6] C. Dwork. diﬀerentiall privacy. in Automata, Languages
and Programming, pp. 1–12, 2006.
[7] N. E. Bordenabe K. Chatzikokolakis, M. E. Andrs andC. Palamidessi. Broadening the scope of diﬀerential privacy using metrics. Privacy Enhancing Technologies, pp.
82–102, 2013.
[8] C. Shahabi H. To and L. Xiong. Privacy-preserving online
task assignment in spatial crowdsourcing with untrusted
server. in 2018 EEE 34th International Conference on Data
Engineering (ICDE), pp. 833–844, 2018.
[9] K. Chatzikokolakis N. E. Bordenabe and C. Palamidessi.
Optimal geo-indistinguishable mechanisms for location privacy. in Proceedings of the 2014 ACM SIGSAC Conference
on Computer and Communications Security, New York,NY, USA, pp. 251–262, 2014.
[10] S. Oh P. Kairouz and P. Viswanath. The composition theorem for diﬀerential privacy. IEEE Transactions on Information Theory, 2017.
[11] C. Palamidessi K. Chatzikokolakis and M. Stronati. A predictive diﬀerentially-private mechanism for mobility traces.
Privacy Enhancing Technologies, pp. 21–41, 2014.
[12] Y. Xiao and L. Xiong. Protecting locations with diﬀerential privacy under temporal correlations. Proceedings of the
22nd ACM SIGSAC Conference on Computer and Communications Security - CCS 15, pp. 1298–1309, 2015.
[13] J. L. Boudec R. Shokri, G. Theodorakopoulos andJ. Hubaux. Quantifying location privacy.
[14] F. McSherry and K. Talwar. Mechanism design via diﬀerential privacy. in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07), pp. 94–103, 2007.