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 ms (1 ^ ms ^ k - mi + 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 s 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 H0 (received vectors have been generated by a conjectural code C) against the hypothesis Hi (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 mi and place ms 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 H0 against the hypothesis H1 by using a constructed statistical criterion, then M(C, a, в) 2(k + 1), where f (x) = b(1 + (q - 2)(1 - pq)x - (q - 1)(1 - pq)2x)1/2 - a f (x) = Vq-1(1 - pq)x, a and в are the probabilities of errors of the first kind and the second kind, respectively; a = Ф-1(а), b = Ф-1(1 - в); Ф-1 - 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 ms, the length mi, and the message m. The main component of them is the algorithm CodeRecognition.