1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – poncho Dec 12 '11 at 15:59
  • $\begingroup$ @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 $\endgroup$ – curious Dec 12 '11 at 16:33
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ @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 $\endgroup$ – curious Dec 12 '11 at 17:41
  • 2
    $\begingroup$ @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? $\endgroup$ – poncho Dec 12 '11 at 18:18
1
$\begingroup$

This sounds like a similar problem addressed by fuzzy extractors/secure sketches.

A small excerpt from the abstract:

We provide formal definitions and efficient secure techniques for:

• turning noisy information into keys usable for any cryptographic application

• reliably and securely authenticating biometric data.

Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly.

We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application.

A secure sketch produces public information about its input w that does not reveal w , and yet allows exact recovery of w given another value that is close to w . Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them

We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of “closeness” of input data, such as Hamming distance, edit distance, and set difference.

The problem addressed in the paper is how to regularly extract the same key from noisy biometric data such as fingerprint scans. Repeated measurements of such information does not yield identical results, but it is desired to generate the same key to be derived from similar-enough data. This sounds similar to the problem you are/were attempting to address: How to generate a particular output for inputs that are "close enough".

$\endgroup$

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.