5 papers
Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
Jacob Imola, Rasmus Pagh, Lukas Retschmeier
This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w}…
Privacy by Postprocessing the Discrete Laplace Mechanism
Quentin Hillebrand, Jacob Imola, Rasmus Pagh +1
We show that an "old dog", the classical discrete Laplace (aka.~geometric) mechanism, can "perform new tricks": 1. It can be post-processed to yield a simple, unbiased estimator of…
Piquant: Private Quantile Estimation in the Two-Server Model
Hannah Keller, Jacob Imola, Fabrizio Boninsegna +2
Quantiles are key in distributed analytics, but computing them over sensitive data risks privacy. Local differential privacy (LDP) offers strong protection but lower accuracy than…
Differentially Private Quantiles with Smaller Error
Jacob Imola, Fabrizio Boninsegna, Hannah Keller +3
In the approximate quantiles problem, the goal is to output quantile estimates, the ranks of which are as close as possible to given quantiles $0 \leq q_1 \leq\dots \leq q_…
Lightweight Protocols for Distributed Private Quantile Estimation
Anders Aamand, Fabrizio Boninsegna, Abigail Gentle +2
Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We co…