1) Client uploads a bloom filter with all contacts on phone
2) Server responds with a bloom filter with all registered contacts that match the client's bloom filter
3) Client displays contacts that match server's bloom filter
You can optionally trade contacts back and forth again with a larger bits/contact ratio to decrease false positives.
I think it works out so that in exchange for 7 bits of information about each contact from the client, you can reduce the server's response by a factor of 128.
The problem with this is that (1) + (2) means the server now knows the user's address book. They're trying to avoid that with encrypted bloom filters and blind signature queries.
(0) The server informs the client about the parameters of the bloom filter where it currently keeps all the contacts.
(1) The client builds the bloom filter with the same parameters based on its address book. After building the bloom filter, the client XORs it with a fuzzing pattern [a].
(2) The server performs a logical AND of the received bloom filter and (its own bloom filter XOR another fuzzing pattern [b]), and sends back the result.
(3) The client XORs the result with the fuzzing pattern [a], and uses this bloom filter to perform the local queries.
(4) The client stores the differences in results between the subsequent results, and each time the same result is returned, it doubles the query interval [c].
(5) The client sends its own ID with each query, so as the network grows and the server inevitably needs to recreate the bloom filter with different parameters, it can do so gradually ahead of time from scratch just based on the IDs of the queriers.
[a] I haven't done any napkin calculations of how random it should be, nor how many bits would need to be set to 1. The idea is to add a certain amount of false negatives here so the server were not able to recover the contact list just by bruteforce lookups. To avoid the leakage of information by correlating the subsequent requests, this pattern should probably be a PRF(client_contacts), rather than a purely random function - thus, if the contact list did not change, it should not change either, and if the contact list did change, it should change in a way to mask the change in the contact list somewhat.
[b] This may not be needed. The idea is to try to protect against the client sending an all-1 list and getting the entire bloom filter. But given that both [a] and [b] may both introduce false negatives and false positives, maybe there should be another approach to restrict what is sent to the client.
[c] Especially given the [a] and [b], chances are quite high that this might be a no-op.
It is obvious this method will introduce the false negatives, and if [b] is used, can add false positives as well.
Good point. Now I understand why they were suggesting bucketing.
I came up with this method for maintaining privacy while retrieving installed apps (to give app recommendations). Sounds like it might not translate across so well.
1) Client uploads a bloom filter with all contacts on phone
2) Server responds with a bloom filter with all registered contacts that match the client's bloom filter
3) Client displays contacts that match server's bloom filter
You can optionally trade contacts back and forth again with a larger bits/contact ratio to decrease false positives.
I think it works out so that in exchange for 7 bits of information about each contact from the client, you can reduce the server's response by a factor of 128.