Cryptology ePrint Archive: Report 2020/1398

A huge class of infinite sequences of minimal binary linear codes with or without crossing the Ashikhmin-Barg’s bound

Fengrong Zhang and Enes Pasalic and René Rodríguez and Yongzhuang Wei

Abstract: A special class of linear codes, having important applications in secret sharing and secure two-party computation, called minimal is characterized by the property that none of the codewords is covered by some other codeword. Denoting by $w_{min}$ and $w_{max}$ the minimal and maximal weight of a binary linear code respectively, a sufficient but not necessary condition for achieving minimality is that $w_{min} /w_{max} > 1/2$ (called Ashikhmin-Barg’s bound). Those minimal codes satisfying the condition $w_{min} /w_{max} \leq 1/2$ are called wide in this article (generally harder to construct), whereas codes satisfying $w_{min} /w_{max} > 1/2$ are called narrow. In this article, we first show that the so-called direct sum of Boolean functions of the form $h(x,y) = f(x) + g(y)$ induces narrow minimal codes whenever g is a bent function. Then, we introduce the concept of non-covering permutations (referring to the property of minimality) which is shown to be sufficient for providing many infinite classes of minimal binary linear codes of larger dimension by employing a suitable subspace of derivatives of the bent function g. In the second part of this article, we first provide one efficient method (with easily satisfied initial conditions) of generating wide minimal codes. Then, we again consider the use of derivatives (along with the underlying Boolean function given as the direct sum) for the purpose of defining another class of wide minimal codes. To the best of our knowledge, the latter method is the most general framework for designing wide binary linear codes. It uses a (suitable) subspace of derivatives of $h(x,y) = f(x) + g(y)$, where $g$ is a bent function and f satisfies certain minimality requirements. For a fixed suitable function $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.

Category / Keywords: foundations / Minimal linear codes; Ashikhmin-Barg’s bound; Derivatives; Direct sum.