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 m of length mi (mi ^ k) on a fixed position m<sub>s</sub> (1 ^ m<sub>s</sub> ^ k - m<sub>i</sub> + 1), and an observer gets noisy codewords of length n through a q-ary symmetric channel qSC(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 m, when the position m<sub>s</sub> and the length mi are unknown. In this paper, we propose a statistical method for finding message m. The method is based on the idea of code recognition in noisy environment: we test hypothesis H<sub>0 </sub>(received vectors have been generated by a conjectural code C) against the hypothesis H<sub>i</sub> (received vectors have not been generated by 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 noised in a symmetric channel qSC(p(2 - qp)). To determine the length m<sub>i</sub> and place m<sub>s </sub>of the unknown message m, we recognize the code C from the calculated differences of the received vectors. For this purpose, we present a code recognition algorithm (called CodeRecognition) and prove that if C is a linear [n, k] code and M(C, а, в) is the minimum number of vectors (received from the channel qSC(p)) that are sufficient for CodeRecognition algorithm to test the hypothesis H<sub>0</sub> against the hypothesis H<sub>1 </sub>by using a constructed statistical criterion, then M(C, a, в) < f <sup>2</sup>(k + 1), where <sub>f</sub> (x) = b(1 + (q - 2)(1 - pq)<sup>x</sup> - (q - 1)(1 - pq)<sup>2x</sup>)<sup>1/2</sup> - a <sup>f</sup> (x) = Vq-1(1 - pq)<sup>x</sup>, a and в are the probabilities of errors of the first kind and the second kind, respectively; a = Ф<sup>-1</sup>(а), b = Ф<sup>-1</sup>(1 - в); Ф<sup>-1</sup> - Laplacian inverse function. We show that the bound above is achieved in the case of Maximum Distance Separable (MDS) codes C. On the base of this result, we obtain a sufficient number of vectors corresponding to the channel qSC(p(2 - qp)). We also present some algorithms for finding the position m<sub>s</sub>, the length mi, and the message m. The main component of them is the algorithm CodeRecognition.