擬似ランダムスケッチによるプライバシー

プライベートデータを持ち、第三者と共有したくない個人の集まりを想像してください。本稿では、個人が自分のデータをどのように表現し、公開することでプライバシーを保ちながら、元の非摂動データから大規模な統計的振る舞いを抽出できるかを考察します。データを摂動させる既存の技術は、クエリへの近似解を得るために必要なユーザーの数、保存された統計的振る舞いの豊かさ、与えられるプライバシー保証、及び各個人が公開しなければならないデータの量によって制約されています。本稿では、擬似ランダムスケッチに基づいて個人のデータの一部を記述する新しい技術を紹介します。このスケッチは、無限の計算能力と任意の部分的知識を持つ攻撃者が、公開されたスケッチから追加のプライベート情報を学習できないことを前提に、各個人のプライバシーが証明可能に維持されることを保証します。しかし、複数のユーザーからのスケッチが属性のサブセットを説明する場合、全属性の否定または非否定にわたる結合を満たすユーザーの割合を推定するために使用できます。近似誤差は関与する属性の数に依存せず、利用可能なユーザーの数のみに依存することを示します。追加の利点として、スケッチのサイズは極めて小さく、O (M)ビットで、Mはユーザーの数です。最後に、スケッチを組み合わせてより複雑なクエリに応える方法を示します。