Let H:X→{0,1}b denote a cryptographically secure, b-bits hash function on a set X. Let H∗:P(X)→{0,1}b be a function on the power set of X defined by H∗({x1,…,xn})=∑iH(xi)

Is see and understand that most variants of this construction using a modular domain for addition are flawed. I also see that these failures do not contradict the NP-completeness of the subset sum problem.

I am however not finding any arguments against the security of this scheme in the non modular case, where the sum is in the natural integer domain. At first glance, one would assume that any solution of the non modular variant that improves on the O(2^(n/2)) bound can be turned into a an improved algorithm for the subset sum problem for random inputs.

Formally, the sum of hashes in the natural domain does not fit the definition of a hash function since the size of the output is variable. This is however easy to fix in practice by applying the hash function once more to the sum.

This is obviously related to previous questions on this forum, such as Is the sum of hashes a suitable hash for sets? and Are there any practical implementation of a homomorphic hashing or signature scheme?

Let $H:X \to \{0,1\}^b$ denote a cryptographically secure, $b$-bits hash function on a set $X$. Let $H^∗:\mathcal P(X) \to \{0,1\}^b$ be a function on the power set of $X$ defined by $H^∗(\{x_1,…,x_n\}) = \Sigma_i H(x_i)$

Is see and understand that most variants of this construction using a modular domain for addition are flawed. I also see that these failures do not contradict the NP-completeness of the subset sum problem.

I am however not finding any arguments against the security of this scheme in the non modular case, where the sum is in the natural integer domain. At first glance, one would assume that any solution of the non modular variant that improves on the $\mathcal O(2^{n/2})$ bound can be turned into a an improved algorithm for the subset sum problem for random inputs.

Formally, the sum of hashes in the natural domain does not fit the definition of a hash function since the size of the output is variable. This is however easy to fix in practice by applying the hash function once more to the sum.

This is obviously related to previous questions on this forum, such as Is the sum of hashes a suitable hash for sets? and Are there any practical implementation of a homomorphic hashing or signature scheme?