<p>Sure.  These are known as homomorphic hash functions.  There are many schemes: see e.g., <a href="https://crypto.stackexchange.com/q/6497/351">https://crypto.stackexchange.com/q/6497/351</a> for one possible entry point into the literature.</p>

<p>One example construction is to let $\mathbb{G}$ be a group with group operation $*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $h:\{0,1\}^* \to \mathbb{G}$ by associativity, i.e.,</p>

<p>$$h(x_1 x_2 \dots x_n) = h(x_1) * \cdots * h(x_n).$$</p>

<p>Then you can choose any group $\mathbb{G}$ of your choice.  If you want $*$ to be non-commutative, choose a non-abelian group $\mathbb{G}$.  One plausible choice is $\mathbb{G} = SL_2(\mathbb{F})$ over some finite field $\mathbb{F}$; see <a href="https://crypto.stackexchange.com/q/17730/351">https://crypto.stackexchange.com/q/17730/351</a>.</p>

<hr>

<p>Your reasons why it can't exist are not valid.  I don't know what "there would be a loss of entropy" means; any hash function always causes a loss  of entropy (if the domain is larger than the range), thanks to the pigeonhole principle, but that doesn't mean hash functions don't exist or can't be deterministic.  The existence of Merkle trees doesn't preclude the existence of other solutions.</p>

CC BY-SA 3.0
2017-05-19T18:38:17.203Z
Thanks... What I believed by loss of entropy is that the loss isn't deterministic (afaik), so the combined loss can't be a function of the losses of its parts. I guess my intuition isn't much better than guess work :P Anyway, given such functions can exist, why aren't they used instead of Merkle trees? It seems like they'd be perfect for the purposes Merkle trees are used for.
Xophmeister
CC BY-SA 3.0
2017-05-19T18:42:07.663Z
@Xophmeister, Your question about Merkle trees is a good one.  There might be various reasons, but as far as I know, the big one is that Merkle trees are provably secure (i.e., collision-resistant) under fairly-well-vetted assumptions (e.g., that SHA256 is collision-resistant).  In contrast the schemes for homomorphic hashing rely on security assumptions that haven't been vetted as thoroughly.
D.W.
CC BY-SA 3.0
2017-05-19T19:48:18.263Z
Interesting: So, if your application didn't require cryptographic guarantees -- e.g., checksumming blocks of data -- homomorphic hashing would have some pretty desirable properties?
Xophmeister
CC BY-SA 3.0
2017-05-19T21:02:21.800Z
@Xophmeister, seems like it, yup.  You'd have to test performance to see how the two approaches, if you're hashing long strings.
D.W.
CC BY-SA 3.0
2017-05-19T18:32:07.027Z
2017-05-19T18:32:07.027Z
D.W.
<p>Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:</p>

<p>$$hash(X+Y) = hash(X) * hash(Y)$$</p>

<p>...where $+$ is concatenation, and $*$ is associative (but not necessarily commutative)?</p>

<p>Clearly $hash$ being the identity function, with $*:=+$, satisfies this. However, what if we put usual constraints on $hash$ -- say, its output is always $n$-bits, where $n$ is small -- and $*$ has to be reasonably economical?</p>

<p>My intuition is saying that no such $(hash,*)$ exists, because:</p>

<ul>
<li><p>In the general case, there would be a loss of entropy in hashing and I don't believe this can be deterministic.</p></li>
<li><p>Merkle trees are a thing, which implies there's no better option.</p></li>
</ul>

<p>(n.b., I realise "linear", in the linear algebra sense, isn't the correct word to use here, but for want of a better term!)</p>

CC BY-SA 3.0
2017-05-19T17:41:44.377Z
The generic term for "function that behaves well with respect to some operations" is (homo)morphism. Googling "morphism hash function" yields, among other things, this article: https://eprint.iacr.org/2013/415.pdf
xavierm02
<linear-algebra><hash-function>
"Linear" hashing function
Xophmeister
# "Linear" hashing function

(Asked by: username_0 on 2017-05-19)

Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $\*$, such that:

$$hash(X+Y) = hash(X) \* hash(Y)$$

...where $+$ is concatenation, and $\*$ is associative (but not necessarily commutative)?

Clearly $hash$ being the identity function, with $\*:=+$, satisfies this. However, what if we put usual constraints on $hash$ -- say, its output is always $n$-bits, where $n$ is small -- and $\*$ has to be reasonably economical?

My intuition is saying that no such $(hash,\*)$ exists, because:

* In the general case, there would be a loss of entropy in hashing and I don't believe this can be deterministic.
* Merkle trees are a thing, which implies there's no better option.

(n.b., I realise "linear", in the linear algebra sense, isn't the correct word to use here, but for want of a better term!)

**Tags:** linear-algebra, hash-function
> **Comments:**
> **username_1**: The generic term for "function that behaves well with respect to some operations" is (homo)morphism. Googling "morphism hash function" yields, among other things, this article: https://eprint.iacr.org/2013/415.pdf  

---

## 1 answers

### Answer by username_2 on 2017-05-19. Score: 3 | Accepted answer

Sure. These are known as homomorphic hash functions. There are many schemes: see e.g., <https://crypto.stackexchange.com/q/6497/351> for one possible entry point into the literature.

One example construction is to let $\mathbb{G}$ be a group with group operation $\*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $h:\{0,1\}^\* \to \mathbb{G}$ by associativity, i.e.,

$$h(x\_1 x\_2 \dots x\_n) = h(x\_1) \* \cdots \* h(x\_n).$$

Then you can choose any group $\mathbb{G}$ of your choice. If you want $\*$ to be non-commutative, choose a non-abelian group $\mathbb{G}$. One plausible choice is $\mathbb{G} = SL\_2(\mathbb{F})$ over some finite field $\mathbb{F}$; see <https://crypto.stackexchange.com/q/17730/351>.

---

Your reasons why it can't exist are not valid. I don't know what "there would be a loss of entropy" means; any hash function always causes a loss of entropy (if the domain is larger than the range), thanks to the pigeonhole principle, but that doesn't mean hash functions don't exist or can't be deterministic. The existence of Merkle trees doesn't preclude the existence of other solutions.

> **Comments:**
> **username_0**: Thanks... What I believed by loss of entropy is that the loss isn't deterministic (afaik), so the combined loss can't be a function of the losses of its parts. I guess my intuition isn't much better than guess work :P Anyway, given such functions can exist, why aren't they used instead of Merkle trees? It seems like they'd be perfect for the purposes Merkle trees are used for.  
> **username_2**: @Xophmeister, Your question about Merkle trees is a good one.  There might be various reasons, but as far as I know, the big one is that Merkle trees are provably secure (i.e., collision-resistant) under fairly-well-vetted assumptions (e.g., that SHA256 is collision-resistant).  In contrast the schemes for homomorphic hashing rely on security assumptions that haven't been vetted as thoroughly.  
> **username_0**: Interesting: So, if your application didn't require cryptographic guarantees -- e.g., checksumming blocks of data -- homomorphic hashing would have some pretty desirable properties?  
> **username_2**: @Xophmeister, seems like it, yup.  You'd have to test performance to see how the two approaches, if you're hashing long strings.  

---

