Paper 2015/1217

Two-faced processes and existence of RNG with proven properties

Boris Ryabko

Abstract

Random and pseudorandom number generators (RNG and PRNG) are used for many purposes including cryptographic, modeling and simulation applications. For such applications a generated bit sequence should mimic true random, i.e., by definition, such a sequence could be interpreted as the result of the flips of a “fair” coin with sides that are labeled “0” and “1”. It is known that the Shannon entropy of this process is 1 per letter, whereas for any other stationary process with binary alphabet the Shannon entopy is stricly less than 1. On the other hand, the entropy of the PRNG output should be much less than 1 bit (per letter), but the output sequence should look like truly random. We describe random processes for which those, in a first glance contradictory properties, are valid. More precisely, it is shown that there exist binary-alphabet random processes whose entropy is less than 1 bit (per letter), but a frequency of occurrences of any word $|u|$ goes to $2^{- |u|}$, where $|u|$ is the length of $u$. In turn, it gives a possibility to construct RNG and PRNG which possess theoretical guarantees. This, in turn, is important for applications such as those in cryptography.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
pseudo-randomness
Contact author(s)
boris @ ryabko net
History
2015-12-21: received
Short URL
https://ia.cr/2015/1217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1217,
      author = {Boris Ryabko},
      title = {Two-faced processes and existence of RNG with proven properties},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1217},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1217}},
      url = {https://eprint.iacr.org/2015/1217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.