With
Isemis mention of "probability of false positives" I thought about
Zero-knowledge proof. This answer makes no claims to be secure as it was never reviewed, so others should review and comment it. I am no professional security expert either and I didn't have the time to make sure the low number of possible phone numbers might be a problem.
- User A and User B connect to each other (directly or via server) and assign a random identifier (RI) to each contact their contacts and stores it in a list (LA and LB) together with the phonenumber padded with the nonce and after applying a Key derivation function. LA stays at A and LB stays at B.
- User A proves one round of knowlege (see Zero-knowledge proof) for each of the numbers in list LA together with RI. User B has to find out by bruteforce to which of the contacts in LB each RI of A might fit. Each contact without fit is dropped out of LB. Possible fits are stored in the list for next round to improve bruteforce speed.
- User B proves one round of knowlege for each of the numbers in list LB together with RI. User A has to find out by bruteforce to which of the contacts in LA each RI of B might fit. Each contact without fit is dropped out of LA. Possible fits are stored in the list for next round to improve bruteforce speed.
- Repeat step 2 and 3 often enough to be statistically secure that each one has proven each of the numbers to the other user.
- Optional: exchange the remainings in lists LA and LB in a secure way mentioned by others or via a secure channel between User A and User B to be sure the matching of RIs was correct.
With this algorithm the server or an observer never learns any relevant information about the contacts of A or B except their count and how many they have in common. User A and B only learn the same information as the server and the common contacts.
Since the first steps of the algorithm are exponential and ressource intensive one should include protection against DOS in implementations.