Loading...
Please wait, while we are loading the content...
Similar Documents
Privacy with Imperfect Randomness
| Content Provider | CiteSeerX |
|---|---|
| Author | Dodisa, Yevgeniy Yaob, Yanqing |
| Abstract | Abstract. We revisit the impossibility of a variety of cryptographic tasks including privacy and differ-ential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryp-tion, 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. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable ” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured ” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing 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 if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong im-possibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Imperfect Randomness Differential Privacy Sv Source Extractable Source Easy-to-understand Concept Friendly Santha-vazirani Strong Im-possibility Result Structured Imperfect Source Traditional Notion Dramatic Impossibility Result Negative Result Non-trivial Differential Privacy Qualitative Gap Secret Sharing Scheme Common Interpretation Cryptographic Task Several Concrete Source Dodis Bd07 Modular Framework Imperfect Source Differ-ential Privacy General Imperfect Source Many Traditional Privacy Task Slight Dent Strong Evidence Following Result |
| Content Type | Text |
| Resource Type | Article |
