I am looking for a way to sign a file, such that someone else can verify that I had this file, even if they only know a hash. I want to prove that I have the full file to someone who only has the hash.

More specifically: Alice has a large file (data). She creates:

  • a hash of data = X
  • a hash of (data + some message (e.g. her ID)) = Y

Both are public. Now Bob only has X (the hash of data), Y, and her ID (but not the data itself). He has to be able to confirm that Y was created using the data, but he should not be able to create Y without access to the data.

I guess what I want can be approximated by deriving a key pair from data and signing the ID with it (X would be the public key, and Y would be the signed ID). The problem with this idea is that someone else could precompute the private key, and pass only that to Alice. She then could compute Y without ever seeing the data. I'd like to require that Alice has to have the full data to create Y.

In particular Alice doesn't need to prove that she still has the data. It suffices to show that she had it at one point in time. The resulting protocol should be non-interactive, i.e. Alice publishes X, Y and ID and then someone can verify that they fit. I also don't need to protect information from Bob. He knows the hash X, and in principle can use it to lookup the data somewhere. It's just really inconvenient for him, so the protocol should allow verification of Y with only X and ID. If he could use the full data and ID to verify Y, then this would be a plain old digital signature.

This scheme I'm looking for seems like something that should already exist and have a name, and I don't want to MacGuyver my own crypto if not neccessary.

  • 1
    $\begingroup$ What you are looking for are Zero Knowledge Proofs. A good explanation is here: cs.rochester.edu/~nelson/courses/cryptology/notes/lecture_17 $\endgroup$ – Daniel Henneberger Dec 19 '14 at 16:58
  • $\begingroup$ @DanielHenneberger: Thanks, I didn't know that term! Although I'm not sure I need something quite as strong as a zero knowledge proof. In my case, Bob isn't prohibited from knowing the data. It's just inconvenient for him to obtain (e.g. because the file is so large). $\endgroup$ – jdm Dec 19 '14 at 17:45
  • $\begingroup$ In that case, can bob repeatedly challenge alice with hashes between bound(s) that bob specifies (hashing a partial file) until bob can be comfortable that alice has the file? It requires more hashes, the hashes can be public without revealing the content of the message (if the hashed content is as long as the hash), and bob will only need a partial file. $\endgroup$ – Daniel Henneberger Dec 19 '14 at 17:54
  • $\begingroup$ @DanielHenneberger: The scheme I was thinking of was non-interactive. Alice publishes her proof and her ID, and Bob can deduce from that and a hash that she had that file. Actually, she might not even have the file anymore the time Bob verifies it. This is probably quite different from the also interesting case where she has to prove that she still has the file. $\endgroup$ – jdm Dec 19 '14 at 19:15
  • $\begingroup$ @DanielHenneberger The link in your first comment is broken, but thanks for posting that. Incredibly useful for me. The correct link is now: cs.rochester.edu/~nelson/courses/csc_cryptography/… $\endgroup$ – Patriot Aug 1 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.