Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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). –  e-sushi Jul 9 at 15:51
1  
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 ? –  Dingo13 Jul 10 at 16:35

1 Answer 1

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.

share|improve this answer
3  
I'd expect grover to be applicable to some degree. –  CodesInChaos Jul 12 at 21:14
    
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 ? –  Dingo13 Jul 15 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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