Shooting Dice
November 19th, 2007 by Jeremy Clark and Richard Carback in : SecurityInside Elections has an interesting post on the dice that were used to randomly select precincts for manual recount. In a Punchscan election, there is a lot more dice rolling. We need random choices of ballots to audit and sides of the tally to reveal.
Dice have their shortcomings. First, to convince yourself a die is not loaded requires a lot of rolling and statistical number crunching. Second, its fine if you are in the room to witness the rolling of the dice, but the process does disenfranchise everyone who is not.
For these reasons, Punchscan uses stock data to generate random numbers. Getting something random out of the data is a bit tricky (although, unfortunately for investors, not tricky enough) but it results in a random selection that anyone with a newspaper or the internet can check. For more details, see this paper.
November 20th, 2007 at 12:56 am
Does this thing pass the FIPS tests? Have you tested it on it? I believe this is the relevant doc:
http://www.itl.nist.gov/fipspubs/fip140-1.htm
Given the way it works, I’m not sure if FIPS absolutely applies? Anywho, I’m just curious… I probably asked when you presented the paper but I have long since forgotten.
November 20th, 2007 at 1:50 am
The cellular automata (rule 30) we run it through passes FIPS 140-1 but I believe it has trouble on FIPS 140-2. However we actually don’t care about cryptographically secure randomness here since the seed is public. We just need good statistical randomness, it doesn’t need to pass the next bit test.
That said, I’m sure there are applications where it would be relevant and in those cases, you could use a better PRNG than a CA.
November 20th, 2007 at 1:09 pm
Cellular automata is just a pet pseudo-random sequence generation technique of ours. Though rule 30 doesn’t pass 140-2, combining automatas in a non-linear way such as through a shrinking generator (as our undergraduate thesis proposed), would.
Of course there are many others. Though we didn’t propose it in the paper, our position was that since there’s not a performance constraint, using a slow semantically secure PRNG like Blum Blum Shub would probably make people “feel better.”
That’s because this proposal violates peoples’ intuition. The only secret information is the future closing price of stock indeces (i.e. what the seed WILL BE). But PRNG is run after the stocks close (i.e. when the seed becomes publically known), allowing anyone to run and generate the same sequence. Normally a PRNG is run for privacy purposes. Here it’s used for verification purposes.
FIPS140-x defines a bit-test which can be roughly summarized as “if you know a bit in the sequence, it shouldn’t help you determine previous or subsequent bits of the sequence.” In this application, everyone knows the seed and algorithm and therefore the entire bit sequence–the FIPS bit-test is moot.