Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

DOI10.1007/978-3-319-17296-5_13MaRDI QIDQ3460457zbMATH OpenOpenAlexFDO

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

Publication date 7 January 2016

Published in Coding Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

algebraic geometry codescode-based cryptographydistinguishersSchur products of codes

Mathematics Subject Classification ID

Cryptography (94A60) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Abstract: 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.

Recommendations

• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• scientific article; zbMATH DE number 4070796
• McEliece public key cryptosystems using algebraic-geometric codes
• Weak keys in the McEliece public-key cryptosystem
• On the edge-independence number and edge-covering number for regular graphs

Cites work

• A characterization of MDS codes that have an error correcting pair
• Algebraic Function Fields and Codes
• Algebraic geometric codes. Basic notions
• Computational aspects of retrieving a representation of an algebraic geometry code
• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Decoding algebraic-geometric codes up to the designed minimum distance
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• How to mask the structure of codes for a cryptographic use
• scientific article; zbMATH DE number 3989251 (Why is no real title available?)
• Information-set decoding for linear codes over F_q
• Majority coset decoding
• McEliece public key cryptosystems using algebraic-geometric codes
• On decoding by error location and dependent sets of error positions
• On the decoding of algebraic-geometric codes
• On the edge-independence number and edge-covering number for regular graphs
• On the unique representation of very strong algebraic geometry codes
• Polynomial time attack on wild McEliece over quadratic extensions
• The non-gap sequence of a subcode of a generalized Reed-Solomon code
• Varieties Defined by Quadratic Equations

Cited in

(15)

• McEliece public key cryptosystems using algebraic-geometric codes
• Classification of Hadamard products of one-codimensional subcodes of Reed-Muller codes
• Computational aspects of retrieving a representation of an algebraic geometry code
• Algebraic attack against variants of McEliece with Goppa polynomial of a special form
• Algebraic Cryptanalysis of the PKC’2009 Algebraic Surface Cryptosystem
• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Code-based cryptosystems using generalized concatenated codes
• Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
• On linear codes with random multiplier vectors and the maximum trace dimension property
• A Hadamard product of linear codes: algebraic properties and algorithms for calculating it
• Constructions of LCD codes from their Schur products
• Towards the security of McEliece's cryptosystem based on Hermitian subfield subcodes
• Hadamard square of series connected linear codes
• Hadamard square of linear codes and the generalized minimal distance of Reed-Muller code of order 2
• Higher-genus McEliece

This page was built for publication: Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

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