<p dir="ltr"><br>
Den 16 okt 2014 19:36 skrev "Jerry Leichter" <<a href="mailto:leichter@lrw.com">leichter@lrw.com</a>>:<br>
><br>
> Suppose Alice has a sequence of bits S and wishes to securely transfer them to Bob, in the sense that Bob can prove that the bits S' he receives are actually the same as S.  Depending on what we mean by "prove", either a keyed MAC or a signature will do the trick.<br>
><br>
> But suppose S is very large, and Bob is only interested some subsequence T of S.  (That is, there is a sequence i0 < i1 < ... < ik such that<br>
> T == S[i0] || S[i1] || ... || S[ik].)   Again, Bob wishes to be able to prove that T is indeed of this form.  Obviously, Bob can accomplish this by transferring all of S and then constructing T, but if |T| << |S|, this is very wasteful.  Bob would like to do this by transferring a number of bits "not much larger" than |T|.  (If the subsequence really is arbitrary, the cost of sending the i's might dominate.  That's not the interesting part of the problem, and can be ignored.)<br>
><br>
> Does anyone know of solutions to problems of this sort?  For the case that the subsequences consist of a small number of long contiguous runs of bits, using a tree hash on substrings of contiguous bits of S might work.  I'm guessing that *some* constraints on S are necessary, but who knows.<br>
><br>
> In general form, the closest thing I've seen to this is "proofs of storage".  In terms of this problem, Bob sent S to Alice, who promises to keep it stored; Bob will later ask for something small - T might be an example, but is not enough - that Alice will be unable to produce unless she has, indeed, retained all of S. There are some clever ideas here that might be adapted, but I haven't kept up with the literature.</p>
<p dir="ltr">The only thing I can think of you haven't mentioned already is Zero-knowledge proofs, showing that what you provided really is exactly the same as the bits in range X to Y within the file with the hash Z (a less formal way to describe what you explained in your second paragraph). These are still very inefficient to generate, OTOH the proofs can be constant size and quick to verify. </p>
<p dir="ltr">I would think tree hashes are the simplest practical solution.</p>