Paper 2015/360

Achieving Differential Privacy with Bias-Control Limited Source

Yanqing Yao and Zhoujun Li

Abstract

In the design of differentially private mechanisms, it’s usually assumed that a uniformly random source is available. However, in many situations it seems unrealistic, and one must deal with various imperfect random sources. Dodis et al. (CRYPTO’12) presented that differential privacy can be achieved with Santha-Vazirani (SV) source via adding a stronger property called SV-consistent sampling and left open question if differential privacy is possible with more realistic (i.e., less structured) sources. A new source, called Bias-Control Limited (BCL) source, introduced by Dodis (ICALP’01), is more realistic. It can be considered as a generalization of the SV and sequential bit-fixing sources. Unfortunately, the natural extension of SV-consistent sampling to the BCL source is hopeless to achieve differential privacy, mainly because SV-consistent sampling requires “consecutive” strings, while some strings can’t be generated from “non-trivial” BCL source. Motivated by this problem, we introduce a new appealing property, called compact BCL-consistent sampling, the degeneration of which is different from SV-consistent sampling shown by Dodis et al. (CRYPTO’12). We prove that if the mechanism based on the BCL source satisfies this property, then it’s differentially private. Even if the BCL source is degenerated into the SV-source, our proof is much more intuitive and simpler than that of Dodis et al. Further, we construct explicit mechanisms using a new truncation technique as well as arithmetic coding. We also propose its concrete results for differential privacy and utility. While the results of Dodis and Yao (CRYPTO’15) imply that if there exist differentially private mechanisms for imperfect randomness, then the parameters should have some constraints, we show an explicit construction of such mechanisms, whose parameters match the prior constraints.