# Can substrings of a long string be efficiently authenticated?

Suppose one has a (strong) shared secret key and wishes to authenticate a very long string in a way that will allow the verifier to verify small substrings without reading much of the stored data and without much storage overhead.

The trivial way to do this is to have a nonce, divide the string into chunks, MAC each chunk along with its position and the nonce, and then MAC the string length along with a special indicator.

Is there any better way to do that?

-
Your trivial solution is open to an attack where the attacker picks chunks from different messages that were authenticated with the same key. So if you go that way you need to include a message specific value in the MAC, losing the ability for incremental updates. – CodesInChaos Jun 7 '13 at 7:33
Very good point. $\:$ – Ricky Demer Jun 7 '13 at 8:00

Here's a better solution, using a Merkle tree.

Suppose the string $S$ is $n$ letters long. Build a binary tree with $n$ leaves, with each leaf corresponding to one letter in the string. Then, each node corresponds to a substring: the $i$th leaf corresponds to the $i$th letter in the string, and an internal node $x$ corresponds to the substring obtained by concatenating all of the leaves that are descendants of $x$. Now, you can store at each node of the tree the MAC of the substring it corresponds to. This is all done in a precomputation.

Once you've precomputed the binary tree, you can authenticate any substring $T$ of $S$ as follows: $T$ can be written as the concatenation of the strings at $O(\lg n)$ nodes in the tree. Therefore, to authenticate $T$, you send the MACs at those nodes. In this way, the authenticator is $O(\lg n)$ in length. This is better than your trivial solution, in terms of the length of the authenticator (as your trivial solution requires an authenticator that is $O(|T|)$ in length). In your storage setting, the length of the authenticator corresponds to the amount of data that must be read from storage to authenticate a particular substring $T$.

If your goal is solely to optimize the length of the authenticator, You might be able to build an even shorter authenticator using set accumulators, though the performance cost would likely be much higher. Given a string $S$, you construct a set of pairs $\langle i, S_i \rangle$, then use a set accumulator construction to sign that set; now it is possible to derive a signature on any subset, such as one corresponding to a substring of consecutive letters from $S$.

Another alternative might be to use hash chaining or MAC chaining. For MAC chaining, you could do the following: let $Y_i = MAC(Y_{i-1} || S_i)$, for each $i$. You can store all of the $Y_i$'s alongside the string. Then, to authenticate a substring $S_{i..j}$ of $S$, you read $Y_{i-1}$, do $j-i$ MAC operations to run forward along the substring, and check that the result matches $Y_j$. Of course, as an engineering optimization, it would be possible to store the $Y_i$ values for only every $k$th index $i$, for some $k$. I don't know whether this will be better in any sense than the other schemes.

You might also be interested in the following research papers:

• Homomorphic signature schemes. Robert Johnson, David Molnar, Dawn Song, and David Wagner. RSA 2002, Cryptographer's Track. See particularly Section 4, redactable signatures.

• Sanitizable Signatures. Giuseppe Ateniese, Daniel H. Chou, Breno de Medeiros, and Gene Tsudik. ESORICS 2005.

Given that you are focusing on stored data, you might also like to look at the line of research on memory integrity checkers, e.g.,

• Checking the correctness of memories. Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. Algorithmica, 12(2/3):225–244, 1994.

• The Complexity of Online Memory Checking. Moni Naor, Guy N. Rothblum. FOCS 2005.

-
I also notice that the "minor enhancement" would require verifying along the subtrees, making it worse the trivial solution. $\:$ – Ricky Demer Jun 7 '13 at 6:39
It's rather unusual to build a tree of MACs. The typical way of doing it is building a tree of hashes and only authenticating the root. – CodesInChaos Jun 7 '13 at 7:31
making leaves smaller than twice the hash size makes little sense. Typically leaves are even bigger than that, for example TTH uses 1KiB leaves. – CodesInChaos Jun 7 '13 at 7:35
I think the best solution would be a MAC chain, rather than a hash chain. $\;$ – Ricky Demer Jun 7 '13 at 23:04
Do you have an example for why a MAC chain requires reading all of the MACs along it? $\:$ I haven't tried thinking through how I imagine the security proof for that would go, but it seems to me like just reading the same MACs as the hashes one would read in a hash chain should work. $\;\;$ – Ricky Demer Jun 8 '13 at 1:47