Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Differential Privacy, Indistinguishability, Randomness, Weak Sources, Santha-Vazirani Sources

Date: received 2 Dec 2013, last revised 14 Feb 2014

Contact author: meiser at cs uni-saarland de, aniket@mmci uni-saarland de, tim ruffing@stud uni-saarland de

Available format(s): PDF | BibTeX Citation

Version: 20140214:133427 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]