4
$\begingroup$

Assume that Alice has a file $F$ which she is going to send, in encrypted form to Bob. Alice possesses $F$ and an encryption key $K$. She sends to Bob the encryption of $F$ using $K$, $E(F,K)$ as well as a compact message authentication code which could be the hash of the file $H = {\rm hash}(F)$, which is used as a unique blinded identifier of the file. It's assumed that multiple users may have the same file, encrypted with different keys, and we wish to detect that they are the same by virtue of $H$ being the same, but Bob needs to know that $H$ matches $F$ without having $F$ unencrypted.

Does there exist any kind of proof that the hash $H$ (or other compact MAC) corresponds to the file $F$? The hashing/MAC algorithm and encryption algorithm (symmetric, asymmetric, homomorphic) are secondary to being able to prove this.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Who is the proof to? Bob or the other users that may have the same file? Also, what is the threat model? Who is the bad guy? $\endgroup$
    – mikeazo
    Jan 6, 2016 at 17:21
  • $\begingroup$ The proof is to Bob. The threat model is that Alice may upload a file F that doesn't satisfy $H={\rm hash}(F)$. If Alice uploaded $\{E(F,K), H\}$ without such a proof, she could engineer apparent collisions of encrypted files, or submit hashes that are unrelated to the file. The goal is to determine when the files from different users are the same, without requiring them to divulge the file itself or encryption keys. $\endgroup$
    – Bob McElrath
    Jan 6, 2016 at 17:38
  • $\begingroup$ @BobMcElrath But that isn't the whole threat model. Presumably Bob shouldn't learn the plaintext $F$, right? What stops Bob from learning $F$ by virtue of knowing the hash? This is the case when $F$ is drawn from a known set of some finite bound, such as public files or small files. Ex: the protocol is weak for any 4 byte file and youtube videos. $\endgroup$
    – Thomas M. DuBuisson
    Jan 6, 2016 at 20:28
  • $\begingroup$ @ThomasM.DuBuisson correct, Bob should not learn $F$. Let's assume $F$ is appropriately salted to mitigate a brute force attack. FWIW All I care about is identifying that the file is the same, so one might consider a different MAC than a simple hash. $\endgroup$
    – Bob McElrath
    Jan 6, 2016 at 21:57

3 Answers 3

Reset to default
3
$\begingroup$

If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some $F$ that hashes to $H$. $K$ can be trivially derived from $F$ and $E(K, F)$ by xor-ing.

An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of $H(F)$ - would go something like this:

You need to use a partially homomorphic hash such that $H(A+B) = H(A) \oplus H(B)$ for some composition operation on each domain. An example might be to add/xor the pre-images and use scalar multiplication of an elliptic curve base point as your hashing function - though note for an arbitrary length message this is going to be magnitudes slower than a traditional cryptographic hash function.

In a single trial in the proof Alice generates a one-time pad - $P$ - and commits to $H(P)$. Bob calculates $H(F+P) = H(F) \oplus H(P)$. He can challenge Alice to reveal either $P$ or $F+P$. Each trial halves the probability that Alice is cheating.

You can turn this into a non-interactive proof by Fiat-Shamir. It's not very succinct however, the proof ends up being many times longer than $F$.

I guess with a homomorphic DRBG you could extend the proof to show that Alice knows a stream cipher key $K$ that defines the tranformation $F \rightarrow E(K, F)$. This would improve the succinctness of the proof as well as being a closer match for what you asked for.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good answer, I think you're giving the same answer as this hash preimage question: crypto.stackexchange.com/questions/1767/… and perhaps a better answer to my question is to use some kind of homomorphic signature rather than a block cipher hash. I'll clarify my question above to specify that $H$ can be any kind of message authentication code. $\endgroup$
    – Bob McElrath
    Jan 8, 2016 at 15:37
2
$\begingroup$

Do you allow Bob to ask all the users having $F$ to encrypt, then to upload the file with a same secret key deriving from $F$ ?

Here would be the principle of the tweaked protocol : all the users must encrypt the file with the same key which depends on the file (calculated via another hash). The key would be a kind of shared key, but which can only decrypt the file $F$. Bob would calculate the hash of the first file he receives, store it, and then calculate the hash of all the new received encrypted files to check whether or not they match the initial hash.

Example of derived symetric key : $H(F | 1)$ (the bit "one" is added at the end of the file). In this construction the unique identifier of the file would be the hash of the - unique - encrypted file .

Improve this answer
$\endgroup$
2
  • $\begingroup$ No, users do not know each other and cannot communicate, nor can they have the same secret key. Also since Bob does not receive $F$ he cannot compute these hashes or the key, he should have only $\{E(F,K), H\}$. The point is to prove to Bob that the file has a given hash, so that the same file encrypted by different users with different keys can be identified to be the same file (without knowing what that file is). $\endgroup$
    – Bob McElrath
    Jan 6, 2016 at 22:01
  • $\begingroup$ Fair enough, in fact in my protocol the users don't know each other either. They just commit to produce a particular encrypted file, encrypted with a particular symetric key which can be determined only if one knows the original file. Eventually only Bob is able to verify that all the users produced the same ciphertext though this protocol. $\endgroup$
    – Fraktal
    Jan 7, 2016 at 18:11
1
$\begingroup$

You could use non-interactive zero-knowedge proofs along with functional encryption. With functional encryption, you could give a secret key for the hash function. You would encrypt the file with the FE scheme. However FE schemes are not practical. You can also solve the problem with functional encryption for inner products. You use the scheme to compute the function Ax where x is a plaintext vector (encoded to have short entries). Now Ax is the GGH hash function and it can be seen be one-way and collision-resistant based on the hardness of the shortest vector in a certain type of lattice. This is an interesting problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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