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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Minimal linear codesAschikhmin-Barg's boundCharacteristic functionsRoot Boolean functions.
Contact author(s)
rene7ca @ gmail com
2020-09-21: received
Short URL
Creative Commons Attribution


      author = {Enes Pasalic and René Rodríguez and Fengrong Zhang and Yongzhuang Wei},
      title = {Several classes of minimal binary linear codes violating the Aschikhmin-Barg's bound},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1131},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.