On the Complexity of Two-Party Differential Privacy
summary
Shows that any two-party computational differential privacy protocol that computes inner product (or Hamming distance) with accuracy better than the trivial Θ(√n) noise yields a key-agreement protocol, so public-key primitives (beyond one-way functions) are necessary to bypass the McGregor et al. barrier. Uses reductions from two-party CDP to correlated outputs, a constructive reconstruction algorithm and a new seed-dependent condenser for strong Santha–Vazirani sources giving ~√n/log n min-entropy; the constructions are explicit and yield the claimed implication.
AI-written summary · about
chapters (8)
- 0:00Introduction to DP
- 3:02Two-party protocols
- 10:22Computational DP
- 13:09Complexity and assumptions
- 20:00Core results and theorems
- 22:22Information-theoretic proof
- 26:56Protocol construction
- 34:06Conclusion and future work
related talks
01h 10mDifferential Privacy: Fundamentals to Forefront II
01h 10mSecure Multiparty Computation II
20mShare data without revealing personal information
20mDesigning for User Privacy: Integrating Differential Privacy into Ad Measurement...
58mSecure Multiparty Computation I
01h 00mSecure Computation 3
34mThe Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and...
34mEfficient Robust Private Aggregation for DP