This paper establishes communication lower bounds for privately computing U-statistics in MPC frameworks, proving that any MPC protocol computing a U-statistic of degree k over parties while satisfying (ε, δ)-differential privacy requires Ω(n2) bits of communication. The study introduces an information-theoretic framework combining techniques from communication complexity, secure computation theory, and differential privacy.
Key findings
Proves Ω(n2) communication lower bounds for degree-k U-statistics under (ε, δ)-DP in MPC.
Demonstrates a degree-dependent hierarchy, with higher-degree U-statistics requiring more communication.
Quantifies the impact of privacy parameters on communication requirements.
Presents a sampling-based protocol for degree-2 U-statistics nearly matching the lower bounds.
Limitations & open questions
The study focuses on communication lower bounds and does not extensively explore optimization techniques for practical MPC implementations.