Paper 2013/808

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

Michael Backes, Aniket Kate, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. 13th International Conference on Applied Cryptography and Network Security (ACNS 2015)
Keywords
indistinguishabilityrandomnessweak sourcesdifferential privacypseudorandom generatorsSantha-Vazirani sources
Contact author(s)
meiser @ cs 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

BibTeX

@misc{cryptoeprint:2013/808,
      author = {Michael Backes and Aniket Kate and Sebastian Meiser and Tim Ruffing},
      title = {Secrecy without Perfect Randomness: Cryptography with (Bounded) Weak Sources},
      howpublished = {Cryptology ePrint Archive, Paper 2013/808},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/808}},
      url = {https://eprint.iacr.org/2013/808}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.