Cryptography Reference
In-Depth Information
The second approach, propounded by Solomonoff [171], Kolmogorov [91]
and Chaitin [27], views randomness as lack of pattern and structure. In this
approach, the shorter the description of an object (objects are understood to
be binary strings), the more it is random. Here description means an input
string (i.e., a program) which when fed to a fixed Universal Turing Machine
generates the object. If the length of the shortest such program is greater
than or equal to the length of the object, then the object is called perfectly
random. In other words, randomness is equivalent to incompressibility.
The third approach is computational. In this view, a distribution that
cannot be e
ciently distinguished from the uniform distribution is considered
random. Often the term “pseudo-random” is used to express this particular
notion of randomness. Contrary to the previous two approaches, here ran-
domness is not an inherent property of objects, or distributions, rather it is
relative to the computational resources of the observer. This model allows for
an e
cient and deterministic generation of (pseudo-)random bitstrings from
shorter seeds.
RC4, and as a matter of fact, any stream cipher, generates a pseudo-
random keystream from a (relatively) short secret key based on the third
view of randomness above.
