1
$\begingroup$

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!)

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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: eprint.iacr.org/2013/415.pdf $\endgroup$
    – xavierm02
    Commented May 19, 2017 at 17:41

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Xophmeister
    Commented May 19, 2017 at 18:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented May 19, 2017 at 18:42
  • $\begingroup$ Interesting: So, if your application didn't require cryptographic guarantees -- e.g., checksumming blocks of data -- homomorphic hashing would have some pretty desirable properties? $\endgroup$
    – Xophmeister
    Commented May 19, 2017 at 19:48
  • $\begingroup$ @Xophmeister, seems like it, yup. You'd have to test performance to see how the two approaches, if you're hashing long strings. $\endgroup$
    – D.W.
    Commented May 19, 2017 at 21:02

Your Answer

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

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