Differential Privacy in the Real World: Imperfect Randomness and Floating-Point Arithmetic
Ilya Mironov
Abstract:
Differential privacy, introduced by Dwork et al in 2006, has become a de facto standard for definition of privacy for aggregate computations over sensitive data. In this talk we consider two challenges in implementing differential privacy that remarkably result in very similar procedures for evaluating one basic differentially-private mechanism.
The first challenge is implementing differential privacy with access only to a single imperfect source of randomness. It has been shown that information-theoretic private-key encryption is impossible unless the source of randomness is extractable (Bosley and Dodis, TCC'07). Somewhat surprisingly, we show that the answer is reversed if the target notion of security is differential privacy. We prove that an accurate and differentially-private approximation to the Laplacian mechanism is feasible even if the only source of randomness accessible to the mechanism is semi-random (Santha-Vazirani).
Another problem area confronting implementations of differential privacy in the real world is floating-point arithmetic. We demonstrate that all four publicly available general-purpose systems for differential privacy are vulnerable to the same attack exploiting the gap between mathematical abstractions and their implementations. We also discuss a fix to the problem, which coincides with the mechanism robust to imperfect randomness.
The talk is going to be self-contained, with all important concepts and definitions introduced and developed as needed. The first part of the talk is based on the joint work (to appear at CRYPTO'12) by Yevgeniy Dodis, Adriana Lopez-Alt (both - NYU), and Salil Vadhan (Harvard, Stanford, and MSR).