I am looking for a hash function which is invariant under small changes.

E.g., if I have two strings MyString and MySttring which slightly differ, their hash values should only differ slightly as well.

Actually, this is the opposite of the normal concept of a hash functions (Avalanche effect) where even slight changes in the input lead to big changes in the output.

Does any one know of such a concept or a hash function? (It should not be the identity function ;))

Background: I want to store personal data (name, surname, date of birth). Due to data privacy laws, it is not allow to store the data in clear text. So, I need to hash it. There might be typing errors or OCR errors when storing the data. So, two hash values of the same person might differ. But they should only differ a little, so I know that the input data must have been very similar.

  • $\begingroup$ There are laws about breaching the security (it is country dependent, you have to check it), but if some protection is not considered secure, there is no breach at all. I also have to store personal data, but if I e.g. use Rot13 - attempt to break it would not be considered malicious act and I would be liable for bad storage of private data. $\endgroup$ – Evil Apr 25 '16 at 16:19
  • $\begingroup$ This problem is quite delicate and the answer will depend on the details of what you're trying to achieve. (1) What queries do you want to support? Do you want to look for approximate matches based on name? On last name? On date of birth? (2) What security/privacy properties do you want it to have? "Not stored in cleartext" is not a useful security property (ROT13 satisfies it, but is probably useless). (3) Can you use a keyed hash, using a secret key? Can you edit your question to clarify? $\endgroup$ – D.W. Apr 26 '16 at 6:41

Use locality-sensitive hashing. Make sure you're not breaking the law.

  • 2
    $\begingroup$ That's a tempting-sound approach, but sadly, I suspect it will be completely insecure for the use cases that the poster has in mind. In particular, I don't think it'll provide any better protection than storing the data in cleartext, for several reasons (LSH's aren't designed for privacy; if the space is enumerable, dictionary attacks will probably break this and allow to recover the original data, for the parameter settings we're likely to see in practice). So I think the problem is harder than it sounds, and might not be solvable in the stated form. $\endgroup$ – D.W. Apr 26 '16 at 6:42
  • $\begingroup$ Thank you, locality-sensitive hashing is a really good hint. I will check how I can build a good local-sensitive hash function for my problem. @D.W. is right, LSH is quite insecure. But I assume it does not need to be very secure. I will need to check the data privacy laws. They prohibit to store the data in plain text, but they might not measurably state how strong a hash function must be. $\endgroup$ – JavAlex Apr 28 '16 at 14:31
  • $\begingroup$ A law that prohibits plain text but does not require one-way hashing is best implemented by full disk encryption. $\endgroup$ – Joshua Apr 28 '16 at 21:29
  • $\begingroup$ @JavAlex, I agree with Joshua. Also you should be aware that hashing (especially LSH) might be plaintext-equivalent, so if plaintext is prohibited, LSH might be effectively prohibited or might create a compliance risk. If you talk to lawyers about this, ask them whether a plaintext-equivalent storage format is any better than plaintext from a legal/compliance perspective. My suspicion is that LSH will be no better than plaintext and thus if plaintext is prohibited then I'm not sure LSH will be any better. $\endgroup$ – D.W. Apr 29 '16 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.