> I don't have the URL handy but the Signal team did investigate the literature and known techniques for this a few years ago and found them to be nonviable.

Private set intersection (in which two Signal users compare contact lists to see which contacts they have in common, then trade Signal information for them) would work just fine.

This is their latest blog post on the topic: https://signal.org/blog/private-contact-discovery/