Quasipolynomial Cryptanalysis of the McEliece Cryptosystem [pdf]

A major result in post-quantum cryptography. A key security assumption behind Classic McEliece, a public-key encryption system considered to resist quantum computers, has been undermined. Researchers found a provable quasipolynomial-time method for detecting the hidden mathematical structure in its public keys. The attack is still astronomically expensive and cannot yet decrypt messages, but this is a serious weakening of one of the oldest post-quantum cryptosystems. McEliece is not broken practically today, but an important assumption underlying its theoretical security has been broken. For the Classic McEliece parameter sets, the estimated cost of the best known structural distinguisher drops from roughly 2^298-2^691 operations to about 2^114-2^124. That is huge.