9
$\begingroup$

I am familiar with public key signatures, but I was wondering if there is a method to accomplish the following.

Suppose I publish a file (say a PDF article) on a peer to peer network. How can I generate some sort of public key or signature which will allow one peer to prove to another peer that they have a copy of this file? Something like a signature that treats the full data as a private key, and for which I can put the public key on e.g. my website.

The best method I can come up with is using a hash of the file as the private key in a standard signature scheme. However this is suboptimal because a peer might not actually have a copy of the file anyore, it might just have stored the hash but deleted the file itself.

I am looking for a method that I can wrap up in some challenge-response scheme that allows a peer to prove that they have access to a full copy of the file that belongs to a particular public key.

$\endgroup$
  • 1
    $\begingroup$ @the_one_who_voted_down: please comment and give a statement why you voted down. $\endgroup$ – user27950 Oct 24 '15 at 17:14
  • 2
    $\begingroup$ Just sending a random challenge and performing a hash over the challenge and file should do the trick I think. The hash should however be over a structure that includes the file size to avoid length extension attacks. Note that you would need additional protection against man-in-the-middle (e.g. by using a signature with a private key of the peer). It would also be easy to collude with somebody that holds the document; I don't think that can be avoided. $\endgroup$ – Maarten - reinstate Monica Oct 24 '15 at 18:51
  • $\begingroup$ Can you elaborate a bit? How should the requester verify that H(challenge + file) is correct from the public key? The requester does not have the file. I'm not worried about mitm. $\endgroup$ – Jeroen Oct 24 '15 at 19:02
  • 4
    $\begingroup$ @MaartenBodewes : $\:$ "You can obviously verify it if you have the same file and challenge", but it's far from obvious how the requester can verify it if "The requester does not have the file." $\;\;\;\;$ $\endgroup$ – user991 Oct 24 '15 at 21:04
  • 5
    $\begingroup$ This reminds me to Proofs of Storage (PoS): "Proofs of storage (PoS) are interactive protocols allowing a client to verify that a server faithfully stores a file" $\endgroup$ – cygnusv Oct 27 '15 at 14:33
3
+100
$\begingroup$

Proofs of Storage (PoS) are challenge-response protocols that allow a client to verify that a server is truthfully storing a file. See this paper from Ateniese, Kamara and Katz for an example of PoS.

The basic idea is explained in this quote from that paper:

Viewing the file $\vec f$ as an $n$-dimensional vector, the client begins by tagging each element of $\vec f$ and then sending both $\vec f$ and the vector of tags $\vec t$ to the server. To verify that the server is storing the entire file, the client sends a random challenge vector $\vec c$ and the server returns $\mu =\sum_i c_i f_i$ along with a tag $\tau$, computed using $\vec f$,$\vec t$, and $\vec c$, which is supposed to authenticate this value.

The key aspect here is defining

  1. how the client (or more correctly, the one who uploads the file) create tags $\vec t$,
  2. how the server computes response tag $\tau$,
  3. (and perhaps more importantly), how the server's response can be verified publicly.

I don't have time at the moment to explain the details of these aspects (they are a little bit complicated...I will try to do it later). In any case, it is important to remark that in order to verify a response in the proposal of Ateniese, Kamara and Katz, one does not need the original file. This is a public-key setting, and the private key is only used for tagging the file at the beginning. After that, everything is done using the public key (both the proof of storage and its verification).

There are similar proposals, such as Proofs of Retrievability (PoR) and Provable Data Possession (PDP).

$\endgroup$
  • $\begingroup$ Tried to read the paper but it is unclear to me if can actually be implemented or is merely theoretical proof based on (impractical) homomorphic methods. $\endgroup$ – Jeroen Oct 30 '15 at 21:54

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.