3
$\begingroup$

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:

  1. Information theoretic security (or perhaps even perfect security) of the output is guaranteed if it is guaranteed for the seed.
  2. 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.

$\endgroup$
3
$\begingroup$

Since you are looking for an algorithm that guarantees entropy for the output if the input it entropic, you are not actually looking for a PRNG, which would expand a seed to a longer random output, but only a transformation from a binary sequence to arbitrary values.

You can achieve this using arithmetic coding, or range encoding, which is the same thing in a slightly different manner. It is a way to encode values from arbitrary probability distributions into minimal size. In your case you can decode a random "seed" sequence to extract random values in any interval(s).


Caution: normally it is fine to be slightly inexact in the encoder math as long as everything is deterministic, since that only worsens the encoding rate slightly. In your case, for secure random numbers the possible outputs must be equally probable so typical implementations may not work for you. Rounding must be done in a way that ensures this.

$\endgroup$
  • $\begingroup$ Thanks for the response. It is only a PRNG in the sense that it is a deterministic algorithm and it accepts some input as a "seed", even though in this case it may be an infinite sequence. I don't think that those range encoding techniques will work. I would have to reverse them in order to go from a bit sequence to some other symbol space. But I couldn't guarantee uniformity. The problem is that "the initial range can easily be divided into sub-ranges whose sizes are proportional to the probability" is not true. It also needs to operate on a symbol-by-symbol basis, not on entire sequences. $\endgroup$ – mikebolt Oct 3 '15 at 1:07
  • $\begingroup$ @mikebolt, I'm not sure what you mean by symbol-by-symbol, but regarding uniformity you can use a very large range and reject values at the end of the interval that do not divide uniformly. It is still better than simple rejection sampling, since the larger your interval the less information you lose. $\endgroup$ – otus Oct 3 '15 at 5:37
  • $\begingroup$ I mean that it is asked to produce one random number/symbol of output at a time, and it must do it without knowledge of future requested ranges. Using a larger range decreases the likelihood that you will lose information each time, but increases the information loss when you do lose information. I would like the information loss rate to approach zero as the sequence length approaches infinity. $\endgroup$ – mikebolt Oct 3 '15 at 19:20
  • $\begingroup$ I think that this is asking for an entropy extractor that can output a number $x$ within range $n$, whilst using up the least input entropy $s$ to generate said number. It's the only way I can relate information theoretic security to rejection sampling. I.e. keep $|n| < |s|$ where size is quantified in bits. $\endgroup$ – Paul Uszak Apr 28 at 23:37
  • $\begingroup$ In my mind the question hinges on whether rejection sampling (et al) consumes entropy discarding failed candidate $x$s. I say no as those bits don't leave the generator. $\endgroup$ – Paul Uszak Apr 28 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.