Doctoral Speaking Skills Talk - Nuozhou Sun
September 24, 2026 4:30PM—5:30PM
Location:
7501
-
Gates and Hillman Centers
Speaker:
NUOZHOU SUN,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://sunnuozhou.github.io/
The McEliece code-based cryptosystem, utilizing binary Goppa codes, is the earliest public-key encryption scheme that is still considered post-quantum secure. In this talk, I will present a simple, classical quasipolynomial-time distinguisher for Goppa–McEliece in the asymptotic “Classic McEliece” regime: for code length `n`, extension degree `m = Θ(log n)`, Goppa degree `t = Θ(n/log n)`, and public-code dimension `k = Θ(n)`, the algorithm runs in time `n^O(log n)` and distinguishes the McEliece public key from the uniform distribution. The distinguisher is not merely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and yields improved, though not yet practical, concrete attack estimates. I will also briefly discuss extensions of this provable algorithm to a heuristic `n^O(log n)`-time ciphertext-decryption attack that recovers the message from a noisy codeword and a heuristic `n^O(log n)`-time key-recovery attack that outputs an equivalent decryption key. While the decryption attack is not concretely efficient, the key-recovery attack is much closer to the distinguisher and may be relevant to NIST security levels.
Event Website:
https://sites.google.com/view/crypto-seminar/home
Contact
Matt Stewart