<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><br>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">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. =)<br><div><br>On Mon, Oct 13, 2014 at 5:57 PM, Bill Cox <<a href="mailto:waywardgeek@gmail.com">waywardgeek@gmail.com</a>> wrote:<br>><br>> On Mon, Oct 13, 2014 at 5:01 PM, Jonathan Katz <<a href="mailto:jkatz@cs.umd.edu">jkatz@cs.umd.edu</a>> wrote:<br>>><br>>> What is your definition of security?<br>><br>><br>> 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.<br>><br>> Finding two different sets of messages resulting in the same hash y is as difficult as finding the discrete log of y.<br>><br>> Bill<br><br></div></div>