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.
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.