The Power of Input Perturbation for Data Privacy

PhD defence by Lukas Retschmeier

Assessment Committee

Associate professor Mikkel Vind Abrahamsen, Computer Science, University of Copenhagen (Chairperson)
Professor Inge Li Gørtz, Technical University of Denmark
Professor Haim Kaplan, Tel-Aviv University

Supervisors

Professor Rasmus Pagh

Associate Professor Martin Aunmüller

Department

Department of Computer Science

Place

The defence is conducted as a hybrid defence.

To attend the defence in person:
Building: Datalogisk Institut - DIKU, Room: Store UP1,
Universitetsparken 1, 2100 Købenvhavn Ø

To attend the defence online:
Please follow the link to attend the defence online: https://ucph-ku.zoom.us/j/2311505430?omn=67892620817
MeetingID, if relevant: 678 9262 0817

Address to gain access to the thesis: https://www.lukasretschmeier.de/phd-thesis.pdf 
You will either receive a copy of the thesis or be informed where you can read a physical copy.
Recipients of copies of the thesis are not allowed to share or distribute it due to copyright compliance.

Short description of the thesis

We investigate when perturbing sensitive inputs before applying classical algorithms yields optimal privacy-utility trade-offs and develop both algorithmic and lower-bound techniques for answering this question.
For the problem of releasing a minimum spanning tree (MST) under the ℓ∞-neighboring relation, we show that a simple input-perturbation achieves asymptotically optimal accuracy while matching the running time of any non-private algorithm.
Furthermore, we develop reconstruction-based lower-bound techniques proving optimality for minimum spanning trees, minimum-weight perfect matchings, and hierarchical clustering under various privacy models.
Beyond graphs, the thesis investigates perturbation-based privacy through lossless releases at multiple privacy levels and improved sparse Gaussian histograms using correlated noise.