Image hash similarity matching possible?

Question

I have the following question:

1. We have two face image files (JPEG), a Matrix of $128\times 128$ with values between 0-255.
2. We would like to hash both image files using a function $f(x, key)$. Where I know $x$, but don't know $key$. The $key$ is being sent by another authority (a).
3. It should not be possible to revert $f(x, key)$ back to the images. Both should be hashes now.
4. Is there a function to compare the similarity of both face images which are now hashed, but not revertable?

Answer 1

Assuming you are talking about a cryptographic hash (as opposed to a hash used for speeding lookups, say), I think you are posing contradictory requirements.

The purpose of a hash is to remove any information from the input values, and essentially look like a random mapping Cryptographic Hash. Thus using it to compare whether 2 inputs are close (similar) in some way should not work.

On the other hand, if you are asking whether you could compare the similarity of 2 faces, you could think of a mapping face->vector of facial measurements, which you could then compare in some vector space definition of distance. But you would not have a 'key' involved. What is the purpose of the key? You want to hide information about the nature of the faces involved? However, I don't think that can work, because then closeness measures will fail.

Answer 2

Disclaimer: cryptography and hashing are not my major areas of expertise.

So, say we have two images $A$ and $B$ with corresponding hashes $h_A$ and $h_B$, respectively. Here, $h_A=f(A,key)$ and $h_B=f(B,key)$, where $f$ is the hashing function.

We also want that $f^{-1}(h_A,[key])$ does not exist, implying that it involves extremely computationally expensive procedures.

Now, we want to know, if there is a function $g(h_A,h_B)$ that is going to measure a similarity between $A$ and $B$ given their hashes $h_A$ and $h_B$. However, that directly contradicts with the requirements on $f^{-1}$ being computationally expensive as it gives me an option to construct $f^{-1}$ procedure by constructing a sequence of more-and-more similar images that will iteratively converge to the original.

So, I would say that even if such function exists, such process severely compromises non-recoverability of the image by having only its hash.

Appendix

(construction of $f^{-1}$):

Input: $h_A$, $f$

Procedure:

1. Take initial image guess $B^{(0)}$ (random, or based on something known)
2. Calculate $h_B^{(0)}$ using $f$
3. Calculate $g(h_A,h_B^{(0)}$)
4. If value of $g$ is less than tolerance -> stop. Otherwise continue.
5. Find new image guess $B^{(1)}$ based on some procedure (genetic algorithms, black-box optimization, etc.). Return to step 2.

Of course, it is hard to find an efficient procedure of finding a new image guess $B^{(i+1)}$ based on $B^{(i)}$ and $g(h_A,h_B^{(i)})$; however, it is still significantly better than trying to crack a good hashing function.