Application of one method of linear code recognition to the wire-tap channel | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 35. DOI: 10.17223/20710410/35/7

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