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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Hint: Lange, Bernstein, and Peters demonstrated that if one used the original security parameters for the McEliece cryptosystem, then they could break the cryptosystem using classical computers in two weeks on a cluster of one hundred computers. You could deduct “the computational time to break McEliece on a quantum computer” from that… (that is, if you know what type of quantum computer you’re actually talking about in the first place – individual specs and setups will strongly influence the computational time needed). $\endgroup$– e-sushiJul 9, 2014 at 15:51
-
1$\begingroup$ In fact I'm interested in the underlying decoding problem. What do we know about complexity to break it with quantum computers. I've seen that McEliece is resistant to quantum computer but to what bound ? $\endgroup$– Dingo13Jul 10, 2014 at 16:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
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$– Dingo13Jul 15, 2014 at 21:47