Imagine you receive a large box of numbers meant to serve as a public key for secure communication. The numbers look completely random, the way scrambled data should look if no one can find a pattern. Yet a careful test reveals a subtle internal order. That is the main finding of a recent paper by Ashrujit Ghoshal, Yuval Ishai, Aayush Jain, and Nuozhou Sun titled “Quasipolynomial Cryptanalysis of the McEliece Cryptosystem.” The paper does not open the box or read any of the messages inside it. It simply shows that the box of numbers can be told apart from one filled with pure chance.[1]
The method begins by setting aside one or more pieces of the public key. Researchers then search for special mathematical patterns that vanish completely on every remaining piece. When the key truly comes from the Classic McEliece system, those same patterns also vanish on the pieces that were set aside. When the key is truly random, the patterns almost never vanish in the same way. The reasoning rests on solid principles of linear algebra and polynomial behavior; it does not depend on unproven guesses. The same line of thinking also points toward a potential method for recovering an original message from an encrypted one, but that step requires extra assumptions that have not been fully proven, and even if they hold, the work required remains far beyond practical reach today.
The entire approach grew out of an earlier effort to design a system that would let a person retrieve a single item from a large remote database without revealing which item was wanted. The query patterns that arose in those attempts looked exactly like the public keys used by McEliece-style systems. A test that broke the privacy of the information-fetching idea could be rewritten as a test that spots the hidden structure inside McEliece keys. The same technique works for several related families of encryption schemes that rely on similar structured codes. When the authors applied it to the exact key sizes examined for possible standardization, the estimated computational effort was lower than earlier structure-finding methods. Lower, in this case, is relative. The amount of memory required for the method of working is so large, many thousands of times greater than the biggest computers available, that no one could actually run the attack.
It is important to understand what the method does not do. It recovers neither the secret key that only the legitimate owner holds, nor any encrypted message, nor the random noise that was deliberately added during encryption. It only decides whether a given public key carries the special structure used by McEliece or is simply random data. Also, the Classic McEliece security guarantees never promised that its public keys would be impossible to distinguish from random data in this strong sense, and its security arguments never depended on that promise. As a result, none of the system's actual security claims have been broken. Noticing the structure is a scientific step forward, but it is not the same as reading messages, finding secret keys, or undoing encryption. An attack that needs memory measured in hundreds of millions of gigabytes remains theoretical, not a practical threat. Some of the extra assumptions needed for message recovery have not been checked on real examples because the calculations become too large.
It’s useful to step back and look at the Classic McEliece system itself. In 1978, Robert McEliece introduced a public-key encryption method built on error-correcting codes. An error-correcting code is a carefully chosen set of strings of zeros and ones that can survive the accidental flipping of a limited number of bits. The owner of the system keeps a secret description of one such efficient code. To create a public key, the owner mixes that secret code with random scrambling so that the public version looks unstructured. Anyone can use the public key to send a message by adding a controlled amount of random noise. Only the owner, who knows the original secret structure, can remove the noise and recover the message. Everyone else faces what appears to be a hard random decoding problem.
Classic McEliece is the modern form of this construction, using a particular family of codes called binary Goppa codes. It was selected as a finalist in the National Institute of Standards and Technology (NIST) post-quantum cryptography process and later advanced to later rounds. Although another code-based scheme (Hamming Quasi-Cyclic; HQC) was ultimately chosen for standardization by NIST, Classic McEliece itself was incorporated into an ISO international standard ISO/IEC 18033-2 in 2026. It is already used in practice as one component of hybrid post-quantum key establishment in certain secure communication systems. Its public keys are large, but its ciphertexts are among the shortest of any post-quantum candidate.
Code-based cryptography, more broadly, relies on the difficulty of decoding a noisy linear code when the underlying structure is hidden. Its security comes from the fact that finding the original message after noise has been added is believed to be hard even for large-scale quantum computers. These systems are candidates for post-quantum cryptography because they do not rely on the number-theoretic problems that quantum algorithms can solve efficiently. Instead, they use combinatorial and algebraic problems that are believed to remain difficult under quantum attack. Classic McEliece is one of the oldest and most studied members of this family.
The new paper shows that an attacker can determine whether a given public key comes from this family or is simply random data. This is comparable to noticing that a particular lock, even though it looks ordinary from the outside, has a distinctive internal mechanism that a trained eye can recognize without being able to open the lock. Such recognition in and of itself does not grant entry, but it does change perceptions of the lock’s uniqueness. In cryptographic terms, the ability to distinguish structured public keys from random ones indicates that the public data is not as featureless as a purely random matrix. Earlier work had already shown ways to find structure, but those methods were either slower or relied on heuristic assumptions. The new method is faster in the relevant parameter ranges and rests on unconditional reasoning for the distinguishing step.
The researchers turned the insight from the private-information-retrieval attempt into a concrete test. They held out part of the public matrix, computed a space of polynomials that vanished on the rest, and checked whether those polynomials also vanished on the held-out part. For genuine McEliece keys, the answer is always yes. For random matrices, the answer is usually no. By adjusting the parameters carefully, they obtained a reliable distinction. They then examined the concrete key sizes that appeared in standardization discussions and estimated the computational and memory costs. The time estimates improved on prior structure-finding approaches. The memory figures, however, remained enormous.
The findings show that the asymptotic picture (the long-term growth rate of the attack as the system parameters become arbitrarily large) for structural attacks on Classic McEliece has changed. Earlier distinguishing methods required effort that grew nearly exponentially with key parameters. The new method grows more slowly, in a quasipolynomial fashion. The same ideas also open a possible path toward recovering messages under additional assumptions. That path remains not yet fully verified or mapped. The paper leaves several clear next questions including whether the method can be made faster and less memory-hungry, whether the message-recovery step can be turned into a fully proven algorithm, whether the same ideas can be strengthened to recover the entire secret key, how many other similar encryption systems are affected, and whether any encryption system built from this family of codes can ultimately avoid a certain fundamental size penalty that the results appear to force.
While those questions are interesting, they don’t change Classic McEliece’s security guarantees. Despite this, the results matter because they refine the security landscape without overturning it. Classic McEliece still rests on the hardness of decoding under noise, a problem the new work does not solve. The ability to notice structure is useful information for designers and analysts, but it does not translate into a practical attack. The memory barrier alone places the method far outside real-world reach. Therefore, there are no immediate use cases in which an adversary could apply the technique against deployed systems.
The research encourages closer examination of the algebraic properties of public keys and should prompt designers to consider whether stronger randomness properties are needed. It also illustrates how ideas from one area of theoretical computer science, private information retrieval, can unexpectedly benefit another area, in this case post-quantum encryption. For Classic McEliece, the work supplies a clearer picture of what structural information is visible and what remains hidden. For code-based cryptography more generally, it suggests that the boundary between structured and unstructured public data may be thinner than previously assumed in certain regimes, while still leaving the core decoding problem, and thus the core security guarantees, intact.
Real-world impacts are currently limited to the research community. No operational system needs to change its parameters or its usage practices based on this result. The enormous resource requirements ensure that the attack remains a laboratory observation rather than a field threat. The natural next steps are to test the remaining assumptions more thoroughly, to explore whether memory can be reduced, and to determine whether the framework extends cleanly to full key recovery. Those investigations will decide whether the new perspective remains a theoretical clarification or eventually contributes to more concrete cryptanalytic tools. In the meantime, the Classic McEliece system continues to stand on the hardness of the decoding task and the security guarantees that the paper leaves untouched.
This article is shared at no charge for educational and informational purposes only.
Red Sky Alliance is a Cyber Threat Analysis and Intelligence Service organization. We provide indicators of compromise information (CTI) via a notification/Tier I analysis service (RedXray) or an analysis service (CTAC). For questions, comments, or assistance, please contact the office directly at 1-844-492-7225 or feedback@redskyalliance.com
- Reporting: https://www.redskyalliance.org/
- Website: https://www.redskyalliance.com/
- LinkedIn: https://www.linkedin.com/company/64265941
Weekly Cyber Intelligence Briefings:
REDSHORTS - Weekly Cyber Intelligence Briefings
https://attendee.gotowebinar.com/register/7855487668891299929
[1] https://six3ro.substack.com/p/when-a-hidden-pattern-emerges-in
Comments