Abstract
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 > logn, then one can deterministically extract nearly b almost perfect random bits from . Further, the restriction that b > logn is nearly tight: there exist sources allowing one to perfectly encrypt (logn − loglogn) 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andreev, A., Clementi, A., Rolim, J., Trevisan, L.: Dispersers, deterministic amplification, and weak random sources. SIAM J. on Computing 28(6), 2103–2116 (1999)
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. on Computing 17(2), 230–261 (1988)
Dodis, Y.: Exposure-Resilient Cryptography (PhD Thesis). MIT PhD Thesis (2000)
Dodis, Y., Ong, S.J., Prabhakaran, M., Sahai, A.: On the (im)possibility of cryptography with imperfect randomness. In: Proc. 45th IEEE FOCS, pp. 196–205. IEEE Computer Society Press, Los Alamitos (2004)
Dodis, Y., Pietrzak, K., Przydatek, B.: Separating Sources for Encryption and Secret-Sharing. In: Proc. Theory of Cryptography Conference (TCC), pp. 601–616 (2006)
Dodis, Y., Spencer, J.: On the (non-)universality of the one-time pad. In: Proc. 43rd IEEE FOCS, pp. 376–388. IEEE Computer Society Press, Los Alamitos (2002)
Dodis, Y., Sahai, A., Smith, A.: On perfect and adaptive security in exposure-resilient cryptography. In: Proc. EUROCRYPT’01, pp. 301–324 (2001)
Goldreich, O., Levin, L.: A Hard-Core Predicate for all One-Way Functions. In: Prof. STOC, pp. 25–32 (1989)
Kamp, J., Rao, A., Vadhan, S., Zuckerman, D.: Deterministic extractors for small-space sources. In: Proc. of STOC 2006, pp. 691–700 (2006)
McInnes, J.L., Pinkas, B.: On the impossibility of private key cryptography with weakly random keys. In: Proc. CRYPTO’90, pp. 421–436 (1990)
Maurer, U., Wolf, S.: Privacy amplification secure against active adversaries. In: Proc. CRYPTO’97, pp. 307–321 (1997)
Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Proc. of CRYPTO, pp. 129–140 (1991)
Renner, R., Wolf, S.: Unconditional authenticity and privacy from an arbitrary weak secret. In: Proc. CRYPTO’03, pp. 78–95 (2003)
Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. JCSS 33(1), 75–87 (1986)
Shannon, C.: Communication Theory of Secrecy systems. Bell Systems Technical J. 28, 656–715 (1949)
Strang, G.: Linear Algebra and Its Applications. Academic Press, London (1980)
Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: Proc. 41st IEEE FOCS, pp. 32–42. IEEE Computer Society Press, Los Alamitos (2000)
von Neumann, J.: Various techniques used in connection with random digits. National Bureau of Standards, Applied Mathematics Series 12, 36–38 (1951)
Vazirani, U.V., Vazirani, V.V.: Random polynomial time is equal to slightly-random polynomial time. In: Proc. 26th IEEE FOCS, pp. 417–428. IEEE Computer Society Press, Los Alamitos (1985)
Zuckerman, D.: Simulating BPP using a general weak random source. Algorithmica 16(4/5), 367–391 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Bosley, C., Dodis, Y. (2007). Does Privacy Require True Randomness?. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)