3 ms·

That makes sense, but any malicious service could pretend that a particular telno was a user of the service, in order to see which users had that contact. I'm

That makes sense, but any malicious service could pretend that a particular telno was a user of the service, in order to see which users had that contact. I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts.

cvwright 11y ago
> I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts. Right, so an honest-but-curious adversary model sounds like it's a good fit for the server. Then all these attacks where the server lies about something are out of scope. Again, I like this idea so I think it's worth thinking about it some more. Not trying to nitpick here, just trying to help think through what you can do. What about the clients? Do you want to limit what they can learn? Given any telno, a client can quickly tell whether that telno belongs to the service, even if the client doesn't really have that number in its contacts. Does that matter? I guess we come to a sort of meta-point here. What does it mean for a number to be in someone's address book? Anything? A fundamental part of the problem seems to stem from trying to make this work with identifiers that come from a (cryptographically speaking) very small space. Extending the attack above, really the client can get a pretty decent approximation of the entire list of telnos in the service. If he checks all 10 billion telnos against the BF for L0, he gets a list that includes all subscribers and several false positives -- each number in the list is only 90% likely to be a subscriber. If he wants to refine his estimate for the likelihood that any given number is a subscriber, he retrieves the corresponding BF for L1. So he starts with a decent estimate of the subscriber list, and with each BF that he downloads, is estimate improves. How bad is that? I'm really not sure...
- chrisdew 11y ago
  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.

cvwright 11y ago

> I'm assuming the objective is to minimise the service's unnecessary knowledge of non-service-user contacts. Right, so an honest-but-curious adversary model sounds like it's a good fit for the server. Then all these attacks where the server lies about something are out of scope. Again, I like this idea so I think it's worth thinking about it some more. Not trying to nitpick here, just trying to help think through what you can do. What about the clients? Do you want to limit what they can learn? Given any telno, a client can quickly tell whether that telno belongs to the service, even if the client doesn't really have that number in its contacts. Does that matter? I guess we come to a sort of meta-point here. What does it mean for a number to be in someone's address book? Anything? A fundamental part of the problem seems to stem from trying to make this work with identifiers that come from a (cryptographically speaking) very small space. Extending the attack above, really the client can get a pretty decent approximation of the entire list of telnos in the service. If he checks all 10 billion telnos against the BF for L0, he gets a list that includes all subscribers and several false positives -- each number in the list is only 90% likely to be a subscriber. If he wants to refine his estimate for the likelihood that any given number is a subscriber, he retrieves the corresponding BF for L1. So he starts with a decent estimate of the subscriber list, and with each BF that he downloads, is estimate improves. How bad is that? I'm really not sure...

chrisdew 11y ago
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.