7
$\begingroup$

Suppose that $s_1$ and $s_2$ are two stings that have a small hamming distance. Is there a preimage resistant "hash" function ($H$) that can map them to the same value i.e., $H(s_1) = H(s_2)$?

$\endgroup$
  • 5
    $\begingroup$ I don't see the relationship with cryptography. In fact, in cryptography, the property you want is often a property we don't want. Perhaps there is a better site for this questions? $\endgroup$ – mikeazo Aug 13 '15 at 14:47
  • 2
    $\begingroup$ And, it's easy to show that the only hash function where $H(s_1) = H(s_2)$ holds consistently is one which is constant (for a specific input length). So, assuming that a constant output isn't the answer you're looking for, how often must $H(s_1) = H(s_2)$ hold? $\endgroup$ – poncho Aug 13 '15 at 14:50
  • 2
    $\begingroup$ Could you use a fuzzy extractor? It likely doesn't have some of the formal security features of a hash. What security properties do you absolutely need? $\endgroup$ – mikeazo Aug 13 '15 at 16:13
  • 1
    $\begingroup$ @mikeazo is right, that paper starts off by mentioning biometric templates, where this issue is well studied. Reading and understanding that paper would probably be a good start. $\endgroup$ – Maarten Bodewes Aug 13 '15 at 16:42
  • 1
    $\begingroup$ @JanLeo please edit question stating the no communication constraint and a more explicit statement of your goals. Presumably the server holds a set of hashes, and your goal is some sort of encrypted "similarity search" $\endgroup$ – kodlu Aug 13 '15 at 20:54
4
$\begingroup$

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could go from one string to the next and it would always have to map to the same value.) So this does not make any sense.

I think, like you also suggest, that an error correction code might be what you want. Such a code is defined by a set of codewords $\{c_1,...,c_n\}$ that are at a certain (Hamming) distance from each other, and around each codeword $c_i$ there is a Hamming sphere $S_i$ that contains those words that are closer to $c_i$ than to any other codeword. A perfect decoder will map any word to the closest codeword, so that it will map any word in $S_i$ to $c_i$. So if you have two words in the same Hamming sphere $S_i$, your decoder will decode them to the same codeword $c_i$. (You can easily generate such words by taking $c_i$ and randomly flipping a number of bits.)

This is not exactly the hash function you wanted, but I think this is as good as it gets if you want to map two words at a small Hamming distance from each other to the same value.

$\endgroup$
  • $\begingroup$ The question is can I run decoder on any inputs? Suppose I have two files with a small hamming distance, can I run decoder them and get the same output? I thought the codewords should follow some format (e.g., hamming code). $\endgroup$ – Jan Leo Aug 14 '15 at 3:43
  • 1
    $\begingroup$ @Jan Leo: In an error correction code, it's not the distance between the words (files), but the closeness to a codeword that matters. For example when you have a repetition code with the codewords 00000 and 11111, then a decoder will map all the words with less then three 1 bits to 00000 and ever word with at least three 1 bits to 11111. So it can also happen the words on the border between two codewords are close to each other, but map to different codewords. E.g., dec(10100)=00000; dec(11100)=11111. $\endgroup$ – Chris Aug 14 '15 at 7:44
  • $\begingroup$ Then two similar files may map to different words, right? $\endgroup$ – Jan Leo Aug 14 '15 at 8:06
  • $\begingroup$ @Jan Leo: Yes. Which words will map to the same codeword depends on the structure of your code (= your set of codewords). PS: In error correction, you typically consider a space that contains words (e.g. 5 bit words like in the previous example) and then some of these are codewords. There is in fact no notion of 'files'; I just reused this term because you used it in your question. $\endgroup$ – Chris Aug 14 '15 at 8:24
  • $\begingroup$ @Chris: you're right and this is the crux of the problem. $\endgroup$ – kodlu Aug 14 '15 at 14:30
3
$\begingroup$

You could combine locality sensitive hashing ($LSH$) with a one-way function $H$. E.g. you could do $H(LSH(x))$ for data $x$. This is one-way and has the feature that two values that fulfill some locality condition map to the same value. Compared to the coding approach, it has the advantage that it works for any domain element. However, locality here is defined in terms of subspaces of the domain. Hence, the tricky part is probably for you to figure out what kind of LSH you need.

The one-wayness of this construction can be shown by reduction as a preimage $y$ of $LSH \circ H$ gives a preimage $y'=LSH(y)$ of $H$.

$\endgroup$
  • $\begingroup$ As far as I know, for similar inputs, LSH will lead to similar outputs, instead of the same output. Then running a one-way function on that will lead to a totally different output. Isn't it? $\endgroup$ – Jan Leo Sep 3 '15 at 17:28
  • $\begingroup$ Simply read the linked Wikipedia article... $\endgroup$ – mephisto Sep 3 '15 at 21:16
  • $\begingroup$ Thanks for this answer, it's what I was looking for. $\endgroup$ – SColvin Aug 31 at 12:07

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.