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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
differential privacyimperfect randomnessBias-Control Limited sourceconsistent samplingtruncation technique
Contact author(s)
yaoyanqing1984 @ gmail com
yaoyanqing1984 @ buaa edu cn
lizj @ buaa edu cn
History
2015-10-08: last of 2 revisions
2015-04-23: received
See all versions
Short URL
https://ia.cr/2015/360
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/360,
      author = {Yanqing Yao and Zhoujun Li},
      title = {Achieving Differential Privacy with Bias-Control Limited Source},
      howpublished = {Cryptology ePrint Archive, Paper 2015/360},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/360}},
      url = {https://eprint.iacr.org/2015/360}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.