Why doesn’t it store a shared secret based on some information from both parties once a contact has been mutually agreed to be shared… then you can quickly do a verification without any interception from outside sources or any information leaking
I was also thinking you might be able to use asymmetric crypto for this, and encrypt the hash + a nonce using your private key, and anyone with your public key can decrypt it and check the hash against the contact list. But this means the potential receiver needs to decrypt with every public key it knows, which for large contact lists might be prohibitively expensive.
Someone has probably devised a more clever way, though.
Same way it does with password manager
Not insurmountable, but it would probably be quite un-Apple-like.