How should I incrementally sign a large set of documents? Say I have a large set (i.e. unordered collection of unique elements) of documents, each of which is around 4KB in size.  I'd like to sign that set with a private key so that anyone can verify the signature with the corresponding public key.

Additionally, I'd like to be able to modify the set by adding or removing elements and generate a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally.  This new signature should be the same as if I had signed the modified set from scratch instead of incrementally.

My first thought was to use a Merkle tree, but such a tree would need to be transmitted, stored, and updated along with the set itself, which is undesirable.  Edit: The overhead of this scheme isn't as severe as I thought, since the signer need not explicitly transmit the Merkle tree and its updates to the verifier(s).  Instead, they just need to agree about how to build and update the tree independently, and in a way that the (amortized) costs of incremental updates are low.

Later, I learned about incremental multiset hash functions and came up with the following scheme:


Compute the SHA256 hashes of each document in the set and combine the hashes using integer multiplication modulo a large prime q.  Call the result H.
Sign H with the private key.
Modify the original set by adding or removing an element, and calculate the new hash H' as H times the SHA256 of the added element (or the inverse of the SHA256 of the removed element) modulo q.
Sign H' with the private key.


Verification proceeds likewise, except that H and H' are verified with the public key in steps 2 and 4, respectively.

Is this scheme secure?  How large would q need to be?

Is there a better option available?
a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally


IMHO this seems to be related to long content, where for a (relatively) small update, the "re-reading" the whole content may be not practical. If you have a large set of smaller documents (4kB) I see no reason why you should treat them as one large content.

I don't know if it will help you, but this is what I've see in one big publishing organization, where they need to ensure integrity of the published (legal) content. 


a hash is computed for each content
there a list of published documents and a composite hash of the hashes of each document (sorted list)
the composite hash is signed 


using a HSM it requires user intervention (manual PIN entry) to sign anything, so they sign only the whole list ensuring integrity on level of the whole list of documents. In this case the list is more or less static (it doesn't change)


  Sign H' with the private key.


effectively that's what the publishing organization is doing - just skipping steps 2 and 3. If a new content is added / removed / updated, just content of the small document is to be hashed and the list of document hashes is updated (and signed) yes, you will need to maintain a sorted list of the documents