Problem statement: you have a friend’s phone number. You want to find your friend’s npub in such a way that the number is never revealed to anyone who doesn’t already know it. That is phone->npub, but NOT npub->phone.

One approach is to treat it as a two-step process. The first step is to find candidate npubs who credibly could have the number. The second step is to challenge candidates to prove it.

Step 1. Find candidates. Suppose each npub publishes a Bloom filter which has been fed their phone number AND other random  garbage. By fetching these filters, you can test them to see if any at least credibly claim to have the number.

Step 2. Challenge candidates. For each candidate, send a DM which has a random payload symmetrically encrypted with a key containing their phone number and a nonce. Tell them the nonce and encryption scheme in the DM. If they have the phone number, they can decrypt the random payload and return it as proof. If they don’t, they’ll have to search. But they can’t have pre-computed the rainbow table because your nonce was random, and also you control the encryption scheme.

If a candidate doesn’t respond in a timely manner, this could be because they didn’t receive the DM, or they’re trying to crack the number. So you’ll have to use some judgement, perhaps starting a DM conversation first, then issuing the challenge.

Note: Because the search space of phone numbers is so small, the Bloom filters must contain a bunch of random phone numbers as false positives to prevent an attacker from determining an npub’s number by brute force tests. A few tens of thousands ought to be enough.

There are probably holes in this approach, I just thought it up now in response to your query.