Paper 2020/1398
Minimal binary linear codes  a general framework based on bent concatenation
Fengrong Zhang, Enes Pasalic, René Rodríguez, and Yongzhuang Wei
Abstract
Minimal codes are characterized by the property that none of the codewords is covered by some other linearly independent codeword. We first show that the use of a bent function $g$ in the socalled direct sum of Boolean functions $h(x,y)=f(x)+g(y)$, where $f$ is arbitrary, induces minimal codes. This approach gives an infinite class of minimal codes of length $2^n$ and dimension $n+1$ (assuming that $h: \F_2^n \rightarrow \F_2$), whose weight distribution is exactly specified for certain choices of $f$. To increase the dimension of these codes with respect to their length, we introduce the concept of \textit{noncovering permutations} (referring to the property of minimality) used to construct a bent function $g$ in $s$ variables, which allows us to employ a suitable subspace of derivatives of $g$ and generate minimal codes of dimension $s+s/2+1$ instead. Their exact weight distribution is also determined. In the second part of this article, we first provide an efficient method (with easily satisfied initial conditions) of generating minimal $[2^n,n+1]$ linear codes that cross the socalled AshikhminBarg bound. This method is further extended for the purpose of generating minimal codes of larger dimension $n+s/2+2$, through the use of suitable derivatives along with the employment of noncovering permutations. To the best of our knowledge, the latter method is the most general framework for designing binary minimal linear codes that violate the AshikhminBarg bound. More precisely, for a suitable choice of derivatives of $h(x,y)=f(x) + g(y)$, where $g$ is a bent function and $f$ satisfies certain minimality requirements, for any fixed $f$, one can derive a huge class of nonequivalent wide binary linear codes of the same length by varying the permutation $\phi$ when specifying the bent function $g(y_1,y_2)=\phi(y_2)\cdot y_1$ in the MaioranaMcFarland class. The weight distribution is given explicitly for any (suitable) $f$ when $\phi$ is an almost bent permutation.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Minimal linear codesAshikhminBarg’s boundDerivativesDirect sum.
 Contact author(s)
 rene7ca @ gmail com
 History
 20210922: revised
 20201110: received
 See all versions
 Short URL
 https://ia.cr/2020/1398
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1398, author = {Fengrong Zhang and Enes Pasalic and René Rodríguez and Yongzhuang Wei}, title = {Minimal binary linear codes  a general framework based on bent concatenation}, howpublished = {Cryptology ePrint Archive, Paper 2020/1398}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1398}}, url = {https://eprint.iacr.org/2020/1398} }