5
$\begingroup$

What is the computational time to break McEliece on a quantum computer?

I've seen that polynomial time algorithms exist, but for special conditions. What about the general case?

$\endgroup$
4
$\begingroup$

Dinh, Moore, Russell have shown that the quantum algorithm (Quantum Fourier sampling) used to attack RSA and ElGamal does not work on McEliece-like crypto systems. (I think) this means, that there are no known algorithms on quantum computers that decrease the complexity of attacks on McEliece, and thus McEliece is just as safe post-quantum computers as it is now.

$\endgroup$
  • 3
    $\begingroup$ I'd expect grover to be applicable to some degree. $\endgroup$ – CodesInChaos Jul 12 '14 at 21:14
  • $\begingroup$ Thanks @QuadrExAtt What are these attacks complexities ? When you say "no known algorithms on quantum computers that decrease the complexity of attacks", you are speaking about attacks without quantum computer ? $\endgroup$ – Dingo13 Jul 15 '14 at 21:47

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.