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.

Bibliographie

[1] Deundyak V. M., Kosolapov Yu. V., “O nekotorykh svoistvakh proizvedeniya Shura — Adamara dlya lineinykh kodov i ikh prilozheniyakh”, Prikladnaya diskretnaya matematika, 2020, no. 50, 72–86 | Zbl

[2] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[3] Chizhov I. V., “Obobschennye avtomorfizmy koda Rida — Mallera i kriptosistema Mak-Elisa — Sidelnikova”, Prikladnaya diskretnaya matematika. Prilozhenie, 2009, no. 1, 36–37 | Zbl

[4] Deundyak V. M., Kosolapov Yu. V., “O nekotorykh svoistvakh proizvedeniya Shura — Adamara dlya lineinykh kodov i ikh prilozheniyakh”, Prikladnaya diskretnaya matematika, 2020, no. 50, 72–86 | Zbl

[5] International Olympiad in Cryptography NSUCRYPTO, (data obrascheniya 30.10.2020) https://nsucrypto.nsu.ru

[6] Sidelnikov V. M., “Otkrytoe shifrovanie na osnove dvoichnykh kodov Rida — Mallera”, Diskretnaya matematika, 6 (1994), 3–20 | Zbl

[7] Vedunova M. V., Geut K. L., Ignatova A. O., “Prelomlyayuschie biektsii v troikakh Shteinera”, Prikladnaya diskretnaya matematika. Prilozhenie, 2020, no. 13, 6–8

[8] Logachev O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2004, 470 pp.

[9] Vysotskaya V. V., “Kvadrat koda Rida — Mallera i klassy ekvivalentnosti sekretnykh klyuchei kriptosistemy Mak-Elisa — Sidelnikova”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 66–68

[10] Gainanov D. N., Novokshenov L. I., Tyagunov L. I., “O grafakh, porozhdaemykh nesovmestnymi sistemami lineinykh neravenstv”, Matem. zametki, 33:2 (1983), 146–150 | MR

[11] Mazurov V. D., Khachai M. Yu., “Busting i polinomialnaya approksimiruemost zadachi o minimalnom affinnom razdelyayuschem komitete”, Tr. IMM UrO RAN, 19, no. 2, 2013, 231–236