Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes
This work is incremental, improving cryptanalysis for specific cryptographic systems by extending attacks to broader genera.
The authors developed a polynomial-time attack on the McEliece cryptosystem when it uses subcodes of algebraic geometry codes, addressing a limitation in prior work that only handled genus zero cases.
We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.