On 10/14/2010 02:49 PM, Samuel Neves wrote:
On 14-10-2010 19:32, Marsh Ray wrote:
3. There are quantum computer attacks theorized which appear to cut
the exponent in half again. Thus a 256 bit hash could possibly be
collided in 264 operations on some future machine.
Is there a source for this? The only quantum approach I've heard of, the
Brassard-Høyer-Tapp algorithm, takes 2^(n/3) time (and space!).
Keep in mind this was me guessing about someone else's reasoning, but it
probably still holds for 2^(n/3).
I'd inferred people might be think that way from some security claims on
a specific SHA-3 candidate function:
http://cubehash.cr.yp.to/submission2/strength.pdf dated 2009-09-14.
"256-bit preimage resistance. CubeHash–256 is expected to provide
preimage resistance of approximately 256 bits, but quantum computers are
expected to reduce preimage resistance to approximately 128 bits."
Of course, that was about preimage resistance of a specific function,
CubeHash, not collision resistance in general. In fact, that same author
claims that all current quantum collision attacks are actually worse
than conventional ones: http://cr.yp.to/papers.html#collisioncost
CubeHash has a simple and highly regular internal structure with no
resistance to meet-in-the-middle attacks other than its large 1024 bit
internal state. Previously, it had been "observed" that for functions of
this general design, (and I hope I'm stating this correctly) if anyone
did the work to find a second preimage of the all-zeroes message, they
would be then able to generate second preimages for any message at all
for O(1). As you can expect, the practical significance of this was
somewhat controversial.
But now it gets interesting:
Gaëtan Leurent then proposes a 2^192 quantum preimage attack (on this
nominally 512-bit hash function):
http://eprint.iacr.org/2010/506
It employs Grover's algorithm for O(N^(1/2)) searching:
http://en.wikipedia.org/wiki/Grover%27s_algorithm
Given that a collision cannot be harder to find than a second preimage,
and a second preimage cannot be harder to find than a first preiamge,
and here was a proposed 2^192 on a 512-bit output-length function, it
seemed like someone might have a tiny bit of justification to not feel
entirely comfortable with "only" a 256-bit hash function.
- Marsh
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
