Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)
Programs & Events >

Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)

Speaker: Ashrujit Ghoshal

Cryptography
  • Date 28 October 2026
  • Location SSB 334
  • Time 3:30 PM - 4:30 PM

Abstract

The McEliece cryptosystem, introduced in 1978 and based on binary Goppa codes, is the oldest public-key encryption scheme still considered secure against quantum attacks. Its remarkable longevity rests in part on the apparent difficulty of distinguishing a McEliece public key from a random linear code.
In this talk, I will describe a simple classical quasipolynomial-time distinguisher for Goppa-McEliece in the asymptotic regime underlying Classic McEliece. For code length n, the algorithm runs in time n^{O(log n)} and distinguishes a McEliece public key from a uniformly random binary linear code with advantage 1-o(1). The attack is not purely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and gives improved, although still far from practical, concrete attack estimates.
Interestingly, the attack arose from an unsuccessful attempt to construct doubly efficient private information retrieval (PIR) schemes from algebraic locally decodable codes. I will explain the distinguisher through this PIR perspective, which gives a relatively intuitive view of the structure being exploited. Finally, I will discuss heuristic extensions of the distinguisher to quasipolynomial-time ciphertext decryption and key recovery. The key-recovery attack, in particular, remains structurally close to the distinguisher and may have implications for concrete security estimates of Classic McEliece.
This is joint work with Yuval Ishai, Aayush Jain and Nuozhou Sun.

Bio

Ashrujit Ghoshal is an Assistant Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Madras. His research lies in the foundations of cryptography, with a focus on understanding the security of cryptographic systems and designing efficient privacy-preserving protocols. His work spans cryptographic time-space tradeoffs, the security of hash functions and proof systems, and private information retrieval (PIR). His research has appeared at leading conferences, including CRYPTO, EUROCRYPT, TCC, and the IEEE Symposium on Security and Privacy.
Before joining IIT Madras, he was a postdoctoral fellow at Carnegie Mellon University. He received his Ph.D. in Computer Science from the University of Washington and his B.Tech. (Hons.) in Computer Science and Engineering from IIT Kharagpur.