8
$\begingroup$

Perhaps this has been answered before. Grover's algorithm should result in a 256 bit hash being complexity 128 bits to crack.

I was wondering, what if you had a 512 bit hash , and xor'd the lower 256 with the upper 256 bits to result in a final 256 bit hash number.

Does this increase the complexity (ie: decreasing the viability of Grover's algorithm) by any factor?

I'm expecting not, however was just theorizing how you could remap a 512 bit hash into a 256 bit space to stop grovers from functioning (reminiscent of some public key compression algorithms).

$\endgroup$
  • 3
    $\begingroup$ Best case it's just another 256-bit hash. $\endgroup$ – otus Oct 2 '15 at 14:11
8
$\begingroup$

Grover's algorithm treats the function it is evaluating as a black box and finds, with high probability, an input to the black box such that it outputs a specified value in $O(N^{1/2})$ evaluations of the function.

Since Grover's algorithm works on the function as a black box, your modification does not hinder Grover's algorithm at all in finding the preimage.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.