I think the information who is a contact of whom should not reside with the provider, but be distributed among the peers. I had a proof of concept of something

I think the information who is a contact of whom should not reside with the provider, but be distributed among the peers. I had a proof of concept of something similar working a couple years ago. I was writing a file-sharing app, and the goal was to piggy-pack on the existing social graph that you had from Facebook, Skype and so on. I could not register as a proper Facebook app, since that required having a domain, and I would be legally catchable in case somebody used my app to share copyrighted or illegal stuff. Back then, Facebook messenger was based on XMPP/Jabber, which allows sending custom stanzas (secret messages that are not shown to the user). My app would ask for your login, then send a message to every contact, and if it got a reply from another instance, it would perform a handshake and exchange keys. This also worked over (old) Skype, which although it didn't support XMPP, you could do something similar with SkypeAPI. (Unfortunately, a few months later almost every messaging service that allowed such a trick stopped it...) Now, this trick doesn't help if you are trying to set up a new social graph in the first place. But I think with this "send an invisible message to a potential contact's app" primitive, you could build a list of mutuals securely. (Other caveats apply, you'd let somebody know that you have their number for example...)