4 ms·

My background is in EE, so forgive me if this is a stupid question. Are there any cryptographic hash functions which support a closeness metric? Having written

My background is in EE, so forgive me if this is a stupid question. Are there any cryptographic hash functions which support a closeness metric? Having written that out, it seems that such a thing would be contradictory, as to be able to compute their closeness would give information away about their nature and thus make them possibly reversible.

MattSteelblade 10y ago
That is correct, it would be contradictory. Fingerprints are un-hashable in that sense.
JadeNB 10y ago
I am also no expert, but I am not sure that I agree with MattSteelblade (https://news.ycombinator.com/item?id=11550845 https://news.ycombinator.com/item?id=11550845). There is certainly such a thing as homomorphic encryption (https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption), which allows one to perform transformations on encrypted text without being able to decrypt it. As long as one of the transformations that can be performed is a measure of closeness (which is certainly the case for fully homomorphic encryption (https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_h... )), and as long as you know the ciphertext of the possible numerical responses, then you can read off closeness without being able to decrypt the hash. The emphasised bit is a drawback, but it demonstrates the theoretical possibility; and, although I don't know of an implementation, nor do I see anything inherently contradictory about a (non-reversible) system designed intentionally to reveal closeness information.
taejo 10y ago
What you're looking for are "fuzzy extractors".
joefkelley 10y ago
Off the top of my head, it would at best severely weaken the strength of the hash function. Instead of having to brute force to find an output that matches exactly, you would only have to brute force for one that was sufficiently close, then use a greedy search to move from there to the actual key. The stronger you make the "closeness" guarantee, the weaker the function becomes to this kind of thing.
warkdarrior 10y ago
Locality-sensitive hashing might be what you want, but it is not a cryptographically strong construct.

MattSteelblade 10y ago

That is correct, it would be contradictory. Fingerprints are un-hashable in that sense.

JadeNB 10y ago

I am also no expert, but I am not sure that I agree with MattSteelblade (https://news.ycombinator.com/item?id=11550845 https://news.ycombinator.com/item?id=11550845). There is certainly such a thing as homomorphic encryption (https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption), which allows one to perform transformations on encrypted text without being able to decrypt it. As long as one of the transformations that can be performed is a measure of closeness (which is certainly the case for fully homomorphic encryption (https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_h... )), and as long as you know the ciphertext of the possible numerical responses, then you can read off closeness without being able to decrypt the hash. The emphasised bit is a drawback, but it demonstrates the theoretical possibility; and, although I don't know of an implementation, nor do I see anything inherently contradictory about a (non-reversible) system designed intentionally to reveal closeness information.

taejo 10y ago

What you're looking for are "fuzzy extractors".

joefkelley 10y ago

Off the top of my head, it would at best severely weaken the strength of the hash function. Instead of having to brute force to find an output that matches exactly, you would only have to brute force for one that was sufficiently close, then use a greedy search to move from there to the actual key. The stronger you make the "closeness" guarantee, the weaker the function becomes to this kind of thing.

warkdarrior 10y ago

Locality-sensitive hashing might be what you want, but it is not a cryptographically strong construct.