Paper 2013/808
Differential Indistinguishability for Cryptography with (Bounded) Weak Sources
Michael Backes and Aniket Kate and Sebastian Meiser and Tim Ruffing
Abstract
Indistinguishability-based definitions of cryptographic primitives such as encryption, commitments, and zero-knowledge proofs are proven to be impossible to realize in scenarios where parties have access only to weak sources of randomness (Dodis et al., FOCS 2004). In this work we demonstrate that it is, nevertheless, possible to quantify this secrecy loss for (bounded) weak sources such as the well-studied Santha-Vazirani (SV) sources. To establish meaningful security guarantees in scenarios where such bounded weak sources are used, we define and study differential indistinguishability, a generalization of indistinguishability inspired by the notion of differential privacy. We analyze strengths and weaknesses of differential indistinguishability both individually as well as under composition, and we interpret the resulting differential security guarantees for encryption and zero-knowledge proofs. Surprisingly, indistinguishability with uniform randomness carries over to differential indistinguishability with bounded weak sources: We show that all primitives that are secure under a traditional indistinguishability-based definition are differentially secure when they use (a limited amount of) bounded weak randomness instead of uniform randomness.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Differential PrivacyIndistinguishabilityRandomnessWeak SourcesSantha-Vazirani Sources
- Contact author(s)
-
meiser @ cs uni-saarland de
aniket @ mmci uni-saarland de
tim ruffing @ stud uni-saarland de - History
- 2015-04-02: last of 4 revisions
- 2013-12-06: received
- See all versions
- Short URL
- https://ia.cr/2013/808
- License
-
CC BY