Application of one method of linear code recognition to the wire-tap channel
Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 76-88

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

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$ ($p1/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}$.
Keywords: code noising, $q$-ary symmetric channel, code recognition.
@article{PDM_2017_1_a6,
     author = {Y. V. Kosolapov and O. Y. Turchenko},
     title = {Application of one method of linear code recognition to the wire-tap channel},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {76--88},
     publisher = {mathdoc},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_1_a6/}
}
TY  - JOUR
AU  - Y. V. Kosolapov
AU  - O. Y. Turchenko
TI  - Application of one method of linear code recognition to the wire-tap channel
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 76
EP  - 88
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_1_a6/
LA  - ru
ID  - PDM_2017_1_a6
ER  - 
%0 Journal Article
%A Y. V. Kosolapov
%A O. Y. Turchenko
%T Application of one method of linear code recognition to the wire-tap channel
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 76-88
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_1_a6/
%G ru
%F PDM_2017_1_a6
Y. V. Kosolapov; O. Y. Turchenko. Application of one method of linear code recognition to the wire-tap channel. Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 76-88. http://geodesic.mathdoc.fr/item/PDM_2017_1_a6/