テクニカル・サマリー: DP4SQL - 柔軟なプライバシー・ポリシーを備えた差分プライベートSQL

問題提起

差分プライバシー（DP）は単一テーブルのデータセットに対しては確立されているが、リレーショナルデータベースへの適用は、複数のリレーションにわたる「もっともらしい否認（plausible deniability）」の定義の複雑さゆえに依然として困難である。既存の差分プライベートSQLシステムは、硬直的でハードコードされたプライバシーモデルに起因する課題を抱えている。

現在のシステムの主な限界は以下の通りである：

1. 不柔軟なポリシー: 異なるテーブル、あるいは同一テーブル内の異なるカラムに対して、異なるレベルの保護（例：あるテーブルではレコードの存在を保護し、別のテーブルでは属性値のみを保護するなど）を必要とするシナリオに対応できない。
2. 公開知識の統合: 公開情報（例：既知のテーブルサイズや、教授名のような公開されているカラムの値）をプライバシー計算に組み込むことが困難である。公開知識を無視することは、過剰な保護（過度なノイズの注入）や、逆に過小な保護（テーブルサイズが既知である場合にレコードの存在を隠蔽できないことによる）を招く。
3. 複雑なエンティティ間の相互作用: 既存のモデルは、外部キーや推移的な所有関係を正しく扱うことができない場合が多い（例：教授が学生に成績を割り当てる場合など）。これは、不正確な感度計算につながり、結果として、不十分なノイズ（プライバシー侵害）または過剰なノイズ（ユーティリティの喪失）を引き起こす。

メソドロジー

本論文は、高レベルのプライバシー・ポリシーの仕様策定と、低レベルの自動推論を分離するシステムである DP4SQL を提案している。その手法は、主に3つのコンポーネントで構成される。

1. 高レベル・プライバシー・ラベリング・フレームワーク

データ管理者は、スキーマ内の各リレーションに対して、単純な高レベル・ラベリング・システムを用いてポリシーを指定する。特定のエンティティ・リレーション $R^\star$（例：学生や教授）に対し、各リレーション $R_i$ には以下の3つのラベルのいずれかが割り当てられる：

• DEL (Delete/削除): レコードの存在がプライベートである。反事実的な世界は、レコードを削除することによって作成される。これは非有界な隣接関係（unbounded neighbors）に対応する。
• REPA (Replace/置換): レコードの存在は公開されているが、特定の属性 $A$ はプライベートである。反事実的な世界は、属性 $A$ の値を置き換えることによって作成される。これは有界な隣近関係（bounded neighbors）に対応する。
• PUB (Public/公開): リレーション全体が公開されている。

このフレームワークにより、学生の存在は保護（DEL）しつつ、教授名は公開（PUB）し、教授の給与はプライベート（REPA）にする、といった混合ポリシーが可能になる。

2. 低レベル・プラウジブル・デナイアビリティ・アクション

自動推論を行うため、システムは高レベルのラベルを、隣接するデータベース間でクエリ結果が最大でどのように変化するかを記述する一連の プラウジブル・デナイアビリティ・アクション（もっともらしい否認アクション） に変換する。アクションは以下の通りである：

• Add$_a$ / Del$_d$: $a$ 個または $d$ 個の行の追加、あるいは削除。
• Rep$^A_k$: $k$ 個の行における属性 $A$ の値の置換。

システムは、以下の要素を含む複雑なSQLクエリに対して、プロダクション・ルールを用いた 推論システム を用いてこれらのアクションを導出する：

• 基本リレーション: プライバシー・ラベルを初期アクションにマッピングする際、外部キー制約から導出された最大所有量（$\hat{\otimes}$）を考慮する。
• 単項変換: 述語（predicate）やグルーピング・キーが保護された属性と交差するかどうかに基づいて、アクションを伝播させるための選択（$\sigma$）、射影（$\pi$）、および集計（$\gamma$）のルール。
• 結合（Join）: システムは、キー・ジョイン（主キーと外部キーのペアに基づく結合）と 一般結合 を区別する。キー・ジョインは整合性制約を活用して、レコードの変化に関するよりタイトな境界を導出し、一般的な結合ルールで見られる過剰な近似を回避する。

3. 感度計算とノイズ注入

推論されたアクションは、グローバル感度（$\hat{\Delta}$）の上限にマッピングされる。この上限は、ラプラス・メカニズムを通じて注入されるノイズのスケールを決定する。システムは、集計関数（COUNT, SUM）の感度を計算するために、推論されたアクション（追加、削除、置換）が出力ベクトルにどのように影響するかを分析する。

主な貢献

1. 柔軟なポリシー指定: 外部キーを持つリレーショナル・スキーマにおいて、混合プライバシー要件（公開サイズ、公開カラム、プライベート属性）をサポートする、高レベルのカラム・ラベリング・フレームワーク。
2. 自動推論エンジン: 高レベルのラベルを低レベルのプラウブル・デナイアビリティ・アクションへと変換し、リレーショナル代数クエリ（結合、集計、サブクエリ）の安定性を正当に推論する形式的な推論システム。
3. よりタイトな感度境界: 公開知識（例：既知のテーブルサイズ）を明示的にモデル化し、キー・ジョイン専用のルールを使用することで、DP4SQLは、すべての属性に対して最悪のシナリオを想定しがちな既存システムよりもタイトな感度境界を導出する。
4. 実装と検証: システムはデータベース・ミドルウェア（DP4SQL）として実装されており、SQLクエリをインターセプトし、必要なノイズを計算して、差分プライベートな回答を返す。

結果

本論文では、大学のスキーマのケーススタディとTPC-Hベンチマークを用いて、DP4SQLをベースライン・ポリシー（純粋な非有界および純粋な有界な隣接関係）および、PrivateSQLに基づくTumult Analyticsシステムと比較評価している。

• プライバシーの正確性（過小保護）: テーブルサイズが公開されているシナリオ（例：TPC-Hにおけるオーダー数）において、ベースラインの非有界モデル（Tumultなど）は、レコードの存在がプライベートであると誤って想定する。これは、サイズが既知である場合には「削除」ではなく「置換」が妥当な反事実的動作であるにもかかわらず、それを考慮していないために、過小保護（不十分なノイズ）を招く。DP4SQLはこれらのケースを正しく識別し、適切なノイズを適用する。
• ユーティリティの向上（過剰保護）: ベースライン・モデルは多くの場合、すべての属性をプライベートとして扱うため、過剰保護（過度なノイズ）を招く。例えば、大学のケーススタディにおいて、公開されているレビュー・スコアや教授名に関するクエリは、DP4SQLの柔軟なポリシー下では感度がゼロであったが、ベースラインは有意なノイズを注入した。TPC-Hにおいては、DP4SQLは公開情報（例：サプライヤー数）を返すクエリに対してゼロの感度を実現したが、ベースラインは結果が使用不能になるほどのノイズ（相対誤差 > 100%）を注入した。
• 精度: ベースラインが過剰保護を行ったケースにおいて、DP4SQLは大幅に低い相対誤差を示した（例：特定のTPC-Hクエリにおいて、ベースラインよりも大幅に低い誤差を達成）。

意義と主張

本論文は、DP4SQLが現在のDP SQLシステムにおける「ワンサイズ・フィッツ・オール（画一的）」な制限に対処していると主張している。データ・キュレーターが「もっともらしい否認」の要件をカスタマイズできるようにすることで、システムはプライバシー侵害（過小保護によるもの）とデータ・ユーティリティの損失（過剰保護によるもの）の間のトレードオフを回避できる。

著者らは、そのアプローチが**健全（sound）**であることを強調している。すなわち、推論システムがグローバル感度の上限を正しく導出し、結果として生成されるメカニズムが $(PS, R^\star, \epsilon)$-差分プライバシーを満たすことを示す形式的な証明を提供している。本研究は、正しいプライバシー・モデリング（特に、公開されたテーブルサイズ、公開されたカラム、およびきめ細かな属性保護について推論する能力）が、複雑な複数テーブルのリレーショナル環境において差分プライバシーをデプロイするために不可欠であることを浮き彫りにしている。