**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.

**Category / Keywords: **foundations / pseudo-randomness

**Date: **received 18 Dec 2015

**Contact author: **boris at ryabko net

**Available format(s): **PDF | BibTeX Citation

**Version: **20151221:044539 (All versions of this report)

**Short URL: **ia.cr/2015/1217

[ Cryptology ePrint archive ]