Paper 2014/520
Squares of Random Linear Codes
Ignacio Cascudo, Ronald Cramer, Diego Mirandola, and Gilles Zémor
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 $\frac{1}{2}k^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2n$ 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.
Note: Final version, to appear on IEEE Transactions on Information Theory
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Errorcorrecting codes
 Contact author(s)
 diego @ cwi nl
 History
 20150114: last of 2 revisions
 20140703: received
 See all versions
 Short URL
 https://ia.cr/2014/520
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/520, author = {Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Gilles Zémor}, title = {Squares of Random Linear Codes}, howpublished = {Cryptology ePrint Archive, Paper 2014/520}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/520}}, url = {https://eprint.iacr.org/2014/520} }