Steganographic capacity for one-dimensional Markov cover} \runningtitle{Steganographic capacity for one-dimensional Markov cover} \author*[1]{Valeriy A. Voloshko} \runningauthor{V. A. Voloshko} \affil[1]{ Belarusian State University, e-mail: valeravoloshko@yandex.ru} \abstract{For shift-invariant probability measures on the set of infinite two-sided binary sequences (one-dimensional covers) we introduce the notion of capacity as a maximum portion of embedded into the cover uniformly distributed (purely random) binary sequence (message) that admits special correction of the cover restoring its distribution up to distribution of $n$-tuples (subwords of some fixed length $n$). “Special correction” is carried out using the proposed new algorithm that changes some of the cover's symbols not occupied by embedded message. The features of the introduced capacity are examined for the Markov cover. In particular, we show how capacity may be significantly increased by weakening of the standard constraint that positions for message embedding have to be chosen by independent unfair coin tosses. Experimental results are presented for correction of real steganographic covers after LSB-embedding.} \keywords{binary sequence, shift-invariant measure, steganography, capacity

For shift-invariant probability measures on the set of infinite two-sided binary sequences (one-dimensional covers) we introduce the notion of capacity as a maximum portion of embedded into the cover uniformly distributed (purely random) binary sequence (message) that admits special correction of the cover restoring its distribution up to distribution of $n$-tuples (subwords of some fixed length $n$). “Special correction” is carried out using the proposed new algorithm that changes some of the cover's symbols not occupied by embedded message. The features of the introduced capacity are examined for the Markov cover. In particular, we show how capacity may be significantly increased by weakening of the standard constraint that positions for message embedding have to be chosen by independent unfair coin tosses. Experimental results are presented for correction of real steganographic covers after LSB-embedding.} \keywords{binary sequence, shift-invariant measure, steganography, capacity