  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 $(\epsilon,
\delta)$ DP learners with training data drawn from any arbitrary compact metric
space, we provide the \emph{first known lower bounds on the adversary's query
complexity} as a function of the learner's privacy parameters. \emph{Our
results are minimax optimal for every $\epsilon \geq 0, \delta \in [0, 1]$,
covering both $\epsilon$-DP and $(0, \delta)$ DP as corollaries}. Beyond this,
we obtain query complexity lower bounds for $(\alpha, \epsilon)$ R\'enyi DP
learners that are valid for any $\alpha > 1, \epsilon \geq 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.
