Ever since the SHA-3 competition, I've been wondering if it is possible to create a hash algorithm that is easier to parallelize. The current algorithms all seem to require building a tree of hashes. This has however rather serious drawbacks:
- as they requires a tree with certain parameters (such as the size of nodes and branches), it needs to be explicitly defined what the tree looks like
- communicating parties should be programmed explicitly to allow hash trees
- the tree is likely to be optimized for certain configurations, and not all parties will have the same configuration (e.g. an 8 or 16 bit processor checking the hash created by a 64 bit server machine with GPU acceleration)
- if the leaves are too big, you need a whole lot of information before you could start with the next leaf
- with the exception of Skein, none of the remaining candidates seem to define how the hash tree should even be constructed
Now I am wondering if you could construct a hash algorithm using a PRF that has a counter as input. In this construct, you would have a relatively strong PRF that is fed both the counter and a block plain text, resulting in an output of a known size (step1). This output would then be compressed together with the other transformed blocks in (step 2). Finally, as usual for a hash, you would have a finalization step which avoids length extension attacks (step3).
To allow for easy parallelism, I think that step 2 should be associative. In other words, it should not matter in which order the output of step 1 is given to the function in step 2. If it is associative, it would even be possible to distribute step 2 between the processes as well. In that case, step 2 may even be relatively heavy (sponge like?). The trick, obviously, is to create collision resistance for the combination of step 1 and step 2. This is where my perfect scheme begins to crumble, and I am wondering if it is even possible to create a solution for the problem.
The advantages of such a scheme are obvious: it would have none of the drawbacks of the tree hash scheme. Anybody could generate a hash using as many threads or computing blocks as they want. Only the block size, the output size of step 1 and the state of step2 would be restraining implementations.
The algorithm would of course not be able to use the Merkle–Damgård construction, as it assumes that each block is processed in a sequential fashion - which introduces the problem in the first place. It seems that Merkle–Damgård and variations on Merkle–Damgård still rule supreme in the SHA-3 competition (at least with most of the final candidates).
[EDIT: By now Keccak has been chosen as winner of the SHA-3 competition, and one of the reasons is that it was the candidate within the 5 remaining candidates that was using a sponge instead of a Merkle–Damgård construction, so I guess that this paragraph is out of date by now]
Unfortunately, I'm not introduced to mathematics enough to see the correct solution, I cannot find if it has been tried, and I'm certainly not able to prove that my scheme would be impossible. Hopefully, this is where you can give me some hints.