[Cryptography] Secure transfer of subsequences

Jerry Leichter leichter at lrw.com
Thu Oct 16 07:43:14 EDT 2014

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.

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
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.)

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.

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.
                                                        -- Jerry

More information about the cryptography mailing list