Abstract
The next bit test as introduced by Blum and Micali was shown by Yao to be a universal test for sources of unbiased independent bits. The aim of this paper is to provide a rigorous methodology for testing sources whose output distributions are not necessarily uniform. We first show that the natural extension of the next bit test, even in the simplest case of biased independent bits, is no longer universal: we construct a source of biased bits, whose bits are obviously dependent and yet none of these bits can be predicted with probability of success greater than the bias. To overcome this difficulty, we develop new universal tests for arbitrary models of (potentially imperfect) sources of randomness. These new tools contribute to the theoretical as well as practical study of sources of randomness.
Article PDF
Similar content being viewed by others
References
Alon, N., and Rabin, M. O., Biased Coins and Randomized Algorithms, Advances in Computing Research, Vol. 5, ed. S. Micali, JAI Press, Greenwich, CT, 1989, pp. 499–507.
Blum, M., Independent Coin Flips From a Correlated Biased Source: A Finite State Markov Chain, Proc. 25th FOCS, 1984, pp. 425–433.
Blum, M., and Micali, S., How To Generate Cryptographically Strong Sequences of Pseudo-Random Bits, SIAM J. Comput., Vol. 13, No. 4, 1984, pp. 850–864. Previous version in Proc. 26th FOCS, 1985.
Boppana, R. B., and Hirschfeld, R., Pseudorandom Generators and Complexity Classes, Advances in Computing Research, Vol. 5, ed. S. Micali, JAI Press, Greenwick, CT, 1989.
Chor, B., and Goldreich, O., Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity, Proc. 26th FOCS, 1985, pp. 429–442.
Feldman, D., Impagliazzo, R., Naor, M., Nisan, N., Rudich, S., and Shamir, A., On Dice and Coins, Proc. ICALP, 1989.
Rabin, M. O., Probabilistic Algorithms for Testing Primality, J. Number Theory, Vol. 12, 1980, pp. 128–138.
Santha, M., and Vazirani, U. V., Generating Quasi-Random Sequences from Semi-Random Sources, J. Comput. System Sci., Vol. 33, 1986, pp. 75–87. Previous version in Proc. 25th FOCS, 1984.
Schrift, A. W., Randomness and Hardness of Bit-Sources, Ph.D. Thesis, The Weizmann Institute of Science, Rehovot, Israel, 1990.
Schrift, A. W., and Shamir, A., The Discrete Log is Very Discrete, Proc. 22nd STOC, 1990, pp. 405–415.
Schrift, A. W., and Shamir, A, On the Universality of the Next Bit Test, Proc. CRYPTO 90.
Vazirani, U. V., and Vazirani, V. V., Trapdoor Pseudo-Random Number Generator with Applications to Protocol Design, Proc. 24th FOCS, 1983, pp. 23–30.
von Neumann, J., Various Techniques Used in Connection with Random Digits, Appl. Math. Ser., Vol. 12, 1951, pp. 36–38. Reprinted in von Neumann's Collected Works, Vol. 5, Pergamon Press, New York, 1963, pp. 768–770.
Yao, A. C., Theory and Applications of Trapdoor Functions, Proc. 23rd FOCS, 1982, pp. 80–91.
Author information
Authors and Affiliations
Additional information
Communicated by Claude Crépeau
Rights and permissions
About this article
Cite this article
Schrift, A.W., Shamir, A. Universal tests for nonuniform distributions. J. Cryptology 6, 119–133 (1993). https://doi.org/10.1007/BF00198461
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF00198461
