<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Oct 13, 2014 at 6:11 PM, Jonathan Katz <span dir="ltr"><<a href="mailto:jkatz@cs.umd.edu" target="_blank">jkatz@cs.umd.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>It is well known (going back to the '90s) that the following function is collision resistant if the discrete log problem is hard:<br>  public constants: g_1, g_2, ..., g_n, all elements mod p<br>  input: x_1 | x_2 | x_3 | ... | x_n<br>  output: \prod_i g_i^{x_i} mod p<br>A proof for the case of n=2 is in my cryptography textbook. Note that this function is also updateable in constant time.<br></div></div></blockquote><div><br></div><div>Very cool...<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>If we model H as a random oracle, we can modify the above to:<br>  input: x_1 | ... | x_n<br>  output: \prod_i H(i)^{x_i} mod p<br>This has also been suggested in the literature.<br><br>You are suggesting instead to look at the construction<br>   input: x_1 | x_2 | ... | x_n<br>   output: \prod_i H(i | x_i) mod p<br>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: <a href="http://cseweb.ucsd.edu/~mihir/papers/incremental.html" target="_blank">http://cseweb.ucsd.edu/~mihir/papers/incremental.html</a><br><br></div>I'm not sure if that's good or bad news vis-a-vis your constructions. =)<div><div class="h5"><br></div></div></div></blockquote><div><br></div><div>Thanks for point out the paper!<br></div><div><br></div><div>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.<br><br></div><div>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.<br><br></div><div>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.<br><br></div><div>In general, the important property of the combining operator seems to be that it mixes bits cryptographically well.  Addition didn't quite get there.<br><br></div><div>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.<br><br></div><div>Thanks again for the pointer.  Very cool<br></div><div><br></div><div>Bill<br></div></div></div></div>