I have a potentially infinite stream of data originating in some physical phenomena that may expose random behavior (due to quantum effects, thermal noise, the butterfly effect in chaotic dynamical systems, etc). The stream may carry some amount of entropy (true randomness), but it may be distributed unevenly throughout the stream and its density is unknown.

I have a limited storage space (say, 1GB). I need a procedure that can collect as much entropy as possible from the stream to the storage provided, and, when required, generate (in a reasonable time) a single file containing the collected entropy. It is preferable to make the resulting file as small as possible without reducing the amount of entropy it contains.

How can I implement such a procedure?

  • $\begingroup$ Does the stream have essentially unlimited length? $\:$ Can you use significantly more space than the file's size? $\endgroup$
    – user991
    Feb 7 '14 at 22:26
  • $\begingroup$ Yes, the stream is potentially infinite, but the total available storage is limited, and a need to produce the resulting file may occur at any moment. I updated the problem statement to explain this better. $\endgroup$ Feb 8 '14 at 0:29
  • $\begingroup$ If the entropy level of the stream is unknown or uneven, I would take large chunks (16KB or more) and run it through SHA-512 to produce your output, possibly encrypting each hash with with independent keys (I have used this method and it seems to produce well distributed data from poor entropy sources, my key generator was SHA256 with a nonce and incrementing counter, cipher Twofish). Do you have entropy estimates of the stream? $\endgroup$ Feb 8 '14 at 12:13

Partition the file into blocks of almost-equal size, and let $B$ denote the maximum block size (in bits). $\:$ Choose a randomness extractor whose outputs are long enough to
sample from the blocks and still have $B$ bits of the output left over.
Choose a seed for the extractor (unless you choose an extractor that doesn't actually use one).

For each [extractor's source's size] bits from the stream, apply the extractor to those bits,
use the output to sample a block as described before, let $s$ be the number of bits in that block,
set that block equal to its old value plus the left-most $s$ bits of the remaining extractor output
(both interpreted as unsigned integers) mod 2$^s$, then if any of the extractor's
output is still unused, continue as if those were the next bits from the stream.


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.