[Cryptography] an associative hash function

[Henry Baker]

At 10:47 AM 5/27/2015, Jelle van den Hooff wrote:
>Hi everyone,
>
>If you are interested in hash functions or data structures, I wrote a short paper (<http://jelle.vandenhooff.name/seqhash.pdf>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.
>
>Jelle

You should be aware of (& possibly reference) the following paper:

http://rsa.cse.nsysu.edu.tw/rsa/cryptology/OneWayFuctionPneNP.pdf

An Observation on Associative One­Way Functions in Complexity Theory
Muhammad Rabi and Alan T. Sherman
Department of Computer Science and Electrical Engineering
University of Maryland Baltimore County
Baltimore, Maryland 21250
email: mrabi at cs.umbc.edu and sherman at cs.umbc.edu
November 8, 1997

Abstract 

We introduce the notion of associative one­way functions and prove that they exist if and 
only if P 6= NP .  As evidence of their utility, we present two novel protocols that apply strong 
forms of these functions to achieve secret key agreement and digital signatures.

Keywords.  Associative one­way functions (AOWFs), computational complexity, cryptology, cryp­ 
tography, cryptocomplexity, cryptographic protocols, digital signatures, key­agreement problem, 
secret­key exchange, theory of computation, public­key cryptography.