Geodesic
Detection of embeddings in binary Markov chains
Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 123-144.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is concerned with problems in steganography on the detection of embeddings and statistical estimation of positions at which message bits are embedded. Binary stationary Markov chains with known or unknown matrices of transition probabilities are used as mathematical models of cover sequences (container files). Based on the runs statistics and the likelihood ratio statistic, statistical tests are constructed for detecting the presence of embeddings. For a family of contiguous alternatives, the asymptotic power of statistical tests based on the runs statistics is found. An algorithm of polynomial complexity is developed for the statistical estimation of positions with embedded bits. Results of computer experiments are presented.
Keywords: steganography, model of embeddings, Markov chain, statistical test, power, total number of runs. 
@article{DM_2015_27_3_a8,
     author = {Yuriy S. Kharin and Egor V. Vecherko},
     title = {Detection of embeddings in binary {Markov} chains},
     journal = {Diskretnaya Matematika},
     pages = {123--144},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_3_a8/}
}
TY  - JOUR
AU  - Yuriy S. Kharin
AU  - Egor V. Vecherko
TI  - Detection of embeddings in binary Markov chains
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 123
EP  - 144
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_3_a8/
LA  - ru
ID  - DM_2015_27_3_a8
ER  - 
%0 Journal Article
%A Yuriy S. Kharin
%A Egor V. Vecherko
%T Detection of embeddings in binary Markov chains
%J Diskretnaya Matematika
%D 2015
%P 123-144
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_3_a8/
%G ru
%F DM_2015_27_3_a8
Yuriy S. Kharin; Egor V. Vecherko. Detection of embeddings in binary Markov chains. Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 123-144. http://geodesic.mathdoc.fr/item/DM_2015_27_3_a8/

[1] Ponomarev K. I., “Parametricheskaya model vkrapleniya i ee statisticheskii analiz”, Diskretnaya matematika, 214:4 (2009), 148–157 | DOI | MR

[2] Ponomarev K. I., “Ob odnoi statisticheskoi modeli steganografii”, Diskretnaya matematika, 21:2 (2009), 138–145 | DOI | MR | Zbl

[3] Ker A., “A capacity result for batch steganography”, IEEE Signal Process. Lett., 14:8 (2007), 525–528 | DOI

[4] Shoitov A.M., “O vyyavlenii fakta zashumleniya konechnoi tsepi Markova s neizvestnoi matritsei perekhodnykh veroyatnostei”, Prikladnaya diskretnaya matematika, 2010, 44–45

[5] Kharin Yu. S., Vecherko E. V., “Statisticheskoe otsenivanie parametrov modeli vkraplenii v dvoichnuyu tsep Markova”, Diskretnaya matematika, 25:2 (2013), 135–148 | DOI | MR | Zbl

[6] Zubkov A. M., “Datchiki psevdosluchainykh chisel i ikh primeneniya”, Trudy II Mezhdunar. nauchn. konf. “Matematika i bezopasnost informatsionnykh tekhnologii”, MGU, 2003, 200–206 | MR | Zbl

[7] Kemeni Dzh. G., Snell Dzh. L., Konechnye tsepi Markova, Nauka, Moskva, 1970

[8] Ivanov V.A., “Modeli vkraplenii v odnorodnye sluchainye posledovatelnosti”, Trudy po diskretnoi matematike, 10, 2008, 18–34

[9] A statistical test suite for random and pseudorandom number generators for cryptographic applicatiions, NIST Special Publication 800-22 Rev. 1a, Nat. Inst. Stand. Technol., 2010

[10] Doukhan P., Mixing: properties and examples, Springer-Verlag, 1994 | MR | Zbl

[11] Kharin Yu. S., Voloshko V. A., “Robust estimation of AR coefficients under simultaneously influencing outliers and missing values”, J. Statist. Plan. Infer., 141:9 (2011), 3276–3288 | DOI | MR | Zbl

[12] Ivchenko G. I., Medvedev Yu. I., Matematicheskaya statistika, Vysshaya shkola, Moskva, 1984 | MR

[13] Wald A., “Tests of statistical hypotheses concerning several parameters when the number of observations is large”, Trans. Amer. Math. Soc., 54, no. 3, 1943, 426–482 | MR | Zbl

[14] Rabiner L. R., “A tutorial on hidden Markov models and selected applications in speech recognition”, Proc. IEEE, 77, no. 2, 1989, 257–286

[15] Yu. S. Kharin, A. I. Petlitskii, “Tsep Markova $s$-go poryadka s $r$ chastichnymi svyazyami i statisticheskie vyvody o ee parametrakh”, Diskretnaya matematika, 19:2 (2007), 109–130 | DOI | MR | Zbl