Evidence that the McEliece Cryptosystem is resistant to Quantum Computing Attacks

A paper was posted on the preprint server Physics arXiv showing that the McEliece public key cryptosystem is resistant to efficient quantum algorithms based on the ideas of Shor’s algorithm, which famously yielded an efficient method for factoring integers. From the abstract

Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have post-quantum cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks. In this article we show that the McEliece cryptosystem over rational Goppa codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states.

Shor’s algorithm is a general method for computing the period of certain functions, and it can be applied to computing the orders of elements modulo a composite number for example (see my post Quantum Computing: are you Shor? for some details). Shor’s algorithm is not directly applicable to the McEliece cryptosystem since it is based on a hard problem from coding theory, and is not obviously solvable by computing periods of functions. The new paper seems to demonstrate that no connection will be found.

However the authors caution that there may be another quantum approach distinct from the principles of Shor’s algorithm that efficiently breaks the McEliece cryptosystem. On the other hand, there is a growing consensus that NP-complete problems do not have efficient quantum algorithms (see the diagram in this post), and the McEliece cryptosystem is based on an NP-hard problem (which means it is at least as hard as an NP-complete problem).

There is also a nice background post on the physics arXiv blog.

Related articles by Zemanta

• 1978 Cryptosystem Resists Quantum Attack (science.slashdot.org)
• Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing Attacks That Defeat All Common Codes [Encryption] (gizmodo.com)