I have an idea for an research project, but I am first wondering if it has been researched or implemented before.
I think I have a way to come up with a set of PRNG algorithms which have the following properties:
- Information theoretic security (or perhaps even perfect security) of the output is guaranteed if it is guaranteed for the seed.
- The algorithm "re-seeds" using additional information from the seed only whenever it is absolutely necessary to guarantee the first property.
It is easy to satisfy these properties: just make an algorithm that outputs the "seed" bits. That's not what I'm interested in. I'm interested in one that could convert between symbol spaces. More generally, this algorithm would present itself as a random number generation function which accepts a natural range
n for each function call, and returns as the result a random integer in the range
[1, n] which is chosen from a perfectly uniform distribution over that range. The seed would probably just be a bit sequence, but it could be any sequence of pairs
(a, b), where
a is the information in the form of a natural number, and
b is the inclusive upper limit for
a. As such it could convert between bases, even mid-sequence.
Meeting the first property is possible by using rejection sampling, but rejection sampling wastes information. My goal is to prove that an algorithm can satisfy both properties in an entropy-optimal way that wastes only a negligible amount of information so as not to burden an entropy source.