International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 06 December 2013

Michael Backes, Aniket Kate, Sebastian Meiser, Tim Ruffing
ePrint Report 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.

Expand

Additional news items may be found on the IACR news page.