LinkedIn’s Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
Audience Engagement API
ある特定のグループの興味関心のあるトピックや記事を分析しマーケティングに活用するための分析ツール
クエリに対する差分攻撃を防ぐために設計・開発
単に、クエリのグループ規模を制限するだけだと不十分で差分プライバシーを保障する必要
COUNTのヒストグラムを得るような分析（少なくとも当論文では）
アーキテクチャ
https://gyazo.com/ea47e82a46430c0a518e0925152bf310
分析者からクエリとDPアルゴリズムを選択して送信
アプリケーションがDPライブラリを用いて、
privacy costを推定、
Pinotへのクエリに用いられるDPバージョンのクエリに修正
例：unknown domainにおいて、d=2kの場合はtop-kクエリが2kに修正など
Budget Management Serviceにその分析者が十分なbudgetが残っているかチェック
残っているbudgetがそのクエリの推定privacy costより小さい場合はクエリを実行しない
budget検証後、修正されたクエリがPinotで実行
クエリ結果がアプリケーションに返され、DPライブラリが対応するDPアルゴリズムを実行し結果が返される。
DPの結果に基づいて、Budget Management Serviceがパラメタ k*, l* を更新
DPアルゴリズム
TBオーダーのデータを分析するため差分プライバシーによるオーバーヘッドは最小限にする必要
https://gyazo.com/4b8263013e991477e044d82e8931fbd7
Δ-restricted sensitivity
ある固定のデータグループ数Δにおいて合計値に最大１の影響を与える
例：ある特定のスキルセットを持つユーザーがいる国トップk を計算
あるユーザーが一つの国にしかいない場合はΔ=1
--> 現実的に1人のユーザーが滞在している国数はΔに抑えられる
unrestricted sensitivity
ユーザーが任意の要素数にわたってせいぜい１の合計値を影響に与える
例：ユーザーのライク数・コメント数・シェア数などのエンゲージメントによって上位 k 記事を計算
--> 1人のユーザーは任意数の記事にエンゲージメント可能
Known Domain
データドメイン（グループ）の数が有限
Unknown Domain
データドメインの数がとても大きい・分からない
DPアルゴリズムでアクセス可能なドメイン数を指定するパラメタdを設定
KnownLap
標準的なLaplaceメカニズム
sensitivityがboundedなのでLaplaceノイズが加えられる
KnownGumb/UnkGumb
Gumbelノイズを加える指数メカニズム
デフォルト：UnkGumb
Privacy Budget
call budget (l*)
δ
何回クエリすることが可能か
l* <- l* -1
information budget (k*)
ε
いくつのグループをレスポンスすることが可能か
Δ-restrected sensitivity
k* <- k* - Δ
unrestricted sensitivity
k* <- k* - 2|o|
|o|: クエリ結果で返されるグループ数
分析者同士の結託は想定しない
ユーザーのデータライフサイクルに合わせて所定のタイムフレームでバジェットはリフレッシュ可能
Budget Management SystemのKVSはEspresso
クエリエンジン・OLAP datastore
https://gyazo.com/680953ffff091c4702536e3d48af6ce0
Budget Management ServiceとPinotは疎結合なのでPrestoやSpark SQLなどのクエリエンジンにDP機能を統合することも可能
8.3 Rationale for Parameters in our Privacy System
ε
30日間データセットはリテンションされ、分析者は毎日同じクエリを実行すると想定すると（毎日seedを変える仕組みなので）同じカウントに対し30の異なるノイズを得る
seedはクエリとデータベースに依存して決定し、データベースは1日単位で更新していくため
これらのノイズの平均が1/2より小さくなる確率を求める
分析者がもっとも近い整数に丸めて本来の値を復元できてしまうので。（ノイズはintegerでない）
https://gyazo.com/e68aaa94668efe5dc16369dcb4ff7103
この攻撃確率が11%程度である場合、$ ε_{per}=0.15
Information Budget
ノイズが小さいことによる差分攻撃はノイズが一つのcountに対し1/2より小さい場合に起こりうる
https://gyazo.com/373076065c48e2ce04e05e79b899a9f3
top-k queryで半数が真の値であるpk個(0 <= p <= 1)のノイズカウントを得る
差分攻撃のために新たにpk個のノイズカウントを得るが、半数が真の値である２つのノイズクエリ結果のうちどの要素が真の値であるかは攻撃者はわからない。
top-k クエリにより要素はオーバーラップできないように設定する必要
最初のtop-kクエリの真の値（半数のノイズを加えない要素）を固定し、次のtop-kクエリをランダムにした時、要素が交差する確率は、交差要素数をsとして、超幾何分布に従い、期待値は $ p^2k https://gyazo.com/5fdfc6d7b15e23b3ddbfaabbcd0762e3
この期待値が1以下であって欲しいので、 $ k < 1/p^2
ε=0.15からp=0.0368が得られ、k=738
...
k* = 3000/month (93%の分析者に影響はない）
Appendix
PripeARL
unrestricted sensitivityでは（ユーザーは任意のグループに貢献できるため）privscy lossに上限をつけるため固定数kまでの合計値セットしかレスポンスしない
user contributionをboundするためにdatasetに対してpre-processingがあるのでオーバーヘッド高い
unkGumbアルゴリズムはpre-processingなしにuser-levelプライバシーを保証
pay-what-you get privacy composition bound
top-kグループのクエリ時にkグループより少ないかもしれないが、privacy lossが出力セット分で抑えられる