Is there a way to prove knowledge of a limited resource like a phone number just to the people who already know about it?

Question

For instance, let's say Bob's phone number is X and Alice has somehow identified that Bob's phone number is X.

Now she doesn't have a direct way to contact Bob, so she wants to post in a public forum with proof that she knows Bob's phone number.

This almost seems impossible since phone numbers are a very limited space and solutions like hashing would not be effective. One possible solution is to have an extremely slow hash (let's say one that takes hour(s) to compute), but this has issues both practically (Bob likely won't bother checking) and theoretically (It's still not difficult for a determined person to find out).

Are there any cryptographic solutions to this, even if they are imperfect? We can assume that there is a period of time after which this information can be made public.

Note: This sounds like something like "proof of knowledge" to me, but since that's not a tag, I'm tagging it as zero-knowledge-proof. Please let me know if this is incorrect.

This was inspired by this but I'm hoping we can get more theoretical answers that answer this specific question.

Answer 1

As you mention, phone numbers have low entropy. Someone who "doesn't know" a phone number at the time of the proof can easily obtain the phone number later. You won't be able to find a non-interactive solution to this problem -- an attacker can always run a dictionary attack and use your "proof" as a test for whether they've found the right number.

For an interactive solution, this problem is often known as the socialist millionaire's problem. Two parties each have a private string, and they want to simply test whether their strings are equal while revealing nothing in the case that the strings are different. The secret strings do not have to have high entropy. You can also achieve this functionality by a symmetric password-authenticated key agreement (PAKE) with explicit mutual authentication / key confirmation. With PAKE, the two participants agree on a random key only if they hold the same secret (low-entropy) "password". Mutual authentication means that the parties are notified if their passwords don't match (instead of simply walking away from the conversation with unrelated keys).

Since these protocols are interactive, it only matters what password (phone number in your case) they use during the interaction. Someone who doesn't know the password only gets one shot to guess it. Using some password $pw$ in the protocol does not leave a way to later test whether a different password $pw'$ was the correct one.