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.