3 ms·

First, it looks like this scheme is broken due to cpu constraints. However... It had looked more like the encrypted bloom filter was intended to prevent the cl

First, it looks like this scheme is broken due to cpu constraints. However... It had looked more like the encrypted bloom filter was intended to prevent the client from obtaining the list of registered users. With (1) + (2), the server only has a few bits of information about each of the phone's contacts. It would be analogous to just having the area codes.

ay 13y ago
What about a slightly modified idea: (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.

ay 13y ago

What about a slightly modified idea: (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.