類似検索の結果の開示におけるプライバシ保護のためのクエリ監査法

摘要

本論文ではプライベート情報を含むデータベースに対する類似検索において，データベースの応答がプライバシ保護要件を満たしているかを判定する（クエリ監査）手法を提案する．データベースは任意の複数クエリレコードそれぞれに対し類似するレコードのID集合を返すとする．我々はこのようなクエリ監査を定式化し，プライバシ基準としてデータベースのプライベート情報が推定される確率を導入した．さらにプライバシ基準の計算を数え上げ問題として記述し監査を高速かつ正確に行うアルゴリズムを導入した．実データを用いた実験で本手法の計算効率及び監査結果の検証を行った．