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.