[Cryptography] Secure parallel hash, with constant time update

Jonathan Katz jkatz at cs.umd.edu
Mon Oct 13 18:11:32 EDT 2014

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.

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. =)

On Mon, Oct 13, 2014 at 5:57 PM, Bill Cox <waywardgeek at gmail.com> wrote:
> On Mon, Oct 13, 2014 at 5:01 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:
>> What is your definition of security?
> In this context, I define it as collision resistance of the digest.  If
an attacker found two sets of message blocks that hash to the same digest,
then this hash would be broken.
> Finding two different sets of messages resulting in the same hash y is as
difficult as finding the discrete log of y.
> Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141013/e96a5738/attachment.html>

More information about the cryptography mailing list