You are looking at a specific version 20140214:133427 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.