Private Query Release via the Johnson-Lindenstrauss Transform

Understand

We introduce a new method for releasing answers to statistical queries with differential privacy, based on the Johnson-Lindenstrauss lemma.

• The key idea is to randomly project the query answers to a lower dimensional space so that the distance between any two vectors of feasible query answers is preserved up to an additive error.
• Then we answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension.
• Using this method, we give, for the first time, purely differentially private mechanisms with optimal worst case sample complexity under average error for answering a workload of $k$ queries over a universe of size $N$.