### 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 so-called 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{non-covering 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 so-called Ashikhmin-Barg 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 non-covering permutations. To the best of our knowledge, the latter method is the most general framework for designing binary minimal linear codes that violate the Ashikhmin-Barg 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 non-equivalent 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 Maiorana-McFarland class. The weight distribution is given explicitly for any (suitable) $f$ when $\phi$ is an almost bent permutation.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Minimal linear codesAshikhmin-Barg’s boundDerivativesDirect sum.
Contact author(s)
rene7ca @ gmail com
History
2021-09-22: revised
See all versions
Short URL
https://ia.cr/2020/1398

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.