Private Query Release via the Johnson-Lindenstrauss Transform. (arXiv:2208.07410v1 [cs.DS])

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 …

arxiv query release