Application of one method of linear code recognition to the wire-tap channel

A security model using the method of code noising is considered. It is assumed that the information blocks of length $k$ contain a fixed message $\mathbf m$ of length $m_l$ $ (m_l\leq k)$ on a fixed position $m_s$ $(1\leq m_s\leq k-m_l+1)$, and an observer gets noisy codewords of length $n$ through a $q$-ary symmetric channel $q\mathrm{SC}(p)$ ($q$— prime power) with error probability $p$ ($p<1/q)$ for each non-zero value. The aim of the observer is to find the unknown message $\mathbf m$, when the position $m_s$ and the length $m_l$ are unknown. In this paper, we propose a statistical method for finding message $\mathbf m$. The method is based on the idea of code recognition in noisy environment: we test hypothesis $H_0$ (received vectors have been generated by a conjectural code $\mathcal C$) against the hypothesis $H_1$ (received vectors have not been generated by $\mathcal C$ or it's subcode). The method is as follows. From the observed vectors, the independent pairwise differences of them are compiled. The resulting vectors are code words of some unknown code $\mathcal C$ noised in a symmetric channel $q\mathrm{SC}(p(2-qp))$. To determine the length $m_l$ and place $m_s$ of the unknown message $\mathbf m$, we recognize the code $\mathcal C$ from the calculated differences of the received vectors. For this purpose, we present a code recognition algorithm (called $\mathrm{CodeRecognition}$) and prove that if $\mathcal C$ is a linear $[n,k]$ code and $M\mathcal C,\alpha,\beta)$ is the minimum number of vectors (received from the channel $q\mathrm{SC}(p)$) that are sufficient for $\mathrm{CodeRecognition}$ algorithm to test the hypothesis $H_0$ against the hypothesis $H_1$ by using a constructed statistical criterion, then $M(\mathcal C,\alpha,\beta)\leq f^2(k +1)$, where
$$ f(x)=\frac{b(1+(q-2)(1-pq)^x-(q-1)(1-pq)^{2x})^{1/2} -a}{\sqrt{q-1}(1-pq)^x}, $$
$\alpha$ and $\beta$ are the probabilities of errors of the first kind and the second kind, respectively; $a=\Phi^{-1}(\alpha)$, $b=\Phi^{-1}(1-\beta)$; $\Phi^{-1}$ – Laplacian inverse function. We show that the bound above is achieved in the case of Maximum Distance Separable (MDS) codes $\mathcal C$. On the base of this result, we obtain a sufficient number of vectors corresponding to the channel $q\mathrm{SC}(p(2-qp))$. We also present some algorithms for finding the position $m_s$, the length $m_l$, and the message $\mathbf m$. The main component of them is the algorithm $\mathrm{CodeRecognition}$.