On Fri, Aug 08, 2008 at 11:20:15AM -0700, Eric Rescorla wrote: > At Fri, 08 Aug 2008 10:43:53 -0700, > Dan Kaminsky wrote: > > Funnily enough I was just working on this -- and found that we'd end up > > adding a couple megabytes to every browser. #DEFINE NONSTARTER. I am > > curious about the feasibility of a large bloom filter that fails back to > > online checking though. This has side effects but perhaps they can be > > made statistically very unlikely, without blowing out the size of a browser. > > Why do you say a couple of megabytes? 99% of the value would be > 1024-bit RSA keys. There are ~32,000 such keys. If you devote an > 80-bit hash to each one (which is easily large enough to give you a > vanishingly small false positive probability; you could probably get > away with 64 bits), that's 320KB. Given that the smallest Firefox > [...]

You could store {<hash>, <seed>} and check matches for false positives by generating a key with the corresponding seed and then checking for an exact match -- slow, but rare. This way you could choose your false positive rate / table size comfort zone and vary the size of the hash accordingly. Nico -- --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]