I have some website where I want people who have no account to allow opt-out from receiving emails. This could be achieved by just storing their email adresses in a "blacklist" table and look them up prior to sending out some mail.
To comply with data protection and for security reasons I want so store the emails encrypted/hashed in some way. I thought of simple md5(password), but that is too easy to crack/bruteforce. Second thought is to use bcrypt/scrypt to have a slow hashing function, but they have some salt for each entry, so I would need to hash the mail for every entry to compare. This would be rather slow with a runtime of O(n) with n being the number of blacklisted entries.
Is there any other way to have the mails securely hashed to do a quick comparison with the blacklist? It should be O(1) runtime, no matter how many entries there are.
You can use any key-derivation function, like PBKDF2 or even BCrypt/SCrypt.
Since the hashes must be searchable, one cannot use unique random salts. Instead we can pass a static salt, which acts as a server side key.
With the KDF we can benefit from the cost factor which slows down brute-forcing considerably. The static salt/key prevents brute-forcing if the attacker has access to the database, but no privileges on the server (the key remains secret), this is a typical scenario of SQL-injection. Just make sure the salt is not part of the hash-string, most implementations of BCrypt will do this, because they are designed for password hashing.
The problem with this approach is, that it is not adaptable to future faster hardware. But even if the KDF is just needing some milliseconds, this is way better than using a simple hash. Maybe you should ask this on Information Security, they may know a better alternative.