I saw in another stack exchange post that the same way quantum annealing can be used to factor primes, it can also be used to calculate a collision in SHA-1 and it references this paper https://arxiv.org/abs/quant-ph/0209084 . I understand that the paper claims a technique that can be applied to all NP-hard problems. Is this true? And I still don't see how one would apply it to the hash collision problem. Any help is greatly appreciated!

  • $\begingroup$ A link to the other post would be good. $\endgroup$ – Chris Jan 24 '18 at 0:19
  • $\begingroup$ Btw, note that they only claim to solve all NP problems in polynomial time, not all NP-hard problems. There are problems in NP hard that cannot be reduced to a boolean circuit at all, much less in polynomial time. $\endgroup$ – Chris Jan 24 '18 at 2:13
  • $\begingroup$ Sorry, here it is. physics.stackexchange.com/questions/11063/… $\endgroup$ – Jim D Jan 26 '18 at 18:11

Calculating preimages in SHA-1 is in NP, so finding collisions certainly is. So their claim of making all NP problems P would definitely apply. It just becomes a matter of converting the problem into a boolean circuit: basically implement SHA-1 as a circuit and set up gates so the only consistent solution is one with a given hash.

On the other hand, I cannot express in words how skeptical I am of this claim. The authors make many assumptions to show that it is plausible that their model relaxes in polynomial time, but fall well short of demonstrating that it does. There are too many possible failure modes of their idealized model.

| cite | improve this answer | |

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.