Uniformity Testing in the Shuffle Model: Simpler, Better, Faster
This work is incremental, offering a more straightforward approach to a known problem in privacy-preserving distribution testing.
The paper tackled uniformity testing under privacy constraints in the shuffle model by simplifying the analysis of an existing algorithm and providing an alternative with the same guarantees using privacy amplification via shuffling.
Uniformity testing, or testing whether independent observations are uniformly distributed, is the prototypical question in distribution testing. Over the past years, a line of work has been focusing on uniformity testing under privacy constraints on the data, and obtained private and data-efficient algorithms under various privacy models such as central differential privacy (DP), local privacy (LDP), pan-privacy, and, very recently, the shuffle model of differential privacy. In this work, we considerably simplify the analysis of the known uniformity testing algorithm in the shuffle model, and, using a recent result on "privacy amplification via shuffling," provide an alternative algorithm attaining the same guarantees with an elementary and streamlined argument.