Squares of Random Linear Codes

DOI10.1109/TIT.2015.2393251zbMATH Open1359.94682arXiv1407.0848OpenAlexW2108277687MaRDI QIDQ2978722FDOQ2978722

Authors: Ignacio Cascudo, Ronald Cramer, Diego Mirandola, Gilles Zémor 

Publication date: 28 April 2017

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

Abstract: Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code "typically" fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $frac12k^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cited In (12)

• Title not available (Why is that?)
• Squares of matrix-product codes
• A class of constacyclic codes are generalized Reed-Solomon codes
• A new approach based on quadratic forms to attack the McEliece cryptosystem
• Structural properties of self-dual monomial codes with application to code-based cryptography
• Some new classes of additive MDS and almost MDS codes over finite fields
• Properties of constacyclic codes under the Schur product
• High dimensional affine codes whose square has a designed minimum distance
• On the dimension and structure of the square of the dual of a Goppa code
• Quantum resistant public key encryption scheme polarRLCE
• Construction of MDS twisted Reed-Solomon codes and LCD MDS codes
• Secret Sharing Schemes with Algebraic Properties and Applications

This page was built for publication: Squares of Random Linear Codes

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