Applied Coding Theory

A non-asymptotic estimate of the probability that a Shur — Hadamard square of long random linear code has a maximum dimension

I. V. Chizhov<sup>abc

a</sup> Lomonosov Moscow State University, Moscow, Russia
^b Federal Research Center “Computer Science and Control” of the RAS, Moscow, Russia
^c Joint Stock “Research and production company Kryptonite”, Moscow, Russia

Abstract: Let $ \mathbb{F}_q $ be a finite field of $ q $ elements. Let $ \mathcal{V}_n(q) $ denote the vector space of length $ n $ over $ \mathbb{F}_q $. Define a linear $ [n,k]_q $-code $ \mathcal{C} $ as any linear subspace of dimension $ k $ of the space $ \mathcal{V}_n(q) $. This paper focuses on a special operation defined on the set of linear codes of the same length: the Schur — Hadamard product, also known as the Schur product or Hadamard product. The Schur — Hadamard product of two vectors $ x = (x_1, \ldots, x_n) \in \mathcal{V}_n(q) $ and $ y = (y_1, \ldots, y_n) \in \mathcal{V}_n(q) $ is defined as the vector $ x \circ y = (x_1 \cdot y_1, \ldots, x_n \cdot y_n) \in \mathcal{V}_n(q), $ where $ \cdot $ is the field $ \mathbb{F}_q $ multiplication. Define the Schur — Hadamard square $ \mathcal{C}^{\circ 2} $ of $ [n]_q $-code $ \mathcal{C} $ as the linear span of the set of vectors $ \{ c \circ b : c, b \in \mathcal{C} \} $. It is known that for any $ [n,k]_q $-code $ \mathcal{C} $ the inequality $ \dim \mathcal{C}^{\circ 2} \le \min\left( {k(k+1)}/{2}, n \right) $ holds. For a random linear code, the probability that its Schur — Hadamard square has the maximum possible dimension tends to 1 as $ n, k \to \infty $. This fact is used in the analysis of code-based cryptosystems. However, in practice researchers deal with fixed values of $ k $ and $ n $. Therefore, the non-asymptotic estimation of the probability that the Schur — Hadamard square of a random $ [n,k]_q $-code has the maximum possible dimension is of interest. In the case $ n < {k(k+1)}/{2} $ such an estimate was obtained earlier. We provide a non-asymptotic estimate for the case $ n > {k(k+1)}/{2} $. Two theorems are proven: the first gives an estimate for very long codes, while the second applies to relatively short codes. Let $ k, n \in \mathbb{N} $ be such that $ k \ge 5 $ and $ n > {k(k+1)}/{2} $. Then the following inequality holds:
$$ \mathrm{Pr}\,\left[ \dim \mathcal{C}^{\circ 2} = {k(k+1)}/{2} \right] > 1 - q^{{k(k+1)}/{2} + \log_q 2 - (2 - \log_q (2q-1)) n}. $$
If $ k \ge 6 $ and $ n < (k^2 - 4k)/{2(\log_q (2q-1)-1)} $, then
$$ \mathrm{Pr}\,\left[ \dim \mathcal{C}^{\circ 2} = {k(k+1)}/{2} \right] > 1 - q^{{k(k+1)}/{2} + \log_q 2 - \left( 1 - \log_q \left( 1 + (q-1)q^{-\delta_q (n,k) k} \right) \right) n}, $$
where $ \delta_q (n,k) = \dfrac{1}{2} + \dfrac{1}{2k} - \dfrac{1}{2k} \sqrt{2k + 1 + 2(\log_q (2q-1) - 1) n}. $ Finally, examples of estimates are given for different values of $ n $, $ k $ and $ q $.

Keywords: Shur product of linear codes, Hadamard product of linear codes, random codes, Shur square of linear code, Hadamard square of linear code, McEliece public key cryptosystem.

UDC: 519.725

DOI: 10.17223/20710410/68/4