I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that elements can be added but not removed from the underlying set (and hash). None of the existing instantiations (AdHash, MuHash, LtHash, or even XHash) appear to support this, because they are all defined over proper groups.

Borrowing from this paper, for an input set $S = \{x_1, \dots, x_n\} \in P(\{0,1\}^*)$, a commutative group $\mathsf{G}$ with operation $◦$, and an underlying hash function $h: \{0,1\}^* → \mathsf{G}$ modeled as a random oracle, the set homomorphic hash $\mathsf{H}$ is defined as $\mathsf{H}(S) = h(x_1)◦h(x_2)◦\dots,◦h(x_n)$. Set homomorphism of $\mathsf{H}$ follows immediately from this construction. Collision resistance of $\mathsf{H}$ follows from the hardness of a computational problem in $\mathsf{G}$ known as the balance problem. Instantiations of $\mathsf{H}$ include AdHash (addition over $\mathbb{Z}_q$ for some sufficiently large modulus $q$), MuHash ($\mathbb{Z}_q^*$ for sufficiently large and prime $q$), and LtHash (over the group $(\mathbb{Z}_q^n, +)$).

In all of these cases, $\mathsf{G}$ is a proper (commutative/abelian) group, with associative (and commutative) binary operation, identity element, and inverses. However, in the original incremental hashing paper, they don’t explicitly state that operations need to be over a full group, only that this is a nice feature because it allows for incrementally adding and removing elements from the underlying set. So what if instead of defining an operation over a proper group, we used an associative operation over a semigroup (and specifically one without any inverses), or a monoid?

Note that something like Cayley hashes (hashing with ${SL}_2$) are pretty close to what I want, except those are homomorphic over the concatenation of bit-strings, rather than sets. There is a related question about a non-reversible additive cryptographic hash algorithm (see their edit, where they define non-reversible to be similar to a semigroup or an operation that doesn't have an inverse) though in my case, I don't need quantum resistance, and the answers to that question don't appear to address the concept of inverses in the semigroup directly. I've also explored the set of non-invertible matrices and related approaches, but this either a) loses information at each application of the operation, or b) seems to be trivial to break for most layouts I could come up with (e.g. upper triangular matrices with a(ll) zero(s) on the diagonal).

My question is thus: does such a semigroup/monoid exist which is suitable for cryptographic applications?



Your Answer

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