Geodesic
Applications of two-faced processes to pseudorandom number generation
Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 68-70.

Voir la notice de l'article provenant de la source Math-Net.Ru

Random and pseudorandom number generators (RNG and PRNG) are used for many purposes including cryptographic 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 labelled 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 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. 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 is important for applications of them in cryptography.
Keywords: random number generator, pseudorandom number generator, Shannon entropy. 
@article{PDMA_2016_9_a26,
     author = {B. Ya. Ryabko},
     title = {Applications of two-faced processes to pseudorandom number generation},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {68--70},
     publisher = {mathdoc},
     number = {9},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2016_9_a26/}
}
TY  - JOUR
AU  - B. Ya. Ryabko
TI  - Applications of two-faced processes to pseudorandom number generation
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2016
SP  - 68
EP  - 70
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2016_9_a26/
LA  - ru
ID  - PDMA_2016_9_a26
ER  - 
%0 Journal Article
%A B. Ya. Ryabko
%T Applications of two-faced processes to pseudorandom number generation
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2016
%P 68-70
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2016_9_a26/
%G ru
%F PDMA_2016_9_a26
B. Ya. Ryabko. Applications of two-faced processes to pseudorandom number generation. Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 68-70. http://geodesic.mathdoc.fr/item/PDMA_2016_9_a26/

[1] Rukhin A., Soto J., Nechvatal J., et al., A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards and Technology, 2010

[2] Barker E., Kelsey D., Recommendation for Random Bit Generator (RBG) Constructions (DRAFT NIST Special Publication 800-90C), National Institute of Standards and Technology, 2012

[3] Ryabko B. Ya., Fionov A. N., Shokin Yu. I., Kriptografiya i steganografiya v informatsionnykh tekhnologiyakh, Nauka, Novosibirsk, 2015

[4] Cover T. M., Thomas J. A., Elements of Information Theory, Wiley-Interscience, N.Y., USA, 2006 | MR | Zbl