la veille

[hdrcouchot.git] / annexePreuveMarquagedhci.tex

diff --git a/annexePreuveMarquagedhci.tex b/annexePreuveMarquagedhci.tex
index 57de268b9c00296b782d77b11a5c4dcc14cc5a94..817e62246baa636f7500bfdd96a2995cb06c182b 100644 (file)
--- a/annexePreuveMarquagedhci.tex
+++ b/annexePreuveMarquagedhci.tex
@@ -1,43 +1,36 @@
 
 

-\begin{theorem}\label{th:stego}
-Soit  $\epsilon$ un nombre positif, 
-$l$ un nombre de LSBs, 
-$X   \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
-un adapteur de stratégie uniformémement distribué indépendant de $X$
-$f_l$ un mode tel que  
-$\textsc{giu}(f_l)$ est fortement connexe et la 
-matrice de Markov associée à  $f_l$ est doublement stochastique.
-Il existe un nombre $q$ d'itérations tel que 
-$|p(Y|K)- p(X)| < \epsilon$. 
-\end{theorem}
+Prouvons le théorème suivant.
+\theoremstegoscureepsilon*

 
 
 
 \begin{proof}   
 
 
 
 \begin{proof}   

-Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and 
-$\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value
-of any  binary number in $\Bool^{l}$.
-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 
-$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$.
-Let $i \in \llbracket 0, 2^l -1 \rrbracket$, 
-the probability $p(\textit{deci}(X^{t+1})= i)$  is 
+Soit $\textit{deci}$ la bijection
+entre $\Bool^{l}$ et
+$\llbracket 0, 2^l-1 \rrbracket$ qui associe la valeur décimale 
+à chaque nombre binaire dans $\Bool^{l} $.
+La probabilité $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ pour $e_j \in \Bool^{l}$ est égale à 
+$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$, notée par la suite $\pi^t$.
+Pour $i \in \llbracket 0, 2^l -1 \rrbracket$, 
+la probabilité  $p(\textit{deci}(X^{t+1})= i)$  est 

 \[
  \sum\limits^{2^l-1}_{j=0}  
 \sum\limits^{l}_{k=1} 
 p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) 
 \]
 \noindent 
 \[
  \sum\limits^{2^l-1}_{j=0}  
 \sum\limits^{l}_{k=1} 
 p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) 
 \]
 \noindent 

-where $ i =_k j $ is true iff the binary representations of 
-$i$ and $j$ may only differ for the  $k$-th element,
-and where 
-$i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of 
+où  $ i =_k j $ est vraie si et seulement si les représentations binaires de 
+$i$ et de  $j$ ne diffèrent que pour le $k^{\textrm{ème}}$ élément et 
+où 
+$i_k$ représente dans cette preuve  le $k^{\textrm{ème}}$ élément dans la représentation binaire 
+du nombre

 $i$.
 
 $i$.
 

-Next, due to the proposition's hypotheses on the strategy,
-$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to  
+En raison des hypothèses sur la stratégie, la probabilité 
+$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ est égale à

 $\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.
 $\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.

-Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the 
-iterative process  and thus does not depend on $X^t$, we have 
+Enfin, puisque $i =_k j$ et  $f_k(j) = i_k$ sont constants 
+et sont donc indépendants de  $X^t$, on a 

 \[
 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
 \pi^t_j.\frac{1}{l}  
 \[
 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
 \pi^t_j.\frac{1}{l}  


@@ -45,53 +38,53 @@ iterative process  and thus does not depend on $X^t$, we have
 p(i =_k j, f_k(j) = i_k ).
 \]
 
 p(i =_k j, f_k(j) = i_k ).
 \]
 

-Since 
+Puisque 

 $\frac{1}{l}  
 \sum\limits^{l}_{k=1} 
 p(i =_k j, f_k(j) = i_k ) 
 $\frac{1}{l}  
 \sum\limits^{l}_{k=1} 
 p(i =_k j, f_k(j) = i_k ) 

-$ is equal to $M_{ji}$ where  $M$ is the Markov matrix associated to
- $f_l$ we thus have
+$ est égal à  $M_{ji}$ où  $M$ est la matrice de Markov associée à 
+ $f_l$, on a ainsi

 \[
 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
 \[
 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}

-\pi^t_j. M_{ji} \textrm{ and thus }
+\pi^t_j. M_{ji} \textrm{ et donc }

 \pi^{t+1} = \pi^{t} M.
 \]
 
 % The calculus of $p(X^{t+1} = e)$ is thus equal to 
 % $\pi^{t+1}_i$. 
 
 \pi^{t+1} = \pi^{t} M.
 \]
 
 % The calculus of $p(X^{t+1} = e)$ is thus equal to 
 % $\pi^{t+1}_i$. 
 

-First of all, 
-since the graph $\Gamma(f)$ is strongly connected,
-then for all vertices $i$ and $j$, a path can
-be  found to  reach $j$  from $i$  in at  most $2^l$  steps.  
-There  exists thus $k_{ij} \in \llbracket 1,  2^l \rrbracket$ s.t.
+Maintenant, puisque le graphe  $\Gamma(f)$ est fortement connexe,
+pour chaque couple de sommets $(i,j)$, un chemin peut être trouvé de $i$ jusqu'à $j$ 
+de longueur au plus égale à $2^l$.
+Il existe donc  $k_{ij} \in \llbracket 1,  2^l \rrbracket$ t.q.

 ${M}_{ij}^{k_{ij}}>0$.  
 ${M}_{ij}^{k_{ij}}>0$.  

-As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that 
-${M}_{ij}^{l\times  k_{ij}}>0$, 
-we can  conclude that, if
-$k$ is the least common multiple of $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \}$ thus 
-$\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ and thus 
-$M$ is a regular stochastic matrix.
+
+Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
+${M}_{ij}^{l\times  k_{ij}}>0$, on peut conclure que si 
+$k$ est le PPCM de $\left\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \right\}$ alors
+$\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ et donc 
+$M$ est une matrice stochastique régulière. 
+

 
 
 
 

-Let us now recall the following stochastic matrix theorem:
-\begin{theorem}[Stochastic Matrix]
-  If $M$ is a regular stochastic matrix, then $M$ 
-  has an unique stationary  probability vector $\pi$. Moreover, 
-  if $\pi^0$ is any initial probability vector and 
-  $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$
-  converges to $\pi$ as $t$ tends to infinity.
+\begin{theorem}
+  Si $M$ est une matrice stochastique régulière, alors $M$ 
+  possède un unique vecteur stationnaire de probabilités  $\pi$
+  ($\pi.M = \pi$).
+  De plus, si $\pi^0$ est un vecteur de probabilité
+ et si on définit 
+  la suite $(\pi^{k})^{k \in  \Nats}$ par 
+  $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
+  alors la chaîne de Markov $\pi^k$
+  converge vers $\pi$ lorsque $k$ tend vers l'infini.

 \end{theorem}
 
 \end{theorem}
 

-Thanks to this theorem, $M$ 
-has an unique stationary  probability vector $\pi$. 
-By hypothesis, since $M$ is doubly stochastic we have 
+Grâce à ce théorème,  $M$ admet un unique vecteur stationnaire de probabilité $\pi$. 
+Par hypothèses, puisque $M$ est doublement stochastique, on a 

 $(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
 $(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$

-and thus $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
-Due to the matrix theorem, there exists some 
-$q$ s.t. 
-$|\pi^q- \pi| < \epsilon$
-and the proof is established.
-Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure
-provided the strategy-adapter is uniformly distributed.
+et donc $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
+Il existe donc $q$ t.q.
+$|\pi^q- \pi| < \epsilon$.
+Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stégo-sécure
+pour peu que l'adapteur de stratégie soit uniformément distribué.

  \end{proof}
  \end{proof}