Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes

DOI10.1109/TIT.2017.2712636MaRDI QIDQ5369878zbMATH OpenOpenAlexFDO

Authors Alain Couvreur, Irene Márquez-Corbella, Ruud Pellikaan

Publication date 19 October 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6025

Mathematics Subject Classification ID

Cryptography (94A60) Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Abstract: We give polynomial time attacks on the McEliece public key cryptosystem based either on algebraic geometry (AG) codes or on small codimensional subcodes of AG codes. These attacks consist in the blind reconstruction either of an Error Correcting Pair (ECP), or an Error Correcting Array (ECA) from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm that corrects up to $frac{d}^{\ast }-1-g2$ errors, where $d^{\ast }$ denotes the designed distance and $g$ denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to $frac{d}^{\ast }-12$ errors. Roughly speaking, for a public code of length $n$ over $mathbb{F}_q$, these attacks run in $O(n^{4}log(n))$ operations in $mathbb{F}_q$ for the reconstruction of an ECP and $O(n^5)$ operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to $O(n^{3+varepsilon}log(n))$ and $O(n^{4+varepsilon})$. Compared to the previous known attack due to Faure and Minder, our attack is efficient on codes from curves of arbitrary genus. Furthermore, we investigate how far these methods apply to subcodes of AG codes.

Recommendations

• McEliece public key cryptosystems using algebraic-geometric codes
• Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes
• Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes
• Cryptanalysis of the McEliece public key cryptosystem based on polar codes
• Algebraic cryptanalysis of McEliece variants with compact keys
• Cryptanalysis of McEliece’s Public-Key Cryptosystem
• Structural cryptanalysis of McEliece schemes with compact keys
• scientific article; zbMATH DE number 1302794
• An efficient attack of a McEliece cryptosystem variant based on convolutional codes
• A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes

Cited in

(20)

• Squares of matrix-product codes
• Theory of supports for linear codes endowed with the sum-rank metric
• On the structure of the Schur squares of twisted generalized Reed-Solomon codes and application to cryptanalysis
• Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes
• ECC\(^2\): error correcting code and elliptic curve based cryptosystem
• On the structural security of a McEliece-type cryptosystem based on the sum of tensor products of binary Reed - Muller codes
• Encryption scheme based on expanded Reed-Solomon codes
• The McEliece-type cryptosystem based on D-codes
• Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
• Higher-genus McEliece
• On linear codes with random multiplier vectors and the maximum trace dimension property
• Calculation of error-correcting pairs for an algebraic-geometric code
• Isometry-Dual Flags of Many-Point AG Codes
• Cryptanalysis of a system based on twisted Reed-Solomon codes
• Power error locating pairs
• Algebraic-geometry codes and decoding by error-correcting pairs
• Towards the security of McEliece's cryptosystem based on Hermitian subfield subcodes
• On calculation of error-correcting pairs for PELP algorithm for algebraic-geometry codes
• Attack on the ECC2 cryptosystem and the McEliece cryptosystem built on elliptic codes
• Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369878)