[Resource Topic] 2020/1131: Several classes of minimal binary linear codes violating the Aschikhmin-Barg's bound

Welcome to the resource topic for 2020/1131

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

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


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} \leq 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 [n+1, 2^{n-2}]. The second approach addresses a specification of characteristic functions covering the weights in [2^{n-2}+1, 2^{n-2} + 2^{n-3}-1] and containing a skewed (removing one element) affine subspace of dimension n-2. Finally, we also characterize an infinite family of such codes that utilize the class of so-called root Boolean functions of weight 2^{n-1}-(n-1), 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.

ePrint: https://eprint.iacr.org/2020/1131

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .