> I don't see why a messaging service like Signal cares about mutual friends.
Signal doesn't care; users care about mutual friends.
Here's an example:
- Alice installs Signal². She has many contacts, and doesn't know which contacts also use Signal². Notably, she doesn't want to give the Signal² servers all of her contacts.
- Alice asks Bob to install Signal². He does, and they trade key information (e.g. via SMS, email, NFC — whatever) and their phones use private set intersection to discover that they have Charlie, Diana & Ed in common. None of those guys has Signal² installed yet, so far as Alice or Bob know.
- Alice asks Charlie to install Signal². He does, they trade key information, and they see that they have Bob, Frank & Gene in common. Charlie gets (what Alice says is) Bob's public key, without contacting Bob directly.
- Charlie's phone contacts Bob's phone, and discovers that they have Alice in common; Charlie's phone validates that Bob's claim of Alice's key matches what he verified himself.
- Bob asks Diana to install Signal². She already has it, so all they need to do is exchange keys and discover mutual contacts. They both know Alice & Ed — and Diana is able to give Bob Ed's public key (it turns out that, unbeknownst to Alice or Bob, he's been using Signal² for months). Bob's phone can then share Ed's public key with Alice in another round of set intersection.
- Diana's phone can also share Ed's public key with Alice, now that she knows Alice's contact information. Alice's phone now has two different people attesting to Ed's public key; if they agree, that's good and if they disagree then her phone can give her a warning. She can contact Ed out-of-band if she chooses. This is an improvement on the current Signal protocol, since Alice has a chance to detect a malicious attestation without having to manually compare keys with Ed.
Note the user experience: as each user starts using Signal², his social network is used to share the contact information of his circles of friends. Users are incented to be truthful, since lying will be easily detected. The Signal² servers never see users' contacts; they don't even need to know users' real-world identities.
Just as in current Signal, each Signal² user is introduced to the program by a friend. Just as in the current Signal, users discover contacts who use Signal². Now, it's not identical: users won't see contacts who use Signal but have no mutual friends in common. This is indeed a cost — but it comes with the benefit of not needing to trust OWS.