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$
2

1 Answer 1

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$
2
  • 3
    $\begingroup$ I'd expect grover to be applicable to some degree. $\endgroup$ Jul 12, 2014 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, 2014 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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