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?