Cryptology ePrint Archive: Report 2013/808

Secrecy without Perfect Randomness: Cryptography with (Bounded) Weak Sources

Michael Backes and Aniket Kate and Sebastian Meiser and Tim Ruffing

Abstract: Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources.

In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirna (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion differential indistinguishability in order to reflect its structural similarity to differential privacy. More concretely, we prove that indistinguishability with uniform randomness implies differential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve differential indistinguishability.

Category / Keywords: foundations / indistinguishability, randomness, weak sources, differential privacy, pseudorandom generators, Santha-Vazirani sources

Original Publication (with minor differences): 13th International Conference on Applied Cryptography and Network Security (ACNS 2015)

Date: received 2 Dec 2013, last revised 2 Apr 2015

Contact author: meiser at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Version: 20150402:152102 (All versions of this report)

Short URL: ia.cr/2013/808

Discussion forum: Show discussion | Start new discussion