This seems to be a simple problem, and I think a simple solution. I haven't worked on a system needing such a thing, but I figured we could have a discussion here so in the future when I/we need to, there won't be a problem.

Goals: Provide a mechanism to determine if any of a users contacts is already a member of given service.

Requirements: Personal identifying information should not be transmitted across the wire. Data transmitted across the wire should not be susceptible to MITM attacks. Any data stored should be useless if compromised.

Proposed Solution: Data transmitted should use any available encryption scheme built into the protocol (SSL). Personally identifying information (phone numbers) should be encrypted using asymmetrical encryption before being transmitted. If this data is stored it should be encrypted using a different encryption mechanism, such as bcrypt. Any lookups performed will use this same mechanism to generate the lookup key.

Incomplete. Lets discuss any holes and improvements.