The solution will have to piggy back off pubkeys.
Discussion
How are you going to lookup people based on their number with that approach? 🐶🐾🤔
If user receives pubkey+phone private key. They can take pubkey from user + address book to generate private keys and if there is a private key match they know they are friends. It would require call it pubkeyphone private key for user A to share.
If user B can take pubkey + any address in contacts, hash it and generate the same pubkeyphone private key and match it to user A they know they are friends.
(Phone number share)
User A wants to share phone number.
Private key of User A is generated using Npub+ phone number.
User A shares that private key.
User B wants to see if they are friends with anyone.
User B takes friend list Npub + phone number list and hashes it (might be lots of random guessing but possible)
If user B generates the same key as user A shared they know they are friends.