LGro
Shared contact discovery
Currently, we use UUIDs for long term identifiers, which isn't ideal because you can't sign with them. So we'll probably switch to using identity keypairs and public keys as identities.
Currently, we just share all known identities with contacts to find shared ones. Given the randomness of public keys that isn't the worst idea but also not ideal since even when I observe the list of identities that two of my contacts share with me and I don't recognize most of their contacts, I can still figure out the shared contacts between the two.
Using private set intersection would be the more privacy oriented solution. See oblivious transport implementations at https://github.com/osu-crypto/libOTe/blob/master/README.md and PSI library https://github.com/OpenMined/PSI, also check out bloom filters e.g. from https://github.com/ArashPartow/bloom.
Since we're only ever comparing a couple hundred maybe thousand contacts and never have the classical client server handful vs millions scenario, we might get away with continuing to send the full set of contacts rather than having to do fancy PSI, as long as it isn't just identities for the contacts but some kind of challenge that is unique to a pair of contacts that do the comparison of their sets.
We can generate a challenge (nonce), then send that to the other side, who, for each identity, computes HASH(identity_public_key + nonce), and sends it back. We then perform the same hashes on our side and see which match. For the ones that don't, we can't reverse the hash they send back, so we don't get to find out what accounts they know about.
If we can find a way to generate a dictionary of identity public keys some other way, this is still breakable.
One even better way that automatically proves to each other that a connection to a certain contact has actually existed at some point:
A on connection with each of their contacts receives their identity signed by their contact's identity AC = Sign(A_pub, C_sec) then A can just send all of those signatures to B and B can try to verify each one with all of the public identity keys they know about to figure out both, which contacts they share and be sure that A actually was connected to them at some point.
(Optionally, the signature can include a date if the use case requires proof of recent connection, which for this case it doesn't.)
The before mentioned approaches were flawed, this is the current candidate for implementation:
The approach is based on each pair of users A and B deriving a secret S_AB based on their long lived identity key pairs.
For each of their other contacts, e.g. C they then hash this secret together with the recipient's i.e. C's public identity key Attest_AB_for_C = H(S_AB, ID_C).
When C receives Attest_AB_for_C from both A and B via their respective information sharing channels, then C learns that A and B already know each other.
If only A and not B would be connected with C, C would only receive Attest_AB_for_C from A and thus not learn anything about the connection between A and B.