[Cryptography] an associative hash function
ben at links.org
Wed May 27 16:09:19 EDT 2015
On 27 May 2015 at 18:47, Jelle van den Hooff <jelle at vandenhooff.name> wrote:
> Hi everyone,
> If you are interested in hash functions or data structures, I wrote a short
> paper (http://jelle.vandenhooff.name/seqhash.pdf) you might like on
> associative hash functions. An associative hash function is a hash function
> that allows you to efficiently calculate hash(concat(a, b)) from hash(a) and
> hash(b). In the paper, I describe how to build an associative hash function
> from history-independent data structures.
> There is a small catch, as the associative hash function described has an
> output that grows in size as O(log n), instead of the O(1) delivered by SHA
> et al. That is, for now, the price to pay for associativity.
Sounds exactly like a Merkle tree.
More information about the cryptography