I have a problem that I'll simplify here. Let's say I want to store a table of {person, fav color}. Only, I don't want anyone to ever be able to look up a person't favorite color; the only thing someone should be able to do is group people if their favorite color is exactly the same (not just merely similar). The obvious solution would be to not store the favorite color, but {person, hash(fav color)} using a good crypto hash(). Only, turns out that there is a very small list of color names, and anyone can easily enumerate all the colors, and compute the hash thereby reversing the hash and extracting the fav color for a person. I can stretch, but that makes computing hash() slow -- it needs to be a fast operation.

Basically, I have input x chosen from a small, easily enumerated space. I want a fast-to-compute function H that will guarantee x==y <=> H(x)==H(y) (with high probability). But knowing H(x) does not allow one to easily compute x.

I'm creating a secret key, and using H(x) as Hmac-Sha256(x, key).

Does this work? Is there a better, more accepted way of doing this?

  • 3
    $\begingroup$ I don't think what you are looking for is possible, you probably need encryption for this, not hashing. Also salting a hash does not slow it down $\endgroup$ – Richie Frame Aug 22 '18 at 23:43
  • $\begingroup$ @RichieFrame I mean to say stretch, not self. Fixed. Encryption doesn't look like the right solution: I'd have to use a fixed IV for my comparison requirement; which means that I will leak information when prefixes are similar. $\endgroup$ – Manish Aug 23 '18 at 1:41
  • $\begingroup$ What if I hire some people to infiltrate your color social network? One of whom has agreed to say their favorite color is red, another who will say orange, one yellow, one green, one blue, ... $\endgroup$ – Future Security Aug 23 '18 at 2:26
  • $\begingroup$ @MaartenBodewes, when using encryption with a fixed IV, common prefixes in the plaintext result in common prefixes in the cipher text. $\endgroup$ – Manish Aug 23 '18 at 5:13
  • $\begingroup$ @FutureSecurity :) You may be taking the example too literally. As I said in the first sentence, I'm simplifying the scenario to highlight only the problem I'm looking to solve. In my case, the 'fav color' value is not under control of the user. $\endgroup$ – Manish Aug 23 '18 at 5:15

Your Answer

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

Browse other questions tagged or ask your own question.