Talk
Polynomial time attack on high rate random alternant codes
Talk by Rocco Mora
Speaker invited by: Prof. Dr. Joachim Rosenthal
Date: 31.05.23 Time: 16.30 - 17.30 Room: Y27H25
In this talk, we present a polynomial-time key-recovery algorithm retrieving the algebraic structure of a high-rate alternant code. This positively answers the long-standing open question regarding whether the distinguisher of high-rate alternant or Goppa codes can be turned into an attack. In particular, our algorithm works for all distinguishable parameters as long as the code is a generic alternant code and when the code field size q is either 2 or 3. This has been achieved by two different ingredients: (i) a way of using code shortening and the component-wise product of codes to derive from the original alternant code a sequence of alternant codes of decreasing degree up to getting an alternant code of degree 3; (ii) an original Gröbner basis approach that takes into account the non-standard constraints on the multiplier and support of an alternant code and that recovers in polynomial time the relevant algebraic structure of an alternant code of degree 3.
(**This eSeminar will take place over Zoom, using the same meeting details as previous seminars. If you do not have meeting details, please contact zita.fiquelideabreu@math.uzh.ch **)