Geodesic
New estimates for dimension of Reed~--- Muller subcodes with maximum Hadamard square
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 98-100.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: post-quantum cryptography, code-based cryptography, Reed — Muller subcodes, Reed — Muller codes, McEliece cryptosystem.
Mots-clés : Hadamard product 
@article{PDMA_2020_13_a27,
     author = {V. V. Vysotskaya},
     title = {New estimates for dimension of {Reed~---} {Muller} subcodes with maximum {Hadamard} square},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {98--100},
     publisher = {mathdoc},
     number = {13},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a27/}
}
TY  - JOUR
AU  - V. V. Vysotskaya
TI  - New estimates for dimension of Reed~--- Muller subcodes with maximum Hadamard square
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 98
EP  - 100
IS  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a27/
LA  - ru
ID  - PDMA_2020_13_a27
ER  - 
%0 Journal Article
%A V. V. Vysotskaya
%T New estimates for dimension of Reed~--- Muller subcodes with maximum Hadamard square
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 98-100
%N 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a27/
%G ru
%F PDMA_2020_13_a27
V. V. Vysotskaya. New estimates for dimension of Reed~--- Muller subcodes with maximum Hadamard square. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 98-100. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a27/

[1] https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization/Call-for-Proposals

[2] Chizhov I. V., Borodin M. A., “Klassifikatsiya proizvedenii Adamara podkodov korazmernosti 1 kodov Rida — Mallera”, Diskretnaya matematika, 32:1 (2020), 115–134

[3] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 1978, no. 4244, 114–116

[4] Vysotskaya V. V., Characteristics of Hadamard Square of Reed — Muller Subcodes of Special Type, https://eprint.iacr.org/2020/507