In order to provide subscribers of this service with complete anonymity over the email addresses being searched for, the only data passed to the API is the first six characters of the SHA-1 hash of the full email address.
I take it the k-anonymity thing essentially "chunks" your database. So rather than returning one (identifying) result for one email address, you instead take the first few characters of its hash, and return a few hundred results corresponding to all the emails whose hashes share the same prefix. (A bit like asking for the "L-N" section of the phone book instead of asking for a single line).
I'd be curious what sort of attack vectors or "side channels" you wargammed out when coming up with the scheme - eg. if a block wound up mostly comprised of email domains (providers) popular in one part of the world, and only a few from another geography, then you might be able to infer identity via timezones based on time of day queries come in.