[CloselyChunky]

I think HIBP implements it like this: you hash your email/phone number and send only a prefix of the hash to the server. The server responds with a list of hashes matching the prefix. Now you can check if your hash is in the list. If so, you have been pwned. This way the server never knows which email you are requesting since it only ever sees a part of the hash.