International Association
for Cryptologic Research

The best attacks known against the McEliece cryptosystem have cost growing exponentially with the number of errors corrected by the error-correcting code used in the cryptosystem. One can modify the cryptosystem to asymptotically increase this number of errors, for the same key size and the same ciphertext size, by generalizing classical binary Goppa codes to subfield subcodes of algebraic-geometry codes, and then moving from genus 0 to higher genus. This paper introduces streamlined algorithms for code generation and decoding for a broad class of these codes; shows that this class includes classical binary Goppa codes; and shows that moving to higher genus within this class decodes more errors than classical binary Goppa codes for concrete sizes of cryptographic interest. A notable feature of this paper's algorithms is the use of arithmetic on the Jacobian variety of the underlying curve.

<p> We analyze Layered ROLLO-I, a code-based cryptosystem published in IEEE Communications Letters and submitted to the Korean post-quantum cryptography competition. Four versions of Layered ROLLO-I have been proposed in the competition. We show that the first two versions do not provide the claimed security against rank decoding attacks and give reductions to small instances of the original ROLLO-I scheme, which was a candidate in the NIST competition and eliminated there due to rank decoding attacks. As a second contribution, we provide two efficient message recovery attacks, affecting every security level of the first three versions of Layered ROLLO-I and security levels 128 and 192 of the fourth version. </p>