> 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: - Alic

> 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.