Beyond k-anonymity: private password breach checking

You can check whether a password has appeared in a previous data breach at haveibeenpwned.com/passwords. The only issue is, of course, that you have to enter your password to find out if it’s been in a breach.

I built a tool that uses homomorphic encryption to perform these lookups completely privately. Here’s why I built it, and an explanation of how it works.

When “k-anonymity” isn’t enough

HIBP uses a simple technique called “k-anonymity” to avoid sending the full hash of your password to the service. Clients send only the first 20 bits of the hash, and the service returns all the hashes of breached passwords that begin with those bits. The (average) number of hashes returned is called “k”, and the idea is that the service only learns that your password could be one of these k values. In the HIBP case, the API generally sets k = 500. For sufficiently large k, this seems like pretty decent privacy.