IACR News item: 23 April 2015
Yanqing Yao, Zhoujun Li
ePrint Report(i.e., less structured) sources than SV source. A new source, called
Bias-Control Limited (BCL) source, introduced by Dodis (ICALP\'01),
as a generalization of the SV source and sequential bit-fixing source, is
more realistic. Unfortunately, if we nationally expand SV-consistent sampling to the BCL source, the expansion is hopeless to achieve differential privacy. One main reason is that SV-consistent sampling requires \"consecutive\"strings, while some strings can\'t be generated from \"non-trivial\"BCL source.
Motivated by this question, we introduce a new appealing property, called
compact BCL-consistent sampling, the degeneration of which is different
from SV-consistent sampling proposed by Dodis et al. 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 accuracy. While the results of [DY14]imply that if there exist differentially private mechanisms for imperfect randomness, then some parameters should have some constraints, ours show explicit construction of such mechanisms whose parameters match
the prior constraints.
Additional news items may be found on the IACR news page.