[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Bill Cox waywardgeek at gmail.com
Mon Oct 6 18:23:42 EDT 2014

On Sat, Oct 4, 2014 at 1:21 PM, Ben Laurie <benl at google.com> wrote:

> However, this is not a good way to go about designing crypto primitives.
I disagree with this point.  This thread is an excellent way for people to
*avoid* mistakes like this hash function.  People should be *encouraged* to
post their latest dumb idea about hashing here, so it can be reviewed
before harming anyone.

Furthermore, this thread introduces a valuable concept I was not aware of
before, and it's fun :-)  The uses for such a hash function are I think
quite broad.  For example, we could incrementally update a
cryptographically strong hash of a huge database in constant time.  So...
here's *my* dumb hashing solution for this problem:

Simply compute:

Digest = H(N || H(H(1 || B1) * H(2 || B2) * ... * H(n || Bn) mod p))

While I am often wrong, I have managed in my head to prove to myself that
finding collisions in the generalized birthday problem over a
multiplicative group modulo a prime is equivalent to solving the discrete
log problem.  If this proof holds up, then this should be a secure hash, so
long as p is large enough, such as 2048 bits.  Also, I assume that H is
effectively a random oracle with no possible analysis of it's function that
could help us find collisions.  Some hash functions, such as H(x) = g^x mod
p clearly fail here.  However, any respected ARX based hash should work
out, as should Wolfram's Rule-30-like hashes such as Keccak.

My proposed proof is simple.  Instead of picking true random numbers ri < p
to multiply together, looking for a collision in the usual way, compute si
= g^ri mod p for i in 1 .. n.  If g is a group generator, then si is just
as random as ri, but we know something about si (it's discrete log).  Using
a supposed algorithm faster than solving the discrete log, we now find the
discrete log of y = g^x.  Just find r1 ... rn such that g^r1 * g^r2 * ... *
g^rn = x, using our fast algorithm, and then the discrete log of x is
trivially found as r1 + r2 + ... + rn mod p-1.

Surely, any algorithm that can find such solutions multiplying r1 * r2 *
... * rn will work just as well using ri = g^H(i) mod p as it would using
the H(i) values as random numbers instead, so this step of replacing ri
with si is sound.

Therefore, this hash function is secure, based on the security of the
discrete log problem.

Does this work out?  If it is secure, as I currently believe, then it
should have a number of good uses in cryptography.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141006/134b11e1/attachment.html>

More information about the cryptography mailing list