[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

[Bear]

On Wed, 2014-10-08 at 20:09 -0400, David Leon Gil wrote:
> On Wed, Oct 8, 2014 at 12:20 PM, Bear <bear at sonic.net> wrote:
> > a) you want aliasing (accidental collisions) to be minimized.
> > b) you want the hash to be fast to compute.
> > c) you want "random" distribution of GUID's in the hash table
> >    (ie, no single part of your hash table should be *more*
> >     full than the other parts, or at least not by any margin
> >     distinguishable from statistical noise on random numbers).
> 
> As an aside, what you're describing is a function with low discrepancy
> on the inputs. This is (interestingly enough) different from a
> function that generates values indistinguishable from uniform random
> numbers in the interval. (The values "anti-bunch", in some sense,
> compared to random numbers.) See, e.g.,
> http://en.wikipedia.org/wiki/Low-discrepancy_sequence for the
> fascinating details of low-discrepancy sequences and quasi-random
> numbers.
> 

Yes, that is exactly the distinction.  A counter viewed through 
a linear congruential transformation is a perfect example of a
low-discrepancy or quasirandom function.  It will generate 
*every* possible value, *once*, before the counter rolls over 
and it starts repeating. 

As a reductio ad absurdum, if it's a sixteen bit counter and 
you've seen the last 65535 outputs, you know exactly what the 
next output is going to be -- it's going to be whatever value 
you haven't seen yet, and then the sequence you've already seen 
will repeat.  If it were a good cryptographic hash, you would 
have, as always, absolutely no idea what the next output will 
be just by knowing previous outputs. 

				Bear