IACR News item: 06 December 2013
Michael Backes, Aniket Kate, Sebastian Meiser, Tim Ruffing
ePrint Report
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 only have access to non-extractable sources of randomness (Dodis et al., FOCS 2004). In this work we demonstrate that it is, nevertheless, possible to quantify this secrecy loss for non-extractable sources such as the (well-studied) Santha-Vazirani (SV) sources. In particular, to establish meaningful security guarantees in scenarios where such imperfect randomness 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, commitments, and zero-knowledge proofs.
Surprisingly, indistinguishability with uniform randomness carries over to differential indistinguishability with SV randomness: We show that all primitives that are secure under a traditional indistinguishibility-based definition are differentially secure when they use (a bounded amount of) SV randomness instead of uniform randomness.
Additional news items may be found on the IACR news page.