3 ms·

Using a hash function for this is about as good as it's going to be. If we accept the conjecture of the existence of one-way functions, and use a cryptographic

Using a hash function for this is about as good as it's going to be. If we accept the conjecture of the existence of one-way functions, and use a cryptographic sound one-way function and implementation, it's provably the best we can do.

lvh 8y ago
That's not provably the case at all. We can absolutely do better, for reasons the root of this thread raises. If that were true, why isn't SHA256 the state of the art in password storage? Reason: the input space is small enough to enumerate. I posted a comment with an alternative construction plus rationale: https://news.ycombinator.com/item?id=17153329 https://news.ycombinator.com/item?id=17153329
- hvidgaard 8y ago
  I never said anything about SHA256. I talked about one-way functions. The thread model is an adversary that gets unlimited access to the values stored for this purpose, and knows the function used to compute it. He wants to check if a given email is in the set. One-way functions is provably the best way to be able to ask yes/no to the question if this email is in the set with no false answers. I have not said anything about using computationally expensive one-way functions because that does not matter if the function takes 10 seconds to compute. He already knows what emails he wants to check.
  - lvh 8y ago
    You did say hash function. Would you mind jotting down that proof?
    - hvidgaard 8y ago
      A proper cryptographic hash function is a one way function, if they exist. But I'd frame your question the other way around then. You do not want to store the emails in a form that leaks any data. For that we need a compressing function. My (unwritten) assumption was that if the adversary compromise the system to get the data, they'll get any secrets too. This means that a HMAC is no better than a cryptographic hash function. I know that is quite possible to create a system where this would be significantly harder than just a DB dump. But that is both significantly more difficult, and expensive. I'll admit that the formulation "provable the best we can do" should've had a big fat asterisk with the disclaimer about the threat model. So, if an attacker have the data set and secrets, and wants to compute if a particular input is a member of this set. Can you do better than a cryptographic hash function?
      - lvh 8y ago
        Can you write down in pseudocode exactly what you're suggesting? As in db.write(sha256(email)) or whatever.

lvh 8y ago

That's not provably the case at all. We can absolutely do better, for reasons the root of this thread raises. If that were true, why isn't SHA256 the state of the art in password storage? Reason: the input space is small enough to enumerate. I posted a comment with an alternative construction plus rationale: https://news.ycombinator.com/item?id=17153329 https://news.ycombinator.com/item?id=17153329

hvidgaard 8y ago
I never said anything about SHA256. I talked about one-way functions. The thread model is an adversary that gets unlimited access to the values stored for this purpose, and knows the function used to compute it. He wants to check if a given email is in the set. One-way functions is provably the best way to be able to ask yes/no to the question if this email is in the set with no false answers. I have not said anything about using computationally expensive one-way functions because that does not matter if the function takes 10 seconds to compute. He already knows what emails he wants to check.
- lvh 8y ago
  You did say hash function. Would you mind jotting down that proof?
  - hvidgaard 8y ago
    A proper cryptographic hash function is a one way function, if they exist. But I'd frame your question the other way around then. You do not want to store the emails in a form that leaks any data. For that we need a compressing function. My (unwritten) assumption was that if the adversary compromise the system to get the data, they'll get any secrets too. This means that a HMAC is no better than a cryptographic hash function. I know that is quite possible to create a system where this would be significantly harder than just a DB dump. But that is both significantly more difficult, and expensive. I'll admit that the formulation "provable the best we can do" should've had a big fat asterisk with the disclaimer about the threat model. So, if an attacker have the data set and secrets, and wants to compute if a particular input is a member of this set. Can you do better than a cryptographic hash function?
    - lvh 8y ago
      Can you write down in pseudocode exactly what you're suggesting? As in db.write(sha256(email)) or whatever.