5
$\begingroup$

Given an (infinite) stream of uncorrelated random bit with a known "reasonable" bias (say 15-85% 1's) I want to whiten it, e.i. produce a shorter stream of bits that has no bias. The restriction is that the output must be usable as a cryptographically secure ransom bit stream.

The proposal is to compress the stream with a Huffman code constructed from a table of theoretic frequencies of bit sequences (say 10 bits at a time). As the number of bits used increases, will this approach ideal performance?

Clearly, the ratio of bits consumed to bits produced will be nearly ideal, but what about the other interesting properties?

Edit1: A while back I looked around a bit on this topic and found some methods but didn't see this approach used and I'm wondering if it has some sort of hidden flaw.

Edit 2: I'm only interested in the performance of this device for uncorrelated input, that is (to make sure I'm using the term correctly) where the bias of any given element is independent of any and all other values. This happens to make the frequency of any given sequence a function only of it's length and sum.

Edit 3: Assume the input is not a bottle neck, that it can generate bits as fast as I need them.

Improve this question
$\endgroup$
4
  • $\begingroup$ If you want to produce an unbiased stream from a biased one how about the following conversion (if a 0 has probability $p$): "00" -> "" (Probability $p^2$) "01" -> "0" (Probability $p (1-p)$) "10" -> "1" (Probability $p (1-p)$) "11" -> "" (Probability $(1-p)^2$) Then the produced bitstream is unbiased, although it may produce arbitrarily short sequences. $\endgroup$
    – Mark Bell
    Commented Jun 25, 2010 at 21:20
  • 3
    $\begingroup$ @qwerty1793: That's a well known solution: en.wikipedia.org/wiki/… $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 22:05
  • $\begingroup$ I just realized, that this well known method can maybe improved. If you use 4 bits at the time. Ignore the combination of "0000" and "1111". Furthermore, ignore two sequences with two 1. Then you keep 4 sequence with one 1, 4 sequences with two 1, and 4 sequences with three 1. From that, you can make 2 bits. Is 50% more efficient in the use of bits. $\endgroup$
    – Lucas K.
    Commented Jun 25, 2010 at 23:00
  • 1
    $\begingroup$ @Lucas K. it's interesting to note that your approach is starting to look a bit like mine. $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 23:23

2 Answers 2

Reset to default
5
$\begingroup$

I think a key search term here is randomness extractor (or randomness disperser). Here is a central paper on this topic: "Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors," Barak B., Kindler G., Shaltiel R., Sudakov B., Wigderson A., Journal of the ACM 57(4): 1-52, 2010. A randomness extractor samples the input bits intelligently and produces a (generally shorter) output string with improved randomness properties. Essentially an extractor converts 'impure' bits into 'pure' bits. They give explicit poly($n$)-time computable deterministic extractors with various guarantees. There is a very nice connection to Ramsey graphs, as that paper title indicates.

Improve this answer
$\endgroup$
3
  • $\begingroup$ After reading about half the the first page, that seems like a solution to a much more general problem. See edit. $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 23:05
  • $\begingroup$ @BCS: Perhaps then you want the simplest (and first?) randomness extractor, the Von Neumann extractor: "His extractor took successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits." $\endgroup$
    – Joseph O'Rourke
    Commented Jun 25, 2010 at 23:12
  • $\begingroup$ the Von Neumann extractor is very inefficient for high biases. Also see my comment to qwerty1793. $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 23:14
3
$\begingroup$

If your goal is to create an unbiased truly random stream, this page has an algorithm which produces results much faster than the usual technique (the one mentioned by qwerty1793 in the comments above).

However, if your concern is simply real-world cryptographic security, since random generators like the one you describe usually produce unbiased streams very slowly, you are better off whitening your stream once using the usual method and using that to seed a provably-secure cryptographic PRNG.

In fact, if you are able to produce your truly-random biased bits as quickly as your PRNG, you could even introduce true randomness to the result by XOR'ing the biased stream with the PRNG output. This works regardless of the stream's bias (due to the fact that random data XOR'ed with non-random data produces random data).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Why would it be slow? It could be implemented as a DFA and I expect may well end up I/O bound (I'm assuming the input stream is not a bottleneck). $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 23:18
  • $\begingroup$ Or are you saying the type of input source I'm assuming are generally very slow? $\endgroup$
    – BCS
    Commented Jun 25, 2010 at 23:25
  • $\begingroup$ @BCS: Yes, true hardware-based random number generators are based on chaotic physical processes, and tend to generate lots of 0's with the occasional (randomly placed) 1, causing them to be very slow for the purpose of generating unbiased random streams. You may get a few thousand bits per second, compared to BBS (hundreds-of-thousands) or Mersenne Twister (hundreds of millions, not cryptographically secure). $\endgroup$
    – BlueRaja
    Commented Jun 26, 2010 at 2:03
  • $\begingroup$ Ok. Well I did put tighter bounds on the bias than that. $\endgroup$
    – BCS
    Commented Jun 28, 2010 at 14:34
  • $\begingroup$ @BCS: It's not only the bias that's important, but the bits-per-seconds. $\endgroup$
    – BlueRaja
    Commented Jun 28, 2010 at 20:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .