4
$\begingroup$

Given a message $m$ that consists of several parts. we want to be able to verify individual parts or a combination thereof.

The simplest solution is independently signing each part. But since asymmetric signatures are relatively expensive to compute and verify, that might not be the most efficient approach.

Is there an efficient and faster alternative approach for this problem?

$\endgroup$
4
  • 1
    $\begingroup$ Build a hash tree of the parts, record the intermediate hashes and the sign the root. $\endgroup$
    – otus
    Sep 17, 2015 at 15:37
  • $\begingroup$ You can use aggregate signatures or aggregate MACs. $\endgroup$ Sep 17, 2015 at 18:13
  • $\begingroup$ Please do not delete your question after receiving an answer. $\endgroup$ Sep 18, 2015 at 10:51
  • $\begingroup$ Please use the comment form if you need to ask for clarification, rather than editing either the question or answer. If you have a followup question that can stand on its own, you can ask a new question. $\endgroup$
    – otus
    Sep 18, 2015 at 12:52

1 Answer 1

5
$\begingroup$

The standard way to do this is with a hash list. That is, you would hash each of the messages $m_i$ to produce a hash $h_i = H(m_i)$, and then combine all the hashes and hash them to obtain a master hash $h = H(h_0 \| h_1 \| h_2 \| \dots \| h_n)$. Finally, you can e.g. digitally sign the master hash to prove that the hash, and by extension all the messages, were sent by you.

(You can, of course, also use a keyed MAC instead of a hash for this, if you want.)

Hash lists can also be generalized into hash trees. For very large numbers of messages, hash trees are potentially more efficient, since they can let you verify the integrity of an individual message without having to load and hash together all the intermediate hashes $h_i$. They're also more efficient to update, if your messages may sometimes change. (That said, if your messages don't change, and you know you're going to want to verify all of them anyway, a simple hash list will have somewhat less overhead than a more complex hash tree.)

Of course, you could also just simply hash the whole combined message $m = (m_0, m_1, \dotsc, m_n)$ at once, without bothering with hash lists or trees. But the advantage of hash lists or trees is that they let you verify the individual message parts without loading and hashing the whole combined message.

$\endgroup$
1
  • $\begingroup$ @Mr.Vendetta: To verify message part $m_i$, given the master hash $h$, you first load the hash list $(h_0, h_1, \dots, h_n)$, check that $H(h_0 \| h_1 \| \dots \| h_n) = h$, and then check that $H(m_i) = h_i$. That's a lot faster than loading and hashing the entire message $m = (m_0, m_1, \dots, m_n)$. $\endgroup$ Sep 26, 2015 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.