Paul Crowley (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
ciphergoth) wrote2002-11-28 01:39 pm
ciphergoth) wrote2002-11-28 01:39 pm
A blow to my Geiger counter strategy
Someone on sci.crypt just referenced this paper
http://citeseer.nj.nec.com/juels98how.html
for a provably optimal strategy to do the same job. Arse. I've implemented their strategy in Python and put it on my unbiasing software page.
http://www.ciphergoth.org/software/unbiasing
However, the good news is that this strategy takes O(N^2) time, where N is the block size; mine takes average time N log N since it's based on Quicksort. That means I can handle far larger blocks in the same time, so mine may still be a winner in some situations, since you always get more information per bit if you take larger blocks, up to the limit of the amount of information available. Also their strategy involves bignum arithmetic; if you factor that in then mine's a lot easier to implement.
I've calculated the theoretical limit of the information available per bit from the HotBits data: it's 6.77 bits/sample. At a block size of 2^18 samples, I get 6.43 bits/sample, so I'm not too far off. On the other hand, their strategy gets 6.62 bits/sample with a block size of just 1024 bits. I'll have to implement theirs in C to get a fair comparison...
Update: Implemented theirs in C. While their strategy consistently gets far more bits/sample at a given blocksize than mine, the real tradeoff is between bits/sample and time. And that's one it looks like I consistently win - I get around 2 million bits/second at a wide range of block sizes, whereas they're getting about a tenth that for the same conversion efficiency - and doubling the block size halves their speed. So I'm not doomed after all - I just need to use larger block sizes than them. Update: see http://hacks.ciphergoth.org/jjsh-versus-me.ps
http://citeseer.nj.nec.com/juels98how.html
for a provably optimal strategy to do the same job. Arse. I've implemented their strategy in Python and put it on my unbiasing software page.
http://www.ciphergoth.org/software/unbiasing
However, the good news is that this strategy takes O(N^2) time, where N is the block size; mine takes average time N log N since it's based on Quicksort. That means I can handle far larger blocks in the same time, so mine may still be a winner in some situations, since you always get more information per bit if you take larger blocks, up to the limit of the amount of information available. Also their strategy involves bignum arithmetic; if you factor that in then mine's a lot easier to implement.
I've calculated the theoretical limit of the information available per bit from the HotBits data: it's 6.77 bits/sample. At a block size of 2^18 samples, I get 6.43 bits/sample, so I'm not too far off. On the other hand, their strategy gets 6.62 bits/sample with a block size of just 1024 bits. I'll have to implement theirs in C to get a fair comparison...
Update: Implemented theirs in C. While their strategy consistently gets far more bits/sample at a given blocksize than mine, the real tradeoff is between bits/sample and time. And that's one it looks like I consistently win - I get around 2 million bits/second at a wide range of block sizes, whereas they're getting about a tenth that for the same conversion efficiency - and doubling the block size halves their speed. So I'm not doomed after all - I just need to use larger block sizes than them. Update: see http://hacks.ciphergoth.org/jjsh-versus-me.ps