Ryabko B.Y.  

Two-Faced Processes and Pseudorandom Number Generators with Proven Properties

Two-Faced Processes and Pseudorandom Number
Generators with Proven Properties

B.Ya. Ryabko1,2*
1Institute of Computational Technologies of SB RAS, Novosibirsk, Russia
2Novosibirsk State University, Novosibirsk, Russia
*e-mail address: boris@ryabko.net

Pseudorandom number generators (PRNG) are used for many purposes including cryptographic [1], modeling and simulation applications [2]. 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 labelled “0” and “1”  (i.e., it is  the Bernoulli process with p(0) = p(1) = ½), see [3].
The RNG and PRNG  attract attention of many researchers due to its importance in practice and interest in theory, because, in a certain sense, this  problem is close to foundations of probability theory, see, for example, [4,5].
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 entropy is strictly 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 [3].
We describe random processes for which these,  contradictory at first glance, 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 the frequency of occurrence of any binary word  goes to its probability for the Bernoulli process with p(0) = p(1) = ½.  
In this report we show how the two-faced processes give a possibility to construct  PRNG which possess theoretical  guarantees.  Besides, we describe some experiments where sequences are generated PRNG which are  based on the two-faced processes.

1 E. Barker and J. Kelsey, Recommendation for Random Bit Generator (RBG)   Constructions (DRAFT NIST Special Publication 800-90C). (National Institute of Standards and Technology, 2012).
2 P. L'Ecuyer,  Random Number Generation and Quasi-Monte Carlo, (Wiley, 2014).
3 A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, and S. Vo,  A Statistical Test   Suite for Random and Pseudorandom Number Generators for Cryptographic  Applications, (National Institute of   Standards and Technology, 2010).
[4] C. S. Calude, Information and Randomness - An Algorithmic Perspective.   2nd Edition, ( Springer-Verlag, 2002).
[5] M. Li and P. Vitanyi,  An Introduction to Kolmogorov Complexity and Its   Applications, 3rd edition, ( New York:  Springer, 2008).