I want to mention that such a feature CAN be implemented in a privacy preserving way using the K-anonymity model (it is currently being used by haveibeenpwned.c

I want to mention that such a feature CAN be implemented in a privacy preserving way using the K-anonymity model (it is currently being used by haveibeenpwned.com). In short you can sent the first 3 bytes of the hash to the server and the server would reply with all the full hashes that match at which point you just do a lookup in the response.