Pseudorandomness

Pseudorandomness measures the extent to which a sequence of numbers, though produced by a completely deterministic and repeatable process, appear to be patternless.[1]

The pattern's seeming randomness is the crux of much online and other security.[2] Since the sequence is repeatable, it is important that the seed which, together with a generator produce the numbers, be well chosen and kept hidden.[3]

History

The generation of random numbers has many uses (mostly in statistics, for random sampling, and simulation). Before modern computing, researchers requiring random numbers would either generate them through various means (dice, cards, roulette wheels,[4] etc.) or use existing random number tables.

The first attempt to provide researchers with a ready supply of random digits was in 1927, when the Cambridge University Press published a table of 41,600 digits developed by L.H.C. Tippett. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel;[4] the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates.

Unpredictability as "almost random"

Using a radioactive substance spewing out electrons and gamma rays whose decay is random, or obtaining unpredictable sequences of data using a radio tuned between stations, harvesting the atmospheric noise yields short term unpredicability.[1] The time investment needed to obtain these numbers led to a compromise: using some of these physics readings as a "seed" to generate more. The fewer the non-seed "random" numbers, the more truly random the numbers seem. One compromise is to intermix the timings between keystrokes by people.[5]

People's actions have been proven to be useful for the repeatability behind multi-factor authentication,[6] and studies of Brownian motion have shown how statistics and probabilistic models can predict what a group will do, even if a particular movement is random.[7]

The predictability of Pseudo-random number sequences produced by a deterministic algorithm are, in short clusters, seemingly random.[8]

In computational complexity

In theoretical computer science, a distribution is pseudorandom against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage.[9] This notion of pseudorandomness is studied in computational complexity theory and has applications to cryptography.

Formally, let S and T be finite sets and let F = {f: S → T} be a class of functions. A distribution D over S is ε-pseudorandom against F if for every f in F, the statistical distance between the distributions f(X), where X is sampled from D, and f(Y), where Y is sampled from the uniform distribution on S, is at most ε.

In typical applications, the class F describes a model of computation with bounded resources and one is interested in designing distributions D with certain properties that are pseudorandom against F. The distribution D is often specified as the output of a pseudorandom generator.[10]

See also

References
  1. George Johnson (June 12, 2001). "Connoisseurs of Chaos Offer A Valuable Product: Randomness". The New York Times.
  2. "The inherent flaws of Proof-of-Stake".
  3. Mark Ward (August 9, 2015). "Web's random numbers are too weak, researchers warn". BBC.
  4. "A Million Random Digits". RAND Corporation. Retrieved March 30, 2017.
  5. Jonathan Knudson (January 1998). "Javatalk: Horseshoes, hand grenades and random numbers". Sun Server. pp. 16–17.
  6. Eze Vidra (November 6, 2007). "Science Fiction? ClassifEye's Biometric Authentication for Cell Phones".
  7. 1880, Thorvald N. Thiele paper, using Least squares (the basis of Regression Analysis)
  8. S. P. Vadhan (2012). Pseudorandomness. pseudorandomness, the theory of efficiently generating objects that “look random” despite being constructed using little or no randomness
  9. Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
  10. "Pseudorandomness" (PDF).

Further reading
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.