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 12k2 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)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Error-correcting codes
Contact author(s)
diego @ cwi nl
History
2015-01-14: last of 2 revisions
2014-07-03: received
See all versions
Short URL
https://ia.cr/2014/520
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2014/520}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.