The Difficulty Of Private Contact Discovery

This is great until you realize the average address book is a disgusting mess of spelling errors, wrong values in wrong fields, punctuation in places where punctuation isn&#x27;t necessary (commas in phone number fields, digits in name fields, etc.)<p>The only field that <i>might</i> be fairly consistent is email address and even that is no guarantee. Sure, it&#x27;s possible to clean up a contact before hashing, but when you consider the fact that the typical phone contains &gt;500 contacts it&#x27;s not something that can be done in a reasonable amount of time on a modern smartphone. For the last two years I&#x27;ve been working on a product that involves cleaning&#x2F;organizing contacts and making them searchable, when I started I had no idea what a massive undertaking it would be.<p>So, hash till your hearts content, but if you have 10 different people with the same contact in their address book I would be willing to bet that you will get 10 different hashes because humans are not good at data entry.

Interesting problem!<p>&gt; It’s also possible to compress “updates” to the bloom filter. The server just needs to calculate the XOR of the version the client has and the updated version, then run that through LZMA (the input will be mostly zeros), and transmit the compressed diff to the client.<p>&gt; Unfortunately, for a reasonably large user base, this strategy doesn’t work because the bloom filters themselves are too large to transmit to mobile clients. For 10 million TextSecure users, a bloom filter like this would be ~40MB, requested from the server 116 times a second if every client refreshes it once a day.<p>Wait, the LZMA-compressed daily diffs would be still be ~40MB? If the 40MB is just the initial bloom filter download, that&#x27;s not so bad. If 40MB is the daily diff, I&#x27;d be interested in seeing the calculation for that.

A new private-set intersection paper, claiming to scale orders of magnitude better than predecessors, has just been released [1]. I don&#x27;t know whether it solves your problem, as I haven&#x27;t read anything beyond the abstract, but you might want to check it out anyway.<p>[1] <a href="https://research.microsoft.com/en-us/um/people/senyk/pubs/sapsi.pdf" rel="nofollow">https:&#x2F;&#x2F;research.microsoft.com&#x2F;en-us&#x2F;um&#x2F;people&#x2F;senyk&#x2F;pubs&#x2F;sa...</a>

The problem is that it&#x27;s easy to upload 1000 randomly generated phone numbers and get back results. But I think you can distinguish random or sequentially generated numbers from a real user&#x27;s actual contact list, by looking at the distribution of friends among the contacts. A real contact list should have a high density of friendships between contacts. The system should only return results if the uploader provides a subgraph that&#x27;s more highly connected than a random one would be.<p>You&#x27;d need to look at real data and tune the parameters to make this effective.

I think there is a big difference between private contact discovery and contact discovery that isn&#x27;t brute forceable like we are seeing with SnapChat and others. One change that could be made for these very small pre image corpuses would be to ask the target user if they should be exposed to the searcher.<p>1) I upload the hashes of my contacts which enqueues a request to those that match the hashes<p>2) The target of the request dequeues those requests and is given the option to expose themselves to the other user<p>3) If approved, the original uploader gets access to that user on the service<p>This would stop the massive discovery issue and would only put a medium amount of friction into the growth engine. It obviously doesn&#x27;t cover the issue that the service itself has access to the contacts which means they could potentially be exposed. However, if the service discards hashes without matching queues and removes matches when dequeued, the risk to the user is much reduced from the full address book storage case.<p>This was written off the top of my head, so forgive me if I have left a big hole somewhere.

I understand how the Encrypted Bloom Filter they describe keeps my contacts private from the service, but it seems to leak the entire contact list the same as the trivial solution:<p>I install millions of copies of the app, all with a different contact list. I do this signed query process for every possible phone number. I now have the complete list of users.

Is this a real problem?<p>Is it reasonable to trust for me to trust you to you run some arbitrary binary on my phone that does some magical black box computation on my contact list and then phone home to your service, but not trust to that you will just not be a dick with the raw data?<p>Stated more simply, if I am paranoid about my privacy, then why am I running your apps and letting you read my contact list at all?

In a similar discussion, I said something about hashing phone number pairs. The graph has a lot more edges than nodes.<p>Still doesn&#x27;t stop someone from attacking a single number though.

So don&#x27;t do it. I know I&#x27;m probably in the minority here but I&#x27;ve never given another app permission to use my facebook or twitter account to &quot;Find Friends&quot; and I personally find the whole practice offensive. Just have an option to invite people by their email address&#x2F;number&#x2F;whatever, but not in bulk.

What about this?<p>1) Client uploads a bloom filter with all contacts on phone<p>2) Server responds with a bloom filter with all registered contacts that match the client&#x27;s bloom filter<p>3) Client displays contacts that match server&#x27;s bloom filter<p>You can optionally trade contacts back and forth again with a larger bits&#x2F;contact ratio to decrease false positives.<p>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&#x27;s response by a factor of 128.

40 MiB for ten million users? I think you should ditch the bloom filter if the false-positive rate is set so low it takes that much space.<p>Assuming you can map phone numbers onto the integers from 0 to ten billion, trivial compression of the is-a-user&#x2F;is-not-a-user bit sequence should easily fit in ~14MiB [1].<p>See also: succinct data structures [2] for accessing data without decompressing it.<p>(This is obviously a short term solution. Growth will overcome the savings.)<p>1: <a href="http://www.wolframalpha.com/input/?i=%28-p+lg_2%28p%29-%281-p%29+lg_2%281-p%29%29+*+ten+billion++%2F+2^23+where++p+%3D+ten+million+%2F+ten+billion" rel="nofollow">http:&#x2F;&#x2F;www.wolframalpha.com&#x2F;input&#x2F;?i=%28-p+lg_2%28p%29-%281-...</a><p>2: <a href="http://en.wikipedia.org/wiki/Succinct_data_structure" rel="nofollow">http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Succinct_data_structure</a>

It&#x27;s not a technical problem it&#x27;s a value prop problem. Most users don&#x27;t care about privacy....<p>Fundamentally there is more value for the network operator to grow the network than for users to disclose their details. Email works perfectly fine without having to disclose your address book because no one owns the network and therefore do not care how many people are using email.<p>Alternatively one could just allow users to choose whether to make their info public and then the client can just search a directory.

What about artificially increasing the size of the hash input. For instance: when finding out if a a contact exists the client sends 10 iterations of the contact (I.E. the contact number with another digit, each 0-9) hashed, the server keeps only one random hashed one to compare to (presumably the client hashes one of them randomly when sending it&#x27;s own contact information).<p>That way you increase the size of the problem from 10^10 to 10^11 but only increase your bandwidth 10 fold.<p>It still keeps the need to balance the amount of bandwidth used, but the bandwidth is no longer determined by the amount of all the users in the system, only the increase in problem size and the amount of contacts a person has.<p>Is that a worthwhile solution?

&gt; Building a social network is not easy. Social networks have value proportional to their size, so participants aren’t motivated to join new social networks which aren’t already large. It’s a paradox where if people haven’t already joined, people aren’t motivated to join.<p>Value is relative. For stakeholders, value is indeed given by the network’s size. For users (participants), it’s very debatable whether size equals value. The author seems to be mistaking the two perspectives for a single one. No paradox here.

Is is possible to leverage some sort of peer-assisted discovery? Where you ask some sub-set of your trusted contacts already on the system, to call the server on your behalf. So that the server is less likely to know whose contacts are being sent to it.<p>Of course, this can only be part of the full solution.<p>Disclaimer: just throwing a wild idea out there. don&#x27;t know anything about the field.

Could you use an enormously expensive hash function so that building a lookup table is infeasible?

I don&#x27;t really think you need to solve this problem using crypto. I think a simpler solution would be to use the &quot;hash it&quot; solution, but restrict how many lookups each client can do. You can either do this by the using the client&#x27;s phone number, IP or other unique information etc. This way an attacker would have a very hard time brute forcing this.<p>Additionally you could use captchas (or other humanity tests, such as SMS verification) to limit hackers creating automated accounts (in order to fight automated bots spamming and polluting the network).