New estimates for dimension of Reed — Muller subcodes with maximum Hadamard square

The existence of some structure in a code can lead to decreasing the security of the whole system built on it. Often subcodes are used to “disguise” the code as a “general-looking” one. However, the security of subcodes with Hadamard square equal to the square of the base code is reduced to the security of the latter. Thus, it is necessary to take this property into account during both synthesis and cryptanalysis of code schemes. In the paper, the authors analyse the minimum number of monomials of degree $r$, which, when added to the code $RM(r-1, m)$, result in a subcode with maximal Hadamard square, that is, coinciding with $RM(2r,m)$. The problem is reformulated in terms of hypergraphs where vertices correspond to variables and each monomial of degree $k$ is associated with a $k$-edge. A set of $r$-edges covering all $2r$-sets is searched. The minimum size of such a set is estimated from below as $w(m,r) \ge \sqrt{\gamma +2\text{C}_m^{2r}}+\sqrt{\gamma}$, where $\gamma = \sum\limits_{i=\max\{1,3r-m\}}^{r-1}\text{C}_r^i$. A greedy algorithm constructing a “good” set is proposed to obtain an upper bound. At each step the algorithm adds a new $r$-edge choosing the “least covered” vertices.