Y. V. Kosolapov, O. Y. Turchenko, “Application of one method of linear code recognition to the wire-tap channel”, Prikl. Diskr. Mat., 2017, no. 35, 76

Abstract: A security model using the method of code noising is considered. It is assumed that the information blocks of length

k

$k$ contain a fixed message

m

$\mathbf m$ of length

m_{l}

$m_l$

(m_{l} \leq k)

$(m_l\leq k)$ on a fixed position

m_{s}

$m_s$

(1 \leq m_{s} \leq k - m_{l} + 1)

$(1\leq m_s\leq k-m_l+1)$ , and an observer gets noisy codewords of length

n

$n$ through a

q

$q$ -ary symmetric channel

q S C (p)

$q\mathrm{SC}(p)$ (

q

$q$ — prime power) with error probability

p

$p$ (

p < 1 / q)

$p<1/q)$ for each non-zero value. The aim of the observer is to find the unknown message

m

$\mathbf m$ , when the position

m_{s}

$m_s$ and the length

m_{l}

$m_l$ are unknown. In this paper, we propose a statistical method for finding message

m

$\mathbf m$ . The method is based on the idea of code recognition in noisy environment: we test hypothesis

H_{0}

$H_0$ (received vectors have been generated by a conjectural code

C

$\mathcal C$ ) against the hypothesis

H_{1}

$H_1$ (received vectors have not been generated by

C

$\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

C

$\mathcal C$ noised in a symmetric channel

q S C (p (2 - q p))

$q\mathrm{SC}(p(2-qp))$ . To determine the length

m_{l}

$m_l$ and place

m_{s}

$m_s$ of the unknown message

m

$\mathbf m$ , we recognize the code

C

$\mathcal C$ from the calculated differences of the received vectors. For this purpose, we present a code recognition algorithm (called

C o d e R e c o g n i t i o n

$\mathrm{CodeRecognition}$ ) and prove that if

C

$\mathcal C$ is a linear

[n, k]

$[n,k]$ code and

M C, α, β)

$M\mathcal C,\alpha,\beta)$ is the minimum number of vectors (received from the channel

q S C (p)

$q\mathrm{SC}(p)$ ) that are sufficient for

C o d e R e c o g n i t i o n

$\mathrm{CodeRecognition}$ algorithm to test the hypothesis

H_{0}

$H_0$ against the hypothesis

H_{1}

$H_1$ by using a constructed statistical criterion, then

M (C, α, β) \leq f^{2} (k + 1)

$M(\mathcal C,\alpha,\beta)\leq f^2(k +1)$ , where

f (x) = \frac{b (1 + (q - 2) (1 - p q)^{x} - (q - 1) (1 - p q)^{2 x})^{1 / 2} - a}{\sqrt{q - 1} (1 - p q)^{x}},

$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 = Φ^{- 1} (α)

$a=\Phi^{-1}(\alpha)$ ,

b = Φ^{- 1} (1 - β)

$b=\Phi^{-1}(1-\beta)$ ;

Φ^{- 1}

$\Phi^{-1}$ – Laplacian inverse function. We show that the bound above is achieved in the case of Maximum Distance Separable (MDS) codes

C

$\mathcal C$ . On the base of this result, we obtain a sufficient number of vectors corresponding to the channel

q S C (p (2 - q p))

$q\mathrm{SC}(p(2-qp))$ . We also present some algorithms for finding the position

m_{s}

$m_s$ , the length

m_{l}

$m_l$ , and the message

m

$\mathbf m$ . The main component of them is the algorithm

C o d e R e c o g n i t i o n

$\mathrm{CodeRecognition}$ .