Jerry Leichter writes: > It all depends on how you define an attack, and how you choose to define your > security. I explored the "outer edge": Distinguishability from a random > function. For a random function from {0,1}*->{0,1}^k, we expect to have to do > 2^k work (where the unit of work is an evaluation of the function) per > collision. The collisions are all "independent" - if you've found N, you have > ... N. The next one you want still costs you 2^k work.
I don't believe this correct. Joux said that for a true random function, finding a multicollision of degree j, i.e. j distinct values which hash to the same thing, takes 2^((j-1)*k/j) for a k-bit hash. He mentioned a Crypto paper by David Wagner from a few years ago which showed how to do this. See http://www.cs.berkeley.edu/~daw/papers/genbday.html . This means that the work for a (j+1)-collision is about 2^(k/j^2) times harder than for a j-collision, not 2^k times harder. Now, this is not done by first finding a j-collision and then looking for a new value that matches; that would, as you say, take 2^k times the work. Rather, one collects enough hashes and then matches them up in an efficient way to find the (j+1)-collision. The wide-internal-path proposal will therefore satisfy the constraints about multicollisions. With a 2k bit wide internal path for a k bit hash, it will take 2^k work to find an internal collision. With some multiple of this, Joux's attack finds large multicollisions. But as the paper by Wagner shows, you can find arbitrarily large multicollisions in a true random k-bit function with less than 2^k work. Since Joux's attack takes more than this, it does not distinguish this hash construction from a random function. Hal --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]