2007 | OriginalPaper | Buchkapitel
Does Privacy Require True Randomness?
verfasst von : Carl Bosley, Yevgeniy Dodis
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness?
We completely resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a
b
-bit value using a shared secret key sampled from some imperfect source of randomness
. Our main result shows that if such
n
-bit source
allows for a secure encryption of
b
bits, where
b
> log
n
, then one can deterministically extract nearly
b
almost perfect random bits from
. Further, the restriction that
b
> log
n
is nearly tight: there exist sources
allowing one to perfectly encrypt (log
n
− loglog
n
) bits, but not to deterministically extract even a single slightly unbiased bit.
Hence, to a large extent,
true randomness is inherent for encryption
: either the key length must be exponential in the message length
b
, or one can deterministically extract nearly
b
almost unbiased random bits from the key. In particular,
the one-time pad scheme is essentially “universal”
.
Our technique also extends to related
computational
primitives which are
perfectly-binding
, such as perfectly-binding commitment and computationally secure private- or public-key encryption, showing the necessity to
efficiently
extract almost
b
pseudorandom
bits.