I would like to have a hash function $H(a_1,...,a_n)$ with the following properties:

  1. $a_1 ... a_n$ are byte arrays with same size (typically 32 or 64 bytes).

  2. It should also allow "easy" update or deletion of a single element, i.e :

    • $H(a_1,...,a_{n+1}) = f(H(a_1,...,a_n), a_{n+1})$
    • $H(a_1,...,a_{i-1},a_{i+1},...,a_n) = g(H(a_1,...,a_{n}), a_i)$
  3. The order of the $a_1 ... a_n$ terms for $H$ function does not matter.

I found a similar question, but I don't think it can easily handle the single item deletion requirement: Is there such thing as an order independent, updatable hash?

Thanks in advance!

  • $\begingroup$ What sort of security requirements does the hash function need to meet? For example, preimage resistance, modified second preimage resistance, modified collision resistance ("modified" because of the commutative nature of the hash function would give some easy second preimages)? $\endgroup$
    – poncho
    Dec 20 '17 at 18:42
  • $\begingroup$ Actually, Ethan's hash function (that you linked to) wouldn't be hard to modify to make it be able to handle deletes; you'd select $g$in Ethan's function to have a prime order $q$, and you'd have the $g$ function you asked for in question 2 be $g(H(a_1, ..., a_n), a_i) = H(a_1, ..., a_n)^{SHA256(a_i)^{-1} \bmod q} \bmod p$ $\endgroup$
    – poncho
    Dec 20 '17 at 18:56
  • $\begingroup$ Thanks a lot, with your suggestion this works perfectly! $\endgroup$ Dec 20 '17 at 23:04
  • $\begingroup$ Here is a more detailed description of what I'm trying to achieve: - I have $o_1 ... o_n$ objects in datastore (which are returned in random order). - Each object $o_i$ is signed in datastore, the signature is $a_i$ - I want to detect "rogue" insertions (can be done with the signatures) and more importantly rogue deletions, so the need for this kind of hash for this purpose. $\endgroup$ Dec 20 '17 at 23:16
  • $\begingroup$ What I'm not sure is how to select a "good" $g$ value of prime order $q$. I basically use this algorithm: - Step 1: Generate a prime number $q$ - Step 2: Compute $p = 2q + 1$ - Step 3: Choose a random $h$ and compute $g = h^{(p-1)/q} (mod p)$ - Step 4: if $g^q (mod p) =1$ then keep $p$, $g$ and $q$ otherwise go to step 1 By the way, what would be a good size for the $q$ parameter ? $\endgroup$ Dec 20 '17 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.