Application of one method of linear code recognition to the wire-tap channel

Y. V. Kosolapov ; O. Y. Turchenko

Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 76-88.

Résumé

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}$.

Détail

Keywords: code noising, $q$-ary symmetric channel, code recognition.

Bibliographie

[1] Wyner A. D., “The wire-tap channel”, Bell Sys. Tech. J., 54 (1975), 1355–1387 | DOI | MR | Zbl

[2] Korzhik V. I., Yakovlev V. A., “Nonasymptotic estimates for efficiency of code jamming in a wire-tap channel”, Probl. Peredachi Inf., 17:4 (1981), 11–18 (in Russian) | MR | Zbl

[3] Ivanov V. A., “Statistical estimation of the code noising efficiency”, Tr. Diskr. Mat., 6, 2002, 48–63 (in Russian)

[4] Kosolapov Y. V., Turchenko O. Y., “Search of an information message in noisy code blocks at repeated data transmission”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2016, no. 9, 55–57 (in Russian)

[5] Weidmann C., “Coding for the $q$-ary symmetric channel with moderate $q$”, IEEE Int. Symp. Inform. Theory, 2008, 2156–2159

[6] Couvreur A., “Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes”, Designs, Codes and Cryptography, 73:2 (2014), 641–666 | DOI | MR | Zbl

[7] Sidel'nikov V. M., Coding Theory, Fizmatlit Publ., Moscow, 2008, 324 pp. (in Russian)

[8] Chabot C., “Recognition of a code in a noisy environment”, Proc. IEEE ISIT, June 2007, 2211–2215

[9] Yardi A. D., Vijayakumaran S., “Detecting linear block codes in noise using the GLRT”, Proc. IEEE Intern. Conf. Communications (Budapest, Hungary, June 9–13, 2013), 4895–4899; Кн. 2, 408 с.

[10] Shiryaev A. N., Probability, MCCME Publ., Moscow, 2004 (in Russian) | MR