Privacy with imperfect randomness

Yevgeniy Dodis, Yanqing Yao

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90, DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Somewhat surprisingly, Dodis et al. [DLMV12] showed that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question of whether differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by this question, we introduce a new, modular framework for showing strong impossibility results for (both traditional and differential) privacy under ageneral imperfect source R. As direct corollaries of our framework, we get the following new results: (1) Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R.(2) First impossibility results for differential privacy for a variety of realistic sources R (including most “block sources”, but not the SV source). (3) Any imperfect source allowing (either traditional or differential) privacy under R admits a certain type of deterministic bit extraction from R.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783662479995
StatePublished - 2015
Event35th Annual Cryptology Conference, CRYPTO 2015 - Santa Barbara, United States
Duration: Aug 16 2015Aug 20 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other35th Annual Cryptology Conference, CRYPTO 2015
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Privacy with imperfect randomness'. Together they form a unique fingerprint.

Cite this