Mozilla also uses this k-anonymity in their implementation of Google Safe Browsing. (As they need to ask Google's server, if the webpage you're visiting or the

Mozilla also uses this k-anonymity in their implementation of Google Safe Browsing. (As they need to ask Google's server, if the webpage you're visiting or the file you're downloading is safe, without telling Google the webpage/file that you are visiting/downloading.) Pretty good documentation on that: https://feeding.cloud.geek.nz/posts/how-safe-browsing-works-in-firefox/ https://feeding.cloud.geek.nz/posts/how-safe-browsing-works-... Another idea here, stolen from Mozilla's implementation, would be to add in a few noise entries when making a request. So, if the user types in their password and the hash evaluates to "2e78f...", you would send off the request for that range and also send off requests for a handful of random, other ranges. In effect, this isn't particularly different from using less symbols to denote the range, e.g. asking for "2e78" instead of "2e78f". But that gives you 16 times as many results, whereas with noise entries, you can fine-tune it to give you for example only 5 times as many results (with 4 noise entries, that is).