# [Cryptography] Secure transfer of subsequences

Natanael natanael.l at gmail.com
Thu Oct 16 14:07:37 EDT 2014

```Den 16 okt 2014 19:36 skrev "Jerry Leichter" <leichter at lrw.com>:
>
> 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.

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.

I would think tree hashes are the simplest practical solution.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141016/96b3ea62/attachment.html>
```