2 \begin{theorem}\label{th:stego}
3 Soit $\epsilon$ un nombre positif,
5 $X \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
6 un adapteur de stratégie uniformémement distribué indépendant de $X$
8 $\textsc{giu}(f_l)$ est fortement connexe et la
9 matrice de Markov associée à $f_l$ est doublement stochastique.
10 Il existe un nombre $q$ d'itérations tel que
11 $|p(Y|K)- p(X)| < \epsilon$.
17 Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and
18 $\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value
19 of any binary number in $\Bool^{l}$.
20 The probability $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ for $e_j \in \Bool^{l}$ is thus equal to
21 $(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$.
22 Let $i \in \llbracket 0, 2^l -1 \rrbracket$,
23 the probability $p(\textit{deci}(X^{t+1})= i)$ is
25 \sum\limits^{2^l-1}_{j=0}
27 p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k )
30 where $ i =_k j $ is true iff the binary representations of
31 $i$ and $j$ may only differ for the $k$-th element,
33 $i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of
36 Next, due to the proposition's hypotheses on the strategy,
37 $p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to
38 $\frac{1}{l}.p(\textit{deci}(X^t) = j , i =_k j, f_k(j) = i_k)$.
39 Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the
40 iterative process and thus does not depend on $X^t$, we have
42 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
45 p(i =_k j, f_k(j) = i_k ).
51 p(i =_k j, f_k(j) = i_k )
52 $ is equal to $M_{ji}$ where $M$ is the Markov matrix associated to
55 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
56 \pi^t_j. M_{ji} \textrm{ and thus }
57 \pi^{t+1} = \pi^{t} M.
60 % The calculus of $p(X^{t+1} = e)$ is thus equal to
64 since the graph $\Gamma(f)$ is strongly connected,
65 then for all vertices $i$ and $j$, a path can
66 be found to reach $j$ from $i$ in at most $2^l$ steps.
67 There exists thus $k_{ij} \in \llbracket 1, 2^l \rrbracket$ s.t.
68 ${M}_{ij}^{k_{ij}}>0$.
69 As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that
70 ${M}_{ij}^{l\times k_{ij}}>0$,
71 we can conclude that, if
72 $k$ is the least common multiple of $\{k_{ij} \big/ i,j \in \llbracket 1, 2^l \rrbracket \}$ thus
73 $\forall i,j \in \llbracket 1, 2^l \rrbracket, {M}_{ij}^{k}>0$ and thus
74 $M$ is a regular stochastic matrix.
77 Let us now recall the following stochastic matrix theorem:
78 \begin{theorem}[Stochastic Matrix]
79 If $M$ is a regular stochastic matrix, then $M$
80 has an unique stationary probability vector $\pi$. Moreover,
81 if $\pi^0$ is any initial probability vector and
82 $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$
83 converges to $\pi$ as $t$ tends to infinity.
86 Thanks to this theorem, $M$
87 has an unique stationary probability vector $\pi$.
88 By hypothesis, since $M$ is doubly stochastic we have
89 $(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
90 and thus $\pi = (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
91 Due to the matrix theorem, there exists some
93 $|\pi^q- \pi| < \epsilon$
94 and the proof is established.
95 Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure
96 provided the strategy-adapter is uniformly distributed.