Exponential Separations in Local Differential Privacy
This work addresses fundamental limitations in privacy-preserving data analysis for researchers and practitioners, providing rigorous lower bounds that are not incremental but foundational in nature.
The paper tackles the problem of understanding sample complexity in locally differentially private protocols by establishing a connection to communication complexity, resulting in exponential separations between sequentially and fully interactive protocols, and between k-round and (k+1)-round sequentially interactive protocols.
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from communication complexity. In particular, we 1) use a communication lower bound for the hidden layers problem to prove an exponential sample complexity separation between sequentially and fully interactive locally private protocols, and 2) use a communication lower bound for the pointer chasing problem to prove an exponential sample complexity separation between $k$ round and $k+1$ round sequentially interactive locally private protocols, for every $k$.