3
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Is $x$ the input image you want to hash? And what assumptions can we make about the key? $\endgroup$ – spektr May 9 '18 at 10:38
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.