Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote -1 down vote favorite

I do not know if the question lies exactly in that field but i'll give it a try unless rejection. I want to study methods of applying LSH functions to feet in a specific area of digest values. Briefly i would like to control the results of hash functions such as "similar" inputs (similarity is defined by an lsh algorithm given a distance metric (i.e:hamming distance)) fall to a specific value. That is i want to control the output of lsh to result in a specific range of values.

share|improve this question
Is your question about existing Locality-sensitive hashing functions? Or, is it how to take a Cryptographical hash function, and use it to create a Locality-sensitive hash function? – poncho Dec 12 '11 at 15:59
@poncho The second one but also how i can control the output range. I.e: i want to have such outputs to a specific range of values – curious Dec 12 '11 at 16:33

1 Answer

up vote 1 down vote

Well, if the question is 'how do we select inputs to a cryptographical hash function so that the outputs are within a specific range', well, you're pretty much limited to:

  • Rejection methods -- that is, you hash the input with some salt, and if the resulting hash value isn't in the range you want, you keep on trying different salt values until it is. For example, if you want the MSBit of the hash to be zero, you keep on trying different salt values until you find a hash with has an MSBit of zero.

  • Postprocessing methods -- that is, you hash the input as usual, and then map it into the range you want. For example,if you want the MSBit of the hash to be zero, you simply take the result of the crpytographical hash function, and set the MSBit to zero.

If you're looking for a more efficient method of selecting hash inputs to constrict the hash output, well, they're not known to exist for cryptographical hash functions. In fact, if there was a large, easily computable subset of inputs that generated a biased hash output, that would imply a cryptographical weakness of the hash function. For example, to find a collision in the hash function, one could just take inputs from the subset, and hash those; if there was a bias in the hash outputs, one would find a collision with probability $0.5$ with a number of hashes strictly less than $1.17741 \cdot 2^{N/2}$ attempts (where $N$ is the size of the hash function); this is a weakness (although a small one if the bias is small, or it takes a large amount of computation to find elements in the subset).

share|improve this answer
@Lets say that i have point1 p1 and point 2 p2.According to an LSH function which i do not care, the probability P1 is very high to belong to the same bucket after applying this LSH as such P[LSH(p1)==LSH(p2)] >P1 if those to points are close together at some fraction.So what i want is to direct the output of inputs which are "close" together to a specifiv output – curious Dec 12 '11 at 17:41
2  
@curious: Well, if you want similar points to hash to the same value with high probability, the obvious thing to do is to find a mapping function $map$ such that $P[map(p1)==map(p2)]>P1$, and then define $LSH(p) = Hash(map(p))$. However, I suspect that doesn't answer your question. What is the underlying problem you're trying to solve? – poncho Dec 12 '11 at 18:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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