$M$ (not public) is hashed with a hash function $\text{H}$ that includes a variable $T_1$ (public), giving $C_1$ (public). The same $M$ (not public) is hashed with the same hash function with another variable $T_2$ (public), giving $C_2$ (public).

Knowing the variables, $C_2$ can be verified to be from the same data as $C_1$.

Is there a hash function $\text{H}(M + T_1) = C_1$ that relates to $\text{H}(M + T_2) = C_2$ in such a way that, knowing $T_1, T_2, C_1, C_2$, and with no knowledge of $M$, it can be verified whether both use the same $M$?

  • $\begingroup$ For things like SHA* etc., without having original data and timestamps, and the timestamp and data before hasing were just concatenated etc.? Then no. $\endgroup$ – deviantfan Jul 24 '18 at 22:18
  • $\begingroup$ not necessarily sha*, just if there exists anything whatsoever. the original data is not available, the timestamps are known. $\endgroup$ – d29d4 Jul 24 '18 at 22:21
  • $\begingroup$ I think I can guess what you're trying to do. You're trying to store salted and hashed passwords and authenticate a user without ever receiving / decrypting / being able to read the password. You want to pass the user new salts and then have them send you something other than the password but which proves they have the password. I had the exact same idea not too long ago. I posted it on infosecSE but it really is better suited for here. I'm currently refining the idea a bit but plan to post it on cryptoSE soon. security.stackexchange.com/questions/189991/… $\endgroup$ – IIAOPSW Jul 24 '18 at 23:56

A SNARK proof could be generated and then verified for a circuit with public input $T_1, C_1, T_2, C_2$ and witness (private input of proving party) $M$ for a popular hash function like SHA256 with libsnark. Original data $M$ is not an input while proof verification. Zcash design would be a good example of this technique.

| improve this answer | |
  • $\begingroup$ The idea was to have a proof-of-data-possession where each host gets an encrypted file, they then verify (monthly) the storage by doing a proof H(Ms+T2)=C2, at time t2 on the signed file Ms, with homomorphic computation so that c2 can be decrypted to what it would be for the original file M, and verified to the hash of the original file H(M+T1)=C1 at time t1. The host then reencrypts their file (and submits the public key while verifying the previous proof), and repeats the process every month. $\endgroup$ – d29d4 Jul 26 '18 at 0:10
  • $\begingroup$ Please be careful about exactly what is doable. "Decrypting a hash" might need a re-wording. SNARK examples might be helpful. $\endgroup$ – Vadym Fedyukovych Jul 26 '18 at 12:07
  • $\begingroup$ seems like there would be homomorphic computation where if you encrypt a file, then do computations on it and then decrypt it, the result is the same as if you do the same computations on the original file. $\endgroup$ – d29d4 Jul 26 '18 at 12:49

This is not probably what you had in mind; but this is easy to achieve with a slight expansion.

Let us assume we have a private, public pair, with private key $P$, and public $K$. We basically consider $P$ to your $M$, and take $K$ to be part of the public knowledge of the verification of the hash.

Then $H(M+X)$ is defined to be $\textrm{Sign}(P,\textrm{Hash}(X))$ for any desired hash algorithm. Let $C_i=\textrm{Sign}(P, \textrm{Hash}(T_i))$. Given the public $K$, one can then verify the legality of each $C_i$ (and of course, for publicly known hash-function, one can also calculate the hash of $T_i$ directly).

| improve this answer | |

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.