RTFA. He addresses that in the first few paragraphs. Because there are 10^10 possible phone numbers (approximately), it is very easy to build a rainbow table of all hashed phone numbers and back-track a hash to it's phone number.

Well, actually I did read the article and address that in my comment that I don't think that it is important to hide the address from the server but it is important to hide them from the brute force attacker. I believe that my suggestion stops a brute force attacker from pulling the whole database like you can today with many of these systems.

Properly implemented rate limiting would be a better way to achieve that though. That is were the 'blinding signature' part comes in: to give the server the possibility to intelligently rate limit.

Rate limiting is a terrible solution to this sort of problem IMO. It just forces the attacker to be patient, but they will eventually get what they want, which is name/phone number pairs of the entire numeric space of phone numbers. His solution is problematic because it distributes the burdain to the user, and anyone who's gotten massive numbers of friend requests on a chat service can attest to how unfriendly that is, but it's on the right track. It should not be possible for an attacker to get contact information for arbitrary phone numbers through an api. Something should gate that, probably through the mutuality of having each other on each other's contact list.

We're not necessarily talking about sharing contact information; all we're talking about here is an acknowledgement of existence.

Given that context, due to the nature of the problem, rate limiting is by definition the -only- solution to the problem (if I'm understanding the problem correctly.)

You do have a point that perhaps the question we should be asking should be 'how do we detect mutual connections,' but that's another story altogether.

Under what circumstances do I want someone who I have not even enough interest in to put in my phone's dialer to be able to ping my phone number and get my name back?

The question of whether services should even be DOING this kind of open book "does this phone number have a user attached and what is their name?" query is more fundamental than any other question, imo. It's not another story, it's a skipped first story.

Phone numbers are not unique values, you should never assume that a phone number alone (or even a phone number and last name) is enough information to uniquely identify an individual.

Case in point: I work with a guy who used to work at his dads office. He and his dad both have the same name, and they both had the same office number. This algorithm would incorrectly identify both people as being the same person when in fact they are not.

Phone numbers are unique values when you need to call a phone or send an SMS, which is what this software does. If you were trying to do your taxes, sure...but in this case a phone number is exactly enough.

Lots of folks still use land lines.

They probably aren't trying to use TextSecure with their landlines though.

You should never assume that any piece of information is not enough to uniquely identify an individual.

You are thinking from the point of view of a database administrator, whose job it is to make it easy to uniquely identify an entity.

In security it's about making it as hard as possible to deduce even the slightest of information about a person, increasing the k-anonymity as they say.

For all intents and purposes, that a phone number resolves to only two people, and they're also conveniently located geographically near to each other, and are probably very distinct in a whole range of other things, makes it the perfect key for any security adversary.

You make a good point, my job is to make it simple for machines to differentiate between two people, a task a human could do easily.