Welcome to the resource topic for 2015/1217
Title:
Two-faced processes and existence of RNG with proven properties
Authors: 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.
ePrint: https://eprint.iacr.org/2015/1217
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .