I'd like to add that (IIUC) this scheme doesn't require Google to retain plaintext credentials or even password hashes. (They still might of course, but they do

I'd like to add that (IIUC) this scheme doesn't require Google to retain plaintext credentials or even password hashes. (They still might of course, but they don't have to.) If implemented as described in the linked paper, it only requires storing the hash of the combined username-password (in encrypted form). It's difficult to imagine a less useful form from the perspective of an adversary. Regarding costs, the one-time hash performed on intake is indeed computationally expensive. However, for queries the only cryptographic operation required is a single elliptic curve computation (using secp224r1) on the hashed record sent by the client. Computationally, that should be in the same ballpark as establishing a single TLS connection. The primary expense (detailed in the paper) is bandwidth, on account of sending out an entire hash bucket with each response. The analysis in the paper assumes a 2 byte prefix, but they're using 3 bytes here to reduce bandwidth at the expense of privacy; for every query made, they have to send back ~250 values instead of just one.