Given a set of bit sequences generated by an extractor, what would be a valid setting for estimating the randomness of these generated keys and what resolutions can be drawn for that extractor in general? The extractor will only generate bit sequences of fixed length such as 20 bits. Thus, all possible outcomes span only a finite key space.
Though we would like to take the generated sequences as input to a cryptographic protocol (which has strong security properties even in the case of low-entropy input) our requirements for 'randomness' are somewhat less strict than in any well-defined notion of randomness since these typically focus on properties of infinite sequences. We are rather focusing on local randomness, i.e. the properties expressed by finite subsequences of random sequences of infinite length, and we would be even comfortable with results characterizing the peculiarities/bias/inter-bit-dependencies our extractor exhibits.
Currently, we approach this problem from two angles:
- Empirical: We apply statistical tests on the set of generated sequences such as comparing the number of birthday collisions in the set of sequences with the estimated number of collisions for a typical sub sample of same size. We should point out here that we are aware of suites as dieharder, but don't think they are applicable here as we are only interested in the case of finite sequences.
- Conceptual: We focus on corner-cases such as the case where our extractor produces the sequence consisting exclusively of ones and reason about the likelihood of this event.
Please Note: We are aware of suites such as dieharder. We also know about different other tests but consider them not applicable here as they do not focus specifically on sets of fixed-length sequences!
Though we think there is no other straight-forward way of solving this question, we would be grateful for any further insights or advices. Meaningful tests would also be much appreciated.
Update: While we know that concatenation of these bit sequences should be possible given they are random, we inherently lack enough data to do so - we depend on specific sensor data for our extractor to work and this is not easy to obtain in large amounts. We might be able to extract only about 1GB. Therefore, we are trying to bypass this lack of data by focusing more on the specific characteristic of our problem.
Also, the term key is probably not applicable here and should be taken as password instead as we do not ever use it to encrypt plain text. This might enable us to use it even if there are some known slight weaknesses in the extractor.