[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Jerry Leichter leichter at lrw.com
Fri Oct 3 11:15:43 EDT 2014

On Oct 2, 2014, at 10:37 PM, Sandy Harris <sandyinchina at gmail.com> wrote:
> There has been a lot of work on parallelizable hashing. Web search for
> "tree hashing" will turn up much of it. Several of the SHA-3
> competition candidates, including at least the winner Keccak and
> finalist Skein, had discussions in their submissions of how to do a
> tree hash with their algorithm.
Keep in mind that "parallelizable" is often taken to mean "linear in the number of available processors".  No tree algorithm is "parallelizable" in this sense - it has a logarithmic delay to roll up the results.

Some encryption modes - e.g., CTR mode - *are* parallelizable in this strong sense.  But it shouldn't be hard to prove that hashing can't possibly be.  (In fact, I suspect that just the requirement that flipping any bit of the input has a 50% chance of flipping any given bit of the output should be enough to show that.)
                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141003/a94f1d1b/attachment.bin>

More information about the cryptography mailing list