annexePreuveMarquagedhci.tex

   1
   2 Prouvons le théorème suivant.
   3 \theoremstegoscureepsilon*
   4
   5
   6
   7 \begin{proof}
   8 Soit $\textit{deci}$ la bijection
   9 entre $\Bool^{l}$ et
  10 $\llbracket 0, 2^l-1 \rrbracket$ qui associe la valeur décimale
  11 à chaque nombre binaire dans $\Bool^{l} $.
  12 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 à
  13 $(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$, notée par la suite $\pi^t$.
  14 Pour $i \in \llbracket 0, 2^l -1 \rrbracket$,
  15 la probabilité  $p(\textit{deci}(X^{t+1})= i)$  est
  16 \[
  17  \sum\limits^{2^l-1}_{j=0}
  18 \sum\limits^{l}_{k=1}
  19 p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k )
  20 \]
  21 \noindent
  22 où  $ i =_k j $ est vraie si et seulement si les représentations binaires de
  23 $i$ et de  $j$ ne diffèrent que le $k^{\textrm{ème}}$ élément et
  24 où
  25 $i_k$ représente dans cette preuve  le $k^{\textrm{ème}}$ élément dans la représentation binaire
  26 du nombre
  27 $i$.
  28
  29 En raison des hypothèses sur la stratégie, la probabilité
  30 $p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ est égale à
  31 $\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.
  32 Enfin, puisque $i =_k j$ et  $f_k(j) = i_k$ sont constant
  33 et sont donc indépendants de  $X^t$, on a
  34 \[
  35 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
  36 \pi^t_j.\frac{1}{l}
  37 \sum\limits^{l}_{k=1}
  38 p(i =_k j, f_k(j) = i_k ).
  39 \]
  40
  41 Puisque
  42 $\frac{1}{l}
  43 \sum\limits^{l}_{k=1}
  44 p(i =_k j, f_k(j) = i_k )
  45 $ est égal à  $M_{ji}$ où  $M$ est la matrice de Markov associée à
  46  $f_l$, on a ainsi
  47 \[
  48 \pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
  49 \pi^t_j. M_{ji} \textrm{ et donc }
  50 \pi^{t+1} = \pi^{t} M.
  51 \]
  52
  53 % The calculus of $p(X^{t+1} = e)$ is thus equal to
  54 % $\pi^{t+1}_i$.
  55
  56 Maintenant, puisque le graphe  $\Gamma(f)$ est fortement connexe,
  57 pour chaque couple de sommets $(i,j)$, un chemin peut être trouvé de $i$ jusqu'à $j$
  58 de longueur au plus égale à $2^l$.
  59 Il existe donc  $k_{ij} \in \llbracket 1,  2^l \rrbracket$ t.q.
  60 ${M}_{ij}^{k_{ij}}>0$.
  61
  62 Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
  63 ${M}_{ij}^{l\times  k_{ij}}>0$, on peut conclure que si
  64 $k$ est le PPCM de $\left\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \right\}$ alors
  65 $\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ et donc
  66 $M$ est une matrice stochastique régulière.
  67
  68
  69
  70 \begin{theorem}
  71   Si $M$ est une matrice stochastique régulière, alors $M$
  72   possède un unique vecteur stationnaire de probabilités  $\pi$
  73   ($\pi.M = \pi$).
  74   De plus, si $\pi^0$ est un vecteur de probabilité
  75  et si on définit
  76   la suite $(\pi^{k})^{k \in  \Nats}$ par
  77   $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$
  78   alors la chaîne de Markov $\pi^k$
  79   converge vers $\pi$ lorsque $k$ tend vers l'infini.
  80 \end{theorem}
  81
  82 Grâce à ce théorème,  $M$ admet un unique vecteur stationnaire de probabilité $\pi$.
  83 Par hypothèses, puisque $M$ est doublement stochastique, on a
  84 $(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
  85 et donc $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
  86 Il existe donc $q$ t.q.
  87 $|\pi^q- \pi| < \epsilon$.
  88 Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stego-secure
  89 pour peu que l'adapteur de stratégie soit uniformément distribué.
  90  \end{proof}