Lossless Compression of Efficient Private Local Randomizers
This addresses communication bottlenecks in federated learning and statistics collection for privacy-preserving systems, offering a significant improvement over prior methods that sacrificed utility.
The paper tackles the problem of high communication costs in locally differentially private (LDP) algorithms by introducing a general compression method that reduces message sizes to the seed size of a pseudo-random generator, with negligible loss in privacy and utility. It demonstrates this with simpler and more accurate algorithms for frequency and high-dimensional mean estimation.
Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server (such as when constructing histograms over large domain or learning a high-dimensional model). This has led to significant efforts on reducing the communication cost of LDP algorithms. At the same time LDP reports are known to have relatively little information about the user's data due to randomization. Several schemes are known that exploit this fact to design low-communication versions of LDP algorithm but all of them do so at the expense of a significant loss in utility. Here we demonstrate a general approach that, under standard cryptographic assumptions, compresses every efficient LDP algorithm with negligible loss in privacy and utility guarantees. The practical implication of our result is that in typical applications the message can be compressed to the size of the server's pseudo-random generator seed. More generally, we relate the properties of an LDP randomizer to the power of a pseudo-random generator that suffices for compressing the LDP randomizer. From this general approach we derive low-communication algorithms for the problems of frequency estimation and high-dimensional mean estimation. Our algorithms are simpler and more accurate than existing low-communication LDP algorithms for these well-studied problems.