3 ms·

The number of downloads required to get each additional nibble is 16 times that of the previous nibble.

• cvwright 11y ago
  Also -- I was too sloppy in my earlier analysis, and as a result, my numbers could be way off. The attacker might learn much less than I initially thought. It depends on how many users are subscribed to the service. After the client downloads the BF for L0 and hashes the entire space of 10 billion telnos, he knows 90% of the non-subscribers for certain. All the telnos that matched in the Bloom filter are either (a) subscribers of the service or (b) false positives from the BF. Let's say there are n subscribers. Then the attacker gets a total of n + 0.10 * (10^10 - n) hits on L0. The likelihood that a matching telno is actually a subscriber is n / (n + 0.10 * (10^10 - n)). So he learns something with each level of the Bloom filter, but getting to 90% certainty may require retrieving several levels of the BF.
  • chrisdew 11y ago
    Thanks for your questions and analysis.