TY - GEN
T1 - Privacy with imperfect randomness
AU - Dodis, Yevgeniy
AU - Yao, Yanqing
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84959339319&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959339319&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48000-7_23
DO - 10.1007/978-3-662-48000-7_23
M3 - Conference contribution
AN - SCOPUS:84959339319
SN - 9783662479995
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 463
EP - 482
BT - Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings
PB - Springer Verlag
T2 - 35th Annual Cryptology Conference, CRYPTO 2015
Y2 - 16 August 2015 through 20 August 2015
ER -