Abstract
The properties of weak sources of randomness have been investigated in many contexts and using several models of weakly random behaviour. For two such models, developed by Santha and Vazirani, and Chor and Goldreich, it is known that the output from one such source cannot be “compressed” to produce nearly random bits. At the same time, however, a single source is sufficient to solve problems in the randomized complexity classes BPP and RP. It is natural to ask exactly which tasks can be done using a single, weak source of randomness and which cannot. The present work begins to answer this question by establishing that a single weakly random source of either model cannot be used to obtain a secure “one-time-pad” type of cryptosystem.
Research supported in part by US-Israel BSF grant 88-00282.
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
M. Blum, “Independent unbiased coin flips from a correlated biased source: A finite state Markov chain”, 25th IEEE Sympos. Found. of Comput. Sci., pp. 425–433. 1984.
B. Chor and O. Goldreich. “Unbiased bits from weak sources of randomness and probabilistic communication complexity”, SIAM J. Comput., Vol. 17, No. 2, pp. 230–261. April 1988.
J. L. McInnes, “Cryptography using weak sources of randomness”, Technical Report 194/87, Dept. of Computer Science, University of Toronto. 1987.
J. von Neumann, “Various techniques used in connection with random digits” (notes by G. E. Forsythe), Applied Math Series, Vol. 12, pp. 36–38, 1951; National Bureau of Standards, Washington D.C., reprinted in “Collected Works”, Vol. 5, pp. 768–770, Pergamon, New York, 1963.
C. E. Shannon, “Communication theory of secrecy systems”, Bell Sys. Tech. J., 28, pp. 656–715. 1949.
M. Santha and U. V. Vazirani, “Generating quasi-random sequences from semirandom sources”, J. Comput. System Sci., 33, pp. 75–87. 1986.
U. V. Vazirani, “Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources”, Proc. 17th Annual Symposium on Theory of Computing, pp. 366–378. 1985.
U. V. Vazirani and V. V. Vazirani, “Random polynomial time is equal to slightly random polynomial time”, Proc. 26th Annual Symposium of Foundations of Computer Science, pp. 417–428. 1985.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
McInnes, J.L., Pinkas, B. (1991). On the Impossibility of Private Key Cryptography with Weakly Random Keys. In: Menezes, A.J., Vanstone, S.A. (eds) Advances in Cryptology-CRYPTO’ 90. CRYPTO 1990. Lecture Notes in Computer Science, vol 537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-38424-3_31
Download citation
DOI: https://doi.org/10.1007/3-540-38424-3_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54508-8
Online ISBN: 978-3-540-38424-3
eBook Packages: Springer Book Archive