Paper 2020/1131

Several classes of minimal binary linear codes violating the Aschikhmin-Barg's bound

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

Abstract

Minimal linear codes are a special class of codes which have important applications in secret sharing and secure two-party computation. These codes are characterized by the property that none of the codewords is covered by some other codeword. Denoting by $w_{min}$ and $w_{max}$ minimal and maximal weight of the codewords respectively, such codes are relatively easy to design when the ratio $w_{min}/w_{max}>1/2$ (known as Aschikhmin-Barg's bound). On the other hand, there are few known classes of minimal codes violating this bound, hence having the property $w_{min}/w_{max}\le 1/2$. In this article, we provide several explicit classes of minimal binary linear codes violating the Aschikhmin-Barg's bound, at the same time achieving a great variety of the ratio $w_{min}/w_{max}$. Our first generic method employs suitable characteristic functions of relatively low weight within the range $$. The second approach addresses a specification of characteristic functions covering the weights in $$ and containing a skewed (removing one element) affine subspace of dimension $$. Finally, we also characterize an infinite family of such codes that utilize the class of so-called root Boolean functions of weight $$, which are useful in certain hardware testing applications. Consequently, many infinite classes of minimal codes crossing the Aschikhmin-Barg's bound, with a wide range of the weight of their characteristic functions, are deduced. In certain cases we also completely specify the weight distribution of resulting codes.