Bases over the field $\mathrm{GF(2)}$ generated by the Schur~--- Hadamard operation

K. L. Geut ; S. S. Titov

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 154-158

Résumé

The paper deals with the problem of constructing, describing and applying bases of vector spaces over the field $\mathrm{GF(2)}$ generated by the componentwise product operation up to degree $d$. This problem “Bases” was posed as unsolved in the Olympiad in cryptography NSUCRYPTO. In order to give a way to solve this problem with the Reed — Muller codes, we define the generating family $\mathcal{F}$ as a list of all string $i$ in a true table under condition: the word $x^1_i , \ldots, x^s_i$ has Hamming weight not superior $d$. The values of coefficients of function $f$ are determined recurrently, as in the proof of the theorem on ANF: the coefficient before composition for subset $T$ (cardinality does not exceed $d$) in the set $\{t^1,\ldots,t^s\}$ of arguments is determined as the sum of the values of $f$ and the values of the coefficients for the whole subset $R\subseteq T$. Hence, for all $s,d$, $s \geq d > 1$, there is a basis for which such a family exists, and the construction of the bases is described above. We propose to use general affine group on space $F^s$, $F=\mathrm{GF}(2)$, for obtaining the class of such bases in the condition of the problem.

Détail

Mots-clés : NSUCRYPTO
Keywords: orthomorphisms, vector space basis, Reed — Muller code.