On the Query Complexity of Training Data Reconstruction in Private Learning

Authors: Prateeti Mukherjee, Satya Lokam
Published: 2023-03-29 | Updated: 2024-01-11

Source: https://arxiv.org/abs/2303.16372

PDF: https://arxiv.org/pdf/2303.16372

AIにより推定されたラベル

プライバシー保護手法 プライバシー評価 プライバシー分析

※ こちらのラベルはAIによって自動的に追加されました。そのため、正確でないことがあります。
詳細は文献データベースについてをご覧ください。

Abstract

We analyze the number of queries that a whitebox adversary needs to make to a private learner in order to reconstruct its training data. For (ϵ, δ) DP learners with training data drawn from any arbitrary compact metric space, we provide the first known lower bounds on the adversary’s query complexity as a function of the learner’s privacy parameters. Our results are minimax optimal for every ϵ ≥ 0, δ ∈ [0, 1], covering both ϵ-DP and (0, δ) DP as corollaries. Beyond this, we obtain query complexity lower bounds for (α, ϵ) Rényi DP learners that are valid for any α > 1, ϵ ≥ 0. Finally, we analyze data reconstruction attacks on locally compact metric spaces via the framework of Metric DP, a generalization of DP that accounts for the underlying metric structure of the data. In this setting, we provide the first known analysis of data reconstruction in unbounded, high dimensional spaces and obtain query complexity lower bounds that are nearly tight modulo logarithmic factors.