[Cryptography] Secure parallel hash, with constant time update

Bill Cox waywardgeek at gmail.com
Mon Oct 13 19:34:47 EDT 2014

On Mon, Oct 13, 2014 at 6:11 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:

> It is well known (going back to the '90s) that the following function is
> collision resistant if the discrete log problem is hard:
>   public constants: g_1, g_2, ..., g_n, all elements mod p
>   input: x_1 | x_2 | x_3 | ... | x_n
>   output: \prod_i g_i^{x_i} mod p
> A proof for the case of n=2 is in my cryptography textbook. Note that this
> function is also updateable in constant time.

Very cool...

> If we model H as a random oracle, we can modify the above to:
>   input: x_1 | ... | x_n
>   output: \prod_i H(i)^{x_i} mod p
> This has also been suggested in the literature.
> You are suggesting instead to look at the construction
>    input: x_1 | x_2 | ... | x_n
>    output: \prod_i H(i | x_i) mod p
> This has the advantage of being more efficient than the above
> constructions. This, too, is secure -- but was already proposed in the
> paper "A New Paradigm for collision-free hashing: Incrementality at reduced
> cost" available here:
> http://cseweb.ucsd.edu/~mihir/papers/incremental.html
> I'm not sure if that's good or bad news vis-a-vis your constructions. =)
Thanks for point out the paper!

I take it as good news.  It means I'm  less of a dork than I thought,
although I wish I had better google-fu.  I was going for "parallel" when
"incremental" would have gotten me these results quickly.

It's fun to read these papers knowing about the generalized birthday
attack.  My construction is identical to MuHASH, which he proved secure in
the same way.  However, he then argues that we can securely use AdHASH,
can't prove it, and instead states similarities between finding collisions
in hashes added together modulo a big number to the modular knapsack
problem, known to be hard.  It's a good example of how hand-waving in
crypto can be a bad idea.

Wagner and friends clearly broke AdHASH with his generalized birthday
attack, but I think MuHASH still stands.  For example, the 4-element
generalized birthday problem works so long as we throw out any hash values
> M/4, where we're doing modulo M addition.  I am a bit surprised that
Wagner's paper spends so much time trying to find weaknesses with
multiplication, but I guess it makes sense if we're talking about weaker
multiplicative groups than integers modulo large primes.  I assume he knew
about AdHASH and MuHASH.

In general, the important property of the combining operator seems to be
that it mixes bits cryptographically well.  Addition didn't quite get there.

With multiplication, even 2-way, picking two random numbers between 0 and
p-1 that multiply to anything other than astronomically larger than p is on
the easily less likely than 1/sqrt(p) - how's that for had waving :-)
Therefore, we can't throw out all those too-large random numbers and expect
to run faster than sqrt(p) calls to H.

Thanks again for the pointer.  Very cool

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141013/43bbd82f/attachment.html>

More information about the cryptography mailing list