9
$\begingroup$

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:

  1. 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.
  2. Sign H with the private key.
  3. 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.
  4. 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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Do you have a particular signature scheme in mind? $\endgroup$
    – ckamath
    Mar 12, 2017 at 9:08
  • 2
    $\begingroup$ You could take a look at updatable redactable signatures: henrich.poehls.com/papers/… $\endgroup$
    – DrLecter
    Mar 12, 2017 at 13:04
  • $\begingroup$ @Occams_Trimmer I was thinking of ECDSA, but would consider others if they have advantages. $\endgroup$
    – Joel Dice
    Mar 12, 2017 at 19:20
  • $\begingroup$ Just XOR all the document hashes together, and sign that. $\endgroup$
    – Anon Coward
    Nov 16, 2017 at 4:21
  • $\begingroup$ The set of 256-bit strings (hash values under SHA-256) is a vector space of dimension 256 over the field with 256 elements. So if you have more than 256 documents, you will always find a subset of documents whose hashes sum up to 0. Removing or adding such a subset would not be detected by the signature you suggest. $\endgroup$
    – j.p.
    Nov 16, 2017 at 6:55

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Note that the calculation of a signature generally includes the hashing (in this case the composite hash). Depending on the crypto library used you may or may not have to calculate the hash separately of the signature algorithm. Or you can use both; it depends. $\endgroup$
    – Maarten Bodewes ♦
    Nov 16, 2017 at 22:21
  • $\begingroup$ That's certainly a secure and simple solution. However, I was hoping to do better than O(n) time complexity for each update (where n is the number of documents). A Merkle tree is also secure and provides O(log n) updates, and the scheme I proposed provides O(1) updates, albeit with uncertain security. $\endgroup$
    – Joel Dice
    Nov 17, 2017 at 21:38
1
$\begingroup$

Facebook recently released LtHash, a set-homomorphic hashing algorithm with exactly the properties I was looking for when I posted this question.

As mentioned in the linked article, the big advantage of this approach over a Merkle tree is that updates and verifications can be performed efficiently without keeping the whole set in memory.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for reporting back Joel, interesting information. This comment will self destruct. $\endgroup$
    – Maarten Bodewes ♦
    Mar 5, 2019 at 12:08

Your Answer

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

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