The Right Thing is for individual users of Signal to privately compute set intersections between their own contacts. If Alice knows Bob, Charlie & Dan, and Bob knows Alice, Charlie & Eve, then when Alice & Bob add each other then they could each execute a protocol which would reveal that they both know Charlie.
In the last discussion of this, pbsd posted a link [1] to a great Microsoft paper covering private set intersection [2]. It works its way through a number of different protocols, but what it ends up with is this:
- Alice generates three sets of dummy data D1, D2 & D3 (where the lengths of all three sets are equal to a security parameter t, and the items in the sets are invalid phone numbers (perhaps, elements of the form 'invalid:$RANDOM_DATA') and sends them to Bob securely. These dummy sets will be used to observe if the server is cheating.
- Bob checks that they are well-formed (i.e., of the right length and invalid phone numbers).
- Alice & Bob then generate a shared key K1 using a simulated coin-tossing protocol.
- Bob then generates a shared key K2 with the server (in this case, the OWS server) using the simulated coing-tossing protocol.
- Alice then sends to the server SHUFFLE{HMAC(K1, Charlie:1), HMAC(K1, Charlie:2), … HMAC(K1, Charlie:n), HMAC(K1, Dan:1), HMAC(K1, Dan:2), … HMAC(K1, Dan:n), HMAC(K1, D1_1), HMAC(K1, D1_2) … HMAC(K1, D1_t), HMAC(K1, D2_1), HMAC(K1, D2_2), HMAC(K1, D2_t)}, where n is another security parameter, Charlie is Charlie's phone number and Dan is Dan's phone number. Since the server doesn't know K1 and it doesn't know how the set was shuffled, it has no idea which of the hashes is which phone number, nor which is a dummy.
- The server then generates a random SEED and sends to Alice KEYED_SHUFFLE(SEED, {HMAC(K2, HMAC(K1, Charlie:1)), HMAC(K2, HMAC(K1, Charlie:2)), … HMAC(K2, HMAC(K1, D2_t))}). Since Alice doesn't know K2, and since she doesn't know how the set was shuffled, she learns nothing yet.
- Bob sends SHUFFLE{HMAC(K2, HMAC(K1, Charlie:1)), HMAC(K2, HMAC(K1, Charlie:2)), … HMAC(K2, HMAC(K1, Charlie:n)), HMAC(K2, HMAC(K1, Eve:1)), HMAC(K2, HMAC(K1, Eve:2)), … HMAC(K2, HMAC(K1, Eve:n)), HMAC(K2, HMAC(K1, D2_1)), HMAC(K2, HMAC(K1, D2_2)), … HMAC(K2, HMAC(K1, D2_t)), HMAC(K2, HMAC(K1, D3_1)), HMAC(K2, HMAC(K1, D3_2)), … HMAC(K2, HMAC(K1, D3_t))} to Alice.
- Alice is know able to compute the intersection of the message she received from the server and the message she received from Bob. She does so, and sends the intersection {HMAC(K2, HMAC(K1, Charlie:1)), HMAC(K2, HMAC(K1, Charlie:2)), … HMAC(K2, HMAC(K1, Charlie:n)), HMAC(K2, HMAC(K1, D2)} to Bob.
- Bob knows K1 & K2, and can calculate HMAC(K2, HMAC(K1, X)) for any X he knows (including the members of the three dummy sets D1, D2 & D3). He can now check that neither Alice nor the server has cheated. First, he finds the original X for each HMAC(K2, HMAC(K1, X)) in the intersection. Then, if any member of D2 is missing from the result, or if any member of D1 or D3 is in the result, then someone has cheated, or if he doesn't see all of Charlie:1, Charlie:2 … Charlie:n then someone has cheated. In this case, Bob knows that neither Alice nor the server cheated, and now he knows that they share Charlie in common.
- Bob tells the server 'continue' and the server sends Alice the random seed used to in the KEYED_SHUFFLE; Alice uses this to determine which item she sent the server corresponds to which item the server sent to her, and from that which item in the intersection she sent to Bob corresponds to Charlie:1, Charlie:2, … Charlie:n, Dan:1, Dan:2, … Dan:n and so forth. Alice, too, can see if either Bob or the server cheated.
At the end of this protocol, Alice & Bob both know that they share a contact in common with the same phone number. In place of phone numbers, of course, one might use pseudonyms, public keys &c. They've sent relatively small messages (just a few times the size of their contact lists), and the server doesn't know how many they have in common, or whether they have anyone in common.
So, problem solved.
Edit: I should note that there's no way for Alice to know that Dan also has an account if they don't know any other user in common, and of course Bob & Alice need to exchange identities offline in person first. But, once that exchange has happened, everything else Just Works™ and due to the small-world phenomenon as more users use it, more users discover one another using it. Users who know one another can even re-run the protocol every once in awhile, when discovering new contacts.
[1] https://news.ycombinator.com/item?id=7009674 [2] http://research.microsoft.com/pubs/194141/sapsi2.pdf