From 523864c862215a63c5133568a9771f5b8f60c89e Mon Sep 17 00:00:00 2001 From: couchot Date: Mon, 12 Sep 2016 21:17:11 +0200 Subject: [PATCH] relecture --- 14Secrypt.tex | 98 ++-- 15RairoGen.tex | 6 +- ahmad.tex | 2 +- annexePreuveMarquageCorrectioncompletude.tex | 70 +-- annexePreuveMarquagedhci.tex | 109 ++--- annexePreuveMarquagefldblement.tex | 88 ++-- annexePreuveStopping.tex | 483 ++++++++----------- annexePreuvesComplexiteStego.tex | 7 +- main.tex | 14 +- oxford.tex | 147 +++--- stabylo.tex | 78 ++- stegoyousra.tex | 10 +- 12 files changed, 473 insertions(+), 639 deletions(-) diff --git a/14Secrypt.tex b/14Secrypt.tex index e36720b..858a8e5 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -371,7 +371,7 @@ plus, comme dans tout code de Gray cyclique, $\textit{TC}_n(i)$ est pair $\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec $\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou -$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et +$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$. \begin{xpl} @@ -509,10 +509,17 @@ P=\dfrac{1}{6} \left( \] \end{xpl} -On remarque que dans cette marche on reste sur place avec une probabilité - - +On remarque que dans cette marche on reste sur place avec une probabilité égale +à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin +lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$. +Les probabilités usuelles que l'on appliquerait aux transitions de +l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales +à $\frac{1}{\mathsf{N}}$. +Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. +Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006} +considère cette marche comme cadre. S'inspirant de +celle-ci, le travail suivant se replace donc dans ce cadre théorique. Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur @@ -536,73 +543,32 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$ et $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ - -Un résultat classique est - -$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - - - -Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de -$\Bool^{\mathsf{N}}$. -Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un -\emph{temps d'arrêt} pour la suite -$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq -(\Bool^{\mathsf{N}})^{t+1}$ tel que -$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs -de -$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. - -Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et -$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. -Un \emph{temps d'arrêt aléatoire} pour la chaîne de -Markov est un temps d'arrêt pour -$(Z_t)_{t\in\mathbb{N}}$. -Si la chaîne de Markov est irréductible et a $\pi$ -comme distribution stationnaire, alors un -\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire -(qui peut dépendre de la configuration initiale $X$), -tel que la distribution de $X_\tau$ est $\pi$: -$$\P_X(X_\tau=Y)=\pi(Y).$$ - - -Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$ -est indépendant de $\tau$. On a les deux théorèmes suivants, dont les -démonstrations sont données en annexes~\ref{anx:generateur}. +Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire +pour être proche de la distribution stationnaire à $\varepsilon$ prêt, +peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}. -\begin{theorem} -Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} -\P_X(\tau > t)$. -\end{theorem} - - -Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction -telle que pour $X \in \Bool^{\mathsf{N}} $, -$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. -La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$, -$\ov{h}(\ov{h}(X))\neq X$. +\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix} +\label{theo:tmps:mix} +On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de +probabilités $p$ définie sur l'ensemble des arcs comme suit: +\[ +p(e) \left\{ +\begin{array}{ll} += \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\ += \frac{1}{2\mathsf{N}} \textrm{ sinon.} +\end{array} +\right. +\] +La chaîne de Markov associée converge vers la distribution uniforme et -\begin{restatable}[Majoration du temps d'arrêt]{theorem}{theostopmajorant} -\label{prop:stop} -Si $\ov{h}$ est bijective et anti involutive -$\ov{h}(\ov{h}(X))\neq X$, alors -$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. +\[ +\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2). +\] \end{restatable} -Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}. -On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement -l'algorithme~\ref{CI Algorithm}. En effet dans la section présente, -la probabilité de rester dans une configuration donnée -est fixée à $\frac{1}{2}+\frac{1}{2n}$. -Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$. -Cette version, qui reste davantage sur place que l'algorithme original, -a été introduite pour simplifier le calcul d'un majorant -du temps d'arrêt. Sans entrer dans les détails de la preuve, on remarque aussi @@ -620,7 +586,7 @@ dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien. On peut évaluer ceci pratiquement: pour une fonction $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale -$x^0$, le code donné à l'algorithme ~\ref{algo:stop} retourne le +$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$ en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans @@ -1090,7 +1056,7 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl \section{Conclusion} -Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir +Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir de codes de Gray équilibrés. Une méthode complètement automatique de construction de ce type de codes a été présentée étendant les méthodes existantes. diff --git a/15RairoGen.tex b/15RairoGen.tex index d905e51..432991f 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -14,7 +14,7 @@ présente tout d'abord l'algorithme de PRNG. La contrainte de distribution uniforme de la sortie est discutée dans cette section. La chaoticité du générateur est ensuite étudiée en section~\ref{prng:unaire:chaos}. -La section~\ref{sub:prng:algo} a été publiéeà~\cite{bcgw11:ip,bcgr11:ip}. +La section~\ref{sub:prng:algo} a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}. \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo} @@ -671,7 +671,7 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva \item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de $\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque $k$, $0 \le k \le p_i-1$, on a - $u_k$ qui apaprtient à $[\mathsf{N}]$ et + $u_k$ qui appartient à $[\mathsf{N}]$ et $y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$. @@ -762,7 +762,7 @@ est fortement connexe. Ce chapitre a proposé un algorithme permettant de construire un PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois -possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov assosiée soit doublement stochastique. +possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique. Le chapitre suivant montre comment construire une telle fonction. diff --git a/ahmad.tex b/ahmad.tex index 05d9177..0f09bdd 100644 --- a/ahmad.tex +++ b/ahmad.tex @@ -113,7 +113,7 @@ $\bigcup_{1\le i \le k} M_i \subseteq [N]$. selon le nouveau vecteur de positions ${x'}$. \end{enumerate} -Voyons comment extraire une marque d'une document PDF. +Voyons comment extraire une marque d'un document PDF. \subsection{Extraction de la marque} diff --git a/annexePreuveMarquageCorrectioncompletude.tex b/annexePreuveMarquageCorrectioncompletude.tex index dd6ad42..76e6e5c 100644 --- a/annexePreuveMarquageCorrectioncompletude.tex +++ b/annexePreuveMarquageCorrectioncompletude.tex @@ -1,64 +1,34 @@ -\begin{theorem} -La condition de l'algorithme de marquage est nécressaire et suffisante -pour permettre l'extraction du message du média marqué. -\end{theorem} + +\marquagecorrectioncompl* \begin{proof} -For sufficiency, let $d_i$ be the last iteration (date) the element $i \in \Im(S_p)$ -of $x$ has been modified:% is defined by +Pour la suffisance, soit $d_i$ la dernière itération où l'élément $i \in \Im(S_p)$ +de la configuration $x$ a été modifié:% is defined by $$ d_i = \max\{j | S^j_p = i \}. $$ -Let $D=\{d_i|i \in \Im(S_p) \}$. -The set $\Im(S_c)_{|D}$ is thus -the restriction of the image of $S_c$ to $D$. +Soit $D=\{d_i|i \in \Im(S_p) \}$. +L'ensemble $\Im(S_c)_{|D}$ est donc la restriction de l'image de $S_c$ à $D$. -The host that results from this iteration scheme is thus -$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ where -$x^l_i$ is either $x^{d_i}_i$ if $i$ belongs to $\Im(S_p)$ or $x^0_i$ otherwise. -Moreover, for each $i \in \Im(S_p)$, the element $x^{d_i}_i$ is equal to +Le vecteur qui résutle de ces itérations est donc +$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ où +$x^l_i$ est soit $x^{d_i}_i$ si $i$ appartient à $\Im(S_p)$ ou $x^0_i$ sinon. +De plus, pour chaque $i \in \Im(S_p)$, l'élément $x^{d_i}_i$ est égal à $m^{d_i-1}_{S^{d_i}_c}$. -Thanks to constraint \ref{itm2:Sc}, all the indexes -$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ belong to +Sous hypothèse que la contrainte imposée soit réalisée, tous les indices +$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ appartiennent à $\Im(S_c)_{|D}$. -Let then $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ s.t. +On a alors $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ tel que $S^{d_i}_c=j$. -Thus we have all the elements $m^._j$ of the vector $m$. -Let us focus now on some $m^{d_i-1}_j$. -Thus the value of $m^0_j$ can be immediately -deduced by counting in $S_c$ how many -times the component $j$ has been switched -before $d_i-1$. +On retrouve ainsi tous les éléments $m^._j$ du vecteur $m$. +A partir de $m^{d_i-1}_j$, +la valeur de $m^0_j$ peut être déduite en comptant dans $S_c$ combien de fois +l'élément $j$ a été invoqué avant $d_i-1$. -Let us focus now on necessity. -If $\Im(S_c)_{|D} \subsetneq +Réciproquement, si $\Im(S_c)_{|D} \subsetneq \llbracket 0 ;\mathsf{P} -1 \rrbracket$, -there exist some $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ that -do not belong to $\Im(S_c)_{|\Im(S_p)}$. -Thus $m_j$ is not present in $x^l$ and the message cannot be extracted. +i lexiste un $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ qui n'appartient pas à $\Im(S_c)_{|\Im(S_p)}$. +Ainsi, $m_j$ n'est pas présent dans $x^l$ et le message ne peut pas extrait. \end{proof} -When the constraint \ref{itm2:Sc} is satisfied, we obtain a scheme -that always finds the original message provided the watermarked media -has not been modified. -In that context, correctness and completeness are established. - - -Thanks to constraint~\ref{itm2:Sc}, the cardinality $k$ of -$\Im(S_p)$ is larger than $\mathsf{P}$. -Otherwise the cardinality of $D$ would be smaller than $\mathsf{P}$ -and similar to the cardinality of $\Im(S_c)_{|D}$, -which is contradictory. - -One bit of index $j$ of the original message $m^0$ -is thus embedded at least twice in $x^l$. -By counting the number of times this bit has been switched in $S_m$, the value of -$m_j$ can be deduced in many places. -Without attack, all these values are equal and the message is immediately -obtained. - After an attack, the value of $m_j$ is obtained as mean value of all -its occurrences. -The scheme is thus complete. -Notice that if the cover is not attacked, the returned message is always equal to the original -due to the definition of the mean function. diff --git a/annexePreuveMarquagedhci.tex b/annexePreuveMarquagedhci.tex index 57de268..22187f7 100644 --- 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} -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 -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 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$. -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)$. -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 constant +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} @@ -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 ). \] -Since +Puisque $\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_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$. -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$. -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} -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$ -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$-stego-secure +pour peu que l'adapteur de stratégie soit uniformément distribué. \end{proof} diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex index 4cb4138..2c7c1e1 100644 --- a/annexePreuveMarquagefldblement.tex +++ b/annexePreuveMarquagefldblement.tex @@ -1,64 +1,66 @@ -On considère le mode +On considère le mode $f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant est défini par \begin{equation} {f_l}(x)_i = \left\{ \begin{array}{l} -\overline{x_i} \textrm{ if $i$ is odd} \\ -x_i \oplus x_{i-1} \textrm{ if $i$ is even} +\overline{x_i} \textrm{ si $i$ est impair} \\ +x_i \oplus x_{i-1} \textrm{ si $i$ est pair} \end{array} \right. -\end{equation}\label{eq:fqq} +\tag{\eqref{eq:fqq}} +\end{equation} -Prouvons que la matrice de Markov associée est doublement stochastique. -the Markov chain is stochastic by construction. +Prouvons que la matrice de Markov associée est doublement stochastique par induction +sur la longueur $l$. +Pour $l=1$ et $l=2$ la preuve est évidente. +Considérons que le résulat est établi jusqu'à $l=2k$ avec $k \in \Nats$. -Let us prove that its Markov chain is doubly stochastic by induction on the -length $l$. -For $l=1$ and $l=2$ the proof is obvious. Let us consider that the -result is established until $l=2k$ for some $k \in \Nats$. - -Let us then firstly prove the doubly stochasticity for $l=2k+1$. -Following notations introduced in~\cite{bcgr11:ip}, -Let $\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ denote -the subgraphs of $\textsc{giu}(f_{2k+1})$ induced by the subset $\Bool^{2k} \times\{0\}$ -and $\Bool^{2k} \times\{1\}$ of $\Bool^{2k+1}$ respectively. -$\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ are isomorphic to $\textsc{giu}(f_{2k})$. -Furthermore, these two graphs are linked together only with arcs of the form -$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ and +On montre d'abord que la double stochasticité est établie pour $l=2k+1$. +En suivant les notations introduites à la section~\ref{anx:sccg}, soit +$\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ les sous-graphes +de $\textsc{giu}(f_{2k+1})$ induits par les ensembles $\Bool^{2k} \times\{0\}$ +et $\Bool^{2k} \times\{1\}$ de $\Bool^{2k+1}$ respectivement. +Les graphes $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ sont isomorphes à $\textsc{giu}(f_{2k})$. +De plus, ils ne sont liés dans $\textsc{giu}(f_{2k+1})$ que par +des arcs de la forme +$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ et $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$. -In $\textsc{giu}(f_{2k+1})$ the number of arcs whose extremity is $(x_1,\dots,x_{2k},0)$ -is the same than the number of arcs whose extremity is $(x_1,\dots,x_{2k})$ -augmented with 1, and similarly for $(x_1,\dots,x_{2k},1)$. -By induction hypothesis, the Markov chain associated to $\textsc{giu}(f_{2k})$ is doubly stochastic. All the vertices $(x_1,\dots,x_{2k})$ have thus the same number of -ingoing arcs and the proof is established for $l$ is $2k+1$. +Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$. +Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$, +et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$. +L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$ +De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$. +Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$ +est doublement stochastique. +Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants et la preuve est établie pour $l= 2k+1$. -Let us then prove the doubly stochasticity for $l=2k+2$. -The map $f_l$ is defined by -$f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$. -With previously defined notations, let us focus on -$\textsc{giu}(f_{2k+2})^0$ and $\textsc{giu}(f_{2k+2})^1$ which are isomorphic to $\textsc{giu}(f_{2k+1})$. -Among configurations of $\Bool^{2k+2}$, only four suffixes of length 2 can be -obviously observed, namely, $00$, $10$, $11$ and $01$. -Since +Montrons à présent la double stochasticité pour $l=2k+2$. +La fonction $f_l$ est définie par $f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$. On se concentre sur +$\textsc{giu}(f_{2k+2})^0$ et $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à $\textsc{giu}(f_{2k+1})$. +Parmi les configurations de $\Bool^{2k+2}$, seuls quatre suffixes de longueur 2 peuvent appraître: +$00$, $10$, $11$ et $01$. +Puisque $f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$, -$f_{2k+2}(\dots,1,1)_{2k+2}=0$ and $f_{2k+2}(\dots,0,1)_{2k+2}=1$, the number of -arcs whose extremity is +$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est \begin{itemize} \item $(x_1,\dots,x_{2k},0,0)$ - is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,0)$). +est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ dans $\textsc{giu}(f_{2k+1})$ + auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,0)$); \item $(x_1,\dots,x_{2k},1,0)$ - is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations -$(x_1,\dots,x_{2k},1,1)$ to configurations -$(x_1,\dots,x_{2k},1,0)$) +est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ + auquel on ajoute 1 (l'arc entre les configurations $(x_1,\dots,x_{2k},1,1)$ et les configurations +$(x_1,\dots,x_{2k},1,0)$); \item $(x_1,\dots,x_{2k},0,1)$ - is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,1)$). +est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ + auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,1)$); \item $(x_1,\dots,x_{2k},1,1)$ - is the same than the one whose extremity is $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations -$(x_1,\dots,x_{2k},1,0)$ to configurations +est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ +auquel on ajoute 1 (l'arc entre les configurations +$(x_1,\dots,x_{2k},1,0)$ et les configurations $(x_1,\dots,x_{2k},1,1)$). \end{itemize} -Thus all the vertices $(x_1,\dots,x_{2k})$ have the same number of -ingoing arcs and the proof is established for $l=2k+2$. +Chacun des sommets $(x_1,\dots,x_{2k+2})$ a donc le même nombre d'arcs entrants, +la preuve est donc établie pour $l=2k+2$. diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex index 510dcef..5b77e95 100644 --- a/annexePreuveStopping.tex +++ b/annexePreuveStopping.tex @@ -1,378 +1,293 @@ -\section{Quantifier l'écart par rapport à la distribution uniforme} -%15 Rairo +L'objectif principal de cette section est de démontrer le théorème~\ref{theo:tmps:mix} rappelé en fin de section. - - - -Let thus be given such kind of map. -This article focuses on studying its iterations according to -the equation~(\ref{eq:asyn}) with a given strategy. -First of all, this can be interpreted as walking into its iteration graph -where the choice of the edge to follow is decided by the strategy. -Notice that the iteration graph is always a subgraph of -${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the -edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. -Next, if we add probabilities on the transition graph, iterations can be -interpreted as Markov chains. - -\begin{xpl} -Let us consider for instance -the graph $\Gamma(f)$ defined -in \textsc{Figure~\ref{fig:iteration:f*}.} and -the probability function $p$ defined on the set of edges as follows: -$$ -p(e) \left\{ -\begin{array}{ll} -= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\ -= \frac{1}{6} \textrm{ otherwise.} -\end{array} -\right. -$$ -The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is -\[ -P=\dfrac{1}{6} \left( -\begin{array}{llllllll} -4&1&1&0&0&0&0&0 \\ -1&4&0&0&0&1&0&0 \\ -0&0&4&1&0&0&1&0 \\ -0&1&1&4&0&0&0&0 \\ -1&0&0&0&4&0&1&0 \\ -0&0&0&0&1&4&0&1 \\ -0&0&0&0&1&0&4&1 \\ -0&0&0&1&0&1&0&4 -\end{array} -\right) -\] -\end{xpl} - - -% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$, -% % which is defined for two distributions $\pi$ and $\mu$ on the same set -% % $\Bool^n$ by: -% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ -% % It is known that -% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ - -% % Let then $M(x,\cdot)$ be the -% % distribution induced by the $x$-th row of $M$. If the Markov chain -% % induced by -% % $M$ has a stationary distribution $\pi$, then we define -% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$ -% Intuitively $d(t)$ is the largest deviation between -% the distribution $\pi$ and $M^t(x,\cdot)$, which -% is the result of iterating $t$ times the function. -% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} -% with respect to $\varepsilon$ is given by -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% It defines the smallest iteration number -% that is sufficient to obtain a deviation lesser than $\varepsilon$. -% Notice that the upper and lower bounds of mixing times cannot -% directly be computed with eigenvalues formulae as expressed -% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work -% only consider reversible Markov matrices whereas we do no restrict our -% matrices to such a form. - - - - - - - -This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ -issued from an hypercube where an Hamiltonian path has been removed. -A specific random walk in this modified hypercube is first -introduced. We further detail -a theoretical study on the length of the path -which is sufficient to follow to get a uniform distribution. -Notice that for a general references on Markov chains -see~\cite{LevinPeresWilmer2006} -, and particularly Chapter~5 on stopping times. - - - - -First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total -variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is -defined by -$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ It is known that -$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreover, if -$\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has -$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ - -Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the -distribution induced by the $X$-th row of $P$. If the Markov chain induced by -$P$ has a stationary distribution $\pi$, then we define -$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$ - -and - -$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -One can prove that +Un résultat classique est $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - -% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il -% un intérêt dans la preuve ensuite.} - - - -%and -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% One can prove that \JFc{Ou cela a-t-il été fait?} -% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - - -Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^{\mathsf{N}}$ valued random -variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping - time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq -(\Bool^{\mathsf{N}})^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -In other words, the event $\{\tau = t \}$ only depends on the values of -$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. +Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de +$\Bool^{\mathsf{N}}$. +Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un +\emph{temps d'arrêt} pour la suite +$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq +(\Bool^{\mathsf{N}})^{t+1}$ tel que +$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. +En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs +de +$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. -Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a -random mapping representation of the Markov chain. A {\it randomized - stopping time} for the Markov chain is a stopping time for -$(Z_t)_{t\in\mathbb{N}}$. If the Markov chain is irreducible and has $\pi$ -as stationary distribution, then a {\it stationary time} $\tau$ is a -randomized stopping time (possibly depending on the starting position $X$), -such that the distribution of $X_\tau$ is $\pi$: +Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et +$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. +Un \emph{temps d'arrêt aléatoire} pour la chaîne de +Markov est un temps d'arrêt pour +$(Z_t)_{t\in\mathbb{N}}$. +Si la chaîne de Markov est irréductible et a $\pi$ +comme distribution stationnaire, alors un +\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire +(qui peut dépendre de la configuration initiale $X$), +tel que la distribution de $X_\tau$ est $\pi$: $$\P_X(X_\tau=Y)=\pi(Y).$$ +Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$ +est indépendant de $\tau$. -A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is -independent of $\tau$. - +On rappelle le théorème suivant~\cite[Proposition 6.10]{LevinPeresWilmer2006}. -\begin{theorem} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} +\begin{theorem}\label{thm-sst} +Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} \P_X(\tau > t)$. \end{theorem} -%Let $\Bool^n$ be the set of words of length $n$. -Let $E=\{(X,Y)\mid -X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ or } X\oplus Y \in 0^*10^*\}$. -In other words, $E$ is the set of all the edges in the classical +Soit $E=\{(X,Y)\mid +X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ ou } X\oplus Y \in 0^*10^*\}$. +En d'autres mots, $E$ est l'ensemble des tous les arcs du ${\mathsf{N}}$-cube. -Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$. -Intuitively speaking $h$ aims at memorizing for each node -$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle, -\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ -cannot be switched. +Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$ +qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel +arc est supprimée à partir du cycle hamiltonien, +\textit{i.e.} quel bit dans $[{\mathsf{N}} ]$ +ne peut pas être inversé. -We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y = -0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube, -\textit{i.e.}, the ${\mathsf{N}}$-cube where the Hamiltonian cycle $h$ -has been removed. +On définit ensuite l'ensemble $E_h = E\setminus\{(X,Y)\mid X\oplus Y = +0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. C'est l'ensemble de tous les arcs +appartenant à l'hypercube modifié, +\textit{i.e.}, le ${\mathsf{N}}$-cube où le cycle hamiltonien $h$ +a été enlevé. -We define the Markov matrix $P_h$ for each line $X$ and -each column $Y$ as follows: +On définit la matrice de Markov $P_h$ pour chaque ligne $X$ et +chaque colonne $Y$ comme suit: \begin{equation} \left\{ \begin{array}{ll} P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\ -P_h(X,Y)=0 & \textrm{if $(X,Y)\notin E_h$}\\ -P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$} +P_h(X,Y)=0 & \textrm{si $(X,Y)\notin E_h$}\\ +P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{si $X\neq Y$ et $(X,Y) \in E_h$} \end{array} \right. \label{eq:Markov:rairo} \end{equation} -We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function -such that for any $X \in \Bool^{\mathsf{N}} $, -$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. -The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$, + + + + +Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction +telle que pour $X \in \Bool^{\mathsf{N}} $, +$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. +La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$, $\ov{h}(\ov{h}(X))\neq X$. + +%Let $\Bool^n$ be the set of words of length $n$. + \begin{lemma}\label{lm:h} -If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$. +Si $\ov{h}$ est bijective et anti-involutive, alors +$h(\ov{h}^{-1}(X))\neq h(X)$. \end{lemma} \begin{proof} -Let $\ov{h}$ be bijective. -Let $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$. -Then $(\ov{h}^{-1}(X),X)$ belongs to $E$ and +Soit $\ov{h}$ bijective. +Soit $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ t.q. $h(\ov{h}^{-1}(X))=k$. +Alors $(\ov{h}^{-1}(X),X)$ appartient à $E$ et $\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$. -Let us suppose $h(X) = h(\ov{h}^{-1}(X))$. In such a case, $h(X) =k$. -By definition of $\ov{h}$, $(X, \ov{h}(X)) \in E $ and +Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$. +Par définition $\ov{h}$, $(X, \ov{h}(X)) \in E $ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$. -Thus $\ov{h}(X)= \ov{h}^{-1}(X)$, which leads to $\ov{h}(\ov{h}(X))= X$. -This contradicts the square-freeness of $\ov{h}$. +Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraine $\ov{h}(\ov{h}(X))= X$ et +qui contredit le fiat que $\ov{h}$ est anti-involutive. \end{proof} -Let $Z$ be a random variable that is uniformly distributed over -$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$. -For $X\in \Bool^{\mathsf{N}}$, we -define, with $Z=(i,b)$, -$$ +Soit $Z$ une variable aléatoire suivant une distribution uniforme sur +$[ {\mathsf{N}}] \times \Bool$. +Pour $X\in \Bool^{\mathsf{N}}$, on définit avec $Z=(i,b)$, +\[ \left\{ \begin{array}{ll} -f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\ +f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\ f(X,Z)=X& \text{otherwise.} \end{array}\right. -$$ +\] -The Markov chain is thus defined as -$$ -X_t= f(X_{t-1},Z_t) -$$ +La chaîne de Markov est ainsi définie par +\[ +X_t= f(X_{t-1},Z_t). +\] -%%%%%%%%%%%%%%%%%%%%%%%%%%%ù -%\section{Stopping time} -An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} -at time $t$ if there -exists $0\leq j t)\leq \frac{E[\tau]}{t}. +\] + +En posant $t_n=32N^2+16N\ln (N+1)$, on obtient: +\[ +\P_X(\tau > t_n)\leq \frac{1}{4}. +\] + + +D'après la définition de $t_{\rm mix}$ et d'après le théorème~\ref{thm-sst}, +on en déduit +\[ +t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2) +\]. +\end{proof} diff --git a/annexePreuvesComplexiteStego.tex b/annexePreuvesComplexiteStego.tex index b8f9704..11af488 100644 --- a/annexePreuvesComplexiteStego.tex +++ b/annexePreuvesComplexiteStego.tex @@ -1,7 +1,6 @@ -\begin{theorem}\label{th:cplxt:hugo} -Le schéma HUGO a une complexité de l'ordre de -$\theta(2 \times n^2(343^2 + \ln(n)))$ -\end{theorem} +Démontrons le théorème suivant: + +\theocplstegano* First of all, HUGO starts with computing the second order SPAM Features. diff --git a/main.tex b/main.tex index 1c00650..86c917e 100644 --- a/main.tex +++ b/main.tex @@ -275,13 +275,12 @@ de telles fonctions. \part{Application au marquage de média} -\chapter{Des embarquement préservant le chaos}\label{chap:watermarking} +\chapter{Des embarquements préservant le chaos}\label{chap:watermarking} \input{oxford} \chapter{Une démarche de marquage de PDF} \input{ahmad} - \chapter{Une démarches plus classique de dissimulation: STABYLO} \input{stabylo} @@ -380,7 +379,7 @@ du chapitre 8} \section{Codes de Gray équilibrés par induction} \input{annexePreuveGrayEquilibre} -\section{Majoration du temps d'arrêt} +\section{Majoration du temps de mixage} \input{annexePreuveStopping} \chapter{Preuves sur le marquage de média}\label{anx:marquage} @@ -392,11 +391,10 @@ du chapitre 8} \section{Le marquage est correct et complet}\label{anx:preuve:marquage:correctioncompletue} \input{annexePreuveMarquageCorrectioncompletude} -\backmatter -\section{Complexités d'algorithmes de stéganographie} -\label{anx:preuve:cplxt} -\input{annexePreuvesComplexiteStego} +% \section{Complexités d'algorithmes de stéganographie} +% \label{anx:preuve:cplxt} +% \input{annexePreuvesComplexiteStego} @@ -404,7 +402,7 @@ du chapitre 8} \bibliography{abbrev,biblioand} \listoffigures \listoftables -\listofdefinitions + \end{document} diff --git a/oxford.tex b/oxford.tex index 0be2951..ebdc417 100644 --- a/oxford.tex +++ b/oxford.tex @@ -3,8 +3,8 @@ marque. Dans ce chapitre, le processus d'embarquement d'un message dans un média est formalisé en section~\ref{sec:watermarking:formulation}. La sécurité des approches de watermarking est étudiée selon deux approches: -l'approche probabiliste~\ref{sec:watermarking:security:probas} -et l'approche chaotique~\ref{sec:watermarking:security:chaos}. +l'approche probabiliste (section~\ref{sec:watermarking:security:probas}) +et l'approche chaotique (section~\ref{sec:watermarking:security:chaos}). Une proposition d'embarquement dans le domaine fréquentiel est abordée en section~\ref{sec:watermarking:frequentiel}. @@ -29,7 +29,7 @@ noté $y$ et le support dans lequel se fait l'insertion est noté $x$. Le processus de marquage est fondé sur les itérations unaires d'une fonction selon une stratégie donnée. Cette fonction et cette stratégie sont paramétrées par un entier naturel permettant à la méthode d'être -appliquable à un média de n'importe quelle taille. +applicable à un média de n'importe quelle taille. On parle alors respectivement de \emph{mode} et d'\emph{adapteur de stratégies} \subsection{Embarquement} @@ -51,13 +51,13 @@ dans lui même. de $\Nats$ dans l'ensemble des séquences d'entiers qui associe à chaque entier naturel $\mathsf{N}$ la suite - $S \in \llbracket 1, n\rrbracket^{\mathds{N}}$. + $S \in [\mathsf{N}@]^{\mathds{N}}$. \end{Def} On définit par exemple l'adapteur CIIS (\emph{Chaotic Iterations with Independent Strategy}) paramétré par $(K,y,\alpha,l) \in [0,1]\times [0,1] \times ]0, 0.5[ \times \mathds{N}$ -qui associe à chque entier $n \in \Nats$ la suite +qui associe à chaque entier $\mathsf{N} \in \Nats$ la suite $(S^t)^{t \in \mathds{N}}$ définie par: \begin{itemize} \item $K^0 = \textit{bin}(y) \oplus \textit{bin}(K)$: $K^0$ est le nombre binaire (sur 32 bits) @@ -65,10 +65,10 @@ $(S^t)^{t \in \mathds{N}}$ définie par: entre les décompositions binaires sur 32 bits des réels $y$ et $K$ (il est aussi compris entre 0 et 1), \item $\forall t \leqslant l, K^{t+1} = F(K^t,\alpha)$, - \item $\forall t \leqslant l, S^t = \left \lfloor n \times K^t \right \rfloor + 1$, + \item $\forall t \leqslant l, S^t = \left \lfloor \mathsf{N} \times K^t \right \rfloor + 1$, \item $\forall t > l, S^t = 0$, \end{itemize} -où est la fonction chaotique linéaire par morceau~\cite{Shujun1}. +où $F$ est la fonction chaotique linéaire par morceau~\cite{Shujun1}. Les paramètres $K$ et $\alpha$ de cet adapteur de stratégie peuvent être vus comme des clefs. On remarque que cette stratégie est unaire. @@ -89,15 +89,15 @@ $(u^k(x))$ de taille $\mid x \mid$ à valeur dans les réels. Cette fonction peut dépendre du message $y$ à embarquer, ou non. \end{Def} -Pour alléger le discours, par la suite, on nottera $(u^k(x))$ pour $(u^k)$ -lorsque cela n'est pas ambigüe. +Pour alléger le discours, par la suite, on notera $(u^k(x))$ pour $(u^k)$ +lorsque cela n'est pas ambiguë. Il reste à partionner les bits de $x$ selon qu'ils sont peu, moyennement ou très significatifs. \begin{Def}[Signification des bits]\label{def:msc,lsc} Soit $u$ une fonction de signification, $m$ et $M$ deux réels t.q. $m < M$. Alors: -$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivements des +$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivement des \emph{bits les plus significatifs (MSBs)} de $x$, \emph{bits les moins significatifs (LSBs)} de $x$ \emph{bits passifs} of $x$ définis par: @@ -111,7 +111,7 @@ u^k \in ]m;M[ \textrm{ et } k \le \mid x \mid \right) \end{eqnarray*} \end{Def} -On peut alors définir une fonction de décompostion +On peut alors définir une fonction de décomposition puis de recomposition pour un hôte $x$: @@ -145,7 +145,7 @@ $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in \mathfrak{B} $ tel que \begin{itemize} -\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[n]$; +\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[\mathsf{N}]$; \item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$ et $|u_p| = |\varphi_p|$. \end{itemize} Soit la base canonique sur l'espace vectoriel $\mathds{R}^{\mid x \mid}$ composée des vecteurs @@ -184,7 +184,7 @@ On peut étendre l'algorithme dhCI~\cite{gfb10:ip} d'embarquement de message com \begin{Def}[Embarquement dhCI étendu] \label{def:dhCI:ext} -Soit $\textit{dec}(u,m,M)$ une function de décomposition, +Soit $\textit{dec}(u,m,M)$ une fonction de décomposition, $f$ un mode, $\mathcal{S}$ un adapteur de stratégie, $x$ un hôte, @@ -200,7 +200,7 @@ $\hat{y}$ dans $x$, t. q.: \begin{itemize} \item le mode $f$ est instancié avec le paramètre $l=|u_m|$, engendrant la fonction $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$; -\item l'adapteur de stratégie $\mathcal{S}$ est intancié avec le paramètre +\item l'adapteur de stratégie $\mathcal{S}$ est instancié avec le paramètre $y$, engendrant une stratégie $S_y \in [l]$; \item on itère la fonction $G_{f_l}$ en prenant la configuration initiale $(S_y,\phi_{m})$ selon le schéma défini @@ -223,7 +223,7 @@ La figure~\ref{fig:organigramme} synthétise la démarche. -\subsection{Détection d'un media marqué}\label{sub:wmdecoding} +\subsection{Détection d'un média marqué}\label{sub:wmdecoding} On caractérise d'abord ce qu'est un média marqué selon la méthode énoncée à la section précédente. On considère que l'on connaît @@ -231,7 +231,7 @@ la marque à embarquer $y$, le support $x$ et que l'on a face à soit un média $z$. -\begin{definition}[Média marqué] +\begin{Def}[Média marqué] Soit $\textit{dec}(u,m,M)$ une fonction de décomposition $f$ un mode, $\mathcal{S}$ un adapteur de stratégie @@ -240,10 +240,10 @@ $y$ un média digital et soit $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ l'image par $\textit{dec}(u,m,M)$ du média $x$. Alors, $z$ est \emph{marqué} avec $y$ si l'image -par $\textit{dec}(u,m,M)$ of $z$ is +par $\textit{dec}(u,m,M)$ of $z$ est $(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$, où $\hat{y}$ est le second membre de $G_{f_l}^q(S_y,\phi_{m})$. -\end{definition} +\end{Def} % Plusieurs stratégies peuvent être utilisées pour déterminer si une image $z$ % est marquée, en particulier si l'image a été attaquée entre temps. @@ -253,40 +253,43 @@ $\hat{y}$ est le second membre de $G_{f_l}^q(S_y,\phi_{m})$. Récemment~\cite{Cayre2005,Perez06} ont proposé des classes de sécurité pour le -marquage d'information. Parmis celles-ci, la stego-sécurité a été au centre +marquage d'information. Parmi celles-ci, la stego-sécurité a été au centre des travaux puisqu'elle représente la classe la plus élevée dans le contexte où l'attaquant n'a accès qu'à l'hôte marqué $z$. Cette définition probabiliste est rappelée ci-après. -Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle porbabiliste +Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle probabiliste de $N_0$ hôtes, et $p(Y|K)$ le modèle probabiliste de $N_0$ contenus marqués avec la même clé $K$ et le même algorithme d'embarquement. -\begin{definition}[Stégo-Sécurité~\cite{Cayre2008}] +\begin{Def}[Stégo-Sécurité~\cite{Cayre2008}] \label{Def:Stego-security} -La fonction d'embarquement is \emph{stégo-sécure} +La fonction d'embarquement est \emph{stégo-sécure} si la propriété $\forall K \in \mathds{K}, p(Y|K)=p(X)$ est établie. -\end{definition} +\end{Def} Il a déjà été démontré~\cite{guyeuxphd,gfb10:ip} que l'algorithme de marquage dont le mode est la fonction négation est stégo-sécure. Un des intérêts de l'algorithme présenté ici est qu'il est paramétré par un mode. Lorsque celui-ci a les même propriétés que celles vues pour la création de PRNG (\textit{i.e.} graphe des itérations fortement connexes et matrice de Markov doublement -stochastique), on a un marquage qui peut être rendu stego-secure à $\epsilon$ pret, -ce que précise le théorème suivant: +stochastique), on a un marquage qui peut être rendu stégo-sécure à $\varepsilon$ prêt, +ce que précise le théorème suivant. La preuve de ce théorème est donnée +en annexes~\ref{anx:marquage}. + -\begin{theorem}\label{th:stego} -Soit $\epsilon$ un nombre positif, +\begin{restatable}[$\varepsilon$-stego sécurité]{theorem}{theoremstegoscureepsilon} +\label{th:stego} +Soit $\varepsilon$ 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$ +un adapteur de stratégie uniformément 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} +$|p(Y|K)- p(X)| < \varepsilon$. +\end{restatable} @@ -295,13 +298,13 @@ On rappelle uniquement la définition de chaos-sécurité introduite dans~\cite{guyeuxphd}. -\begin{definition}[Chaos-sécurité] +\begin{Def}[Chaos-sécurité] \label{DefinitionChaosSecure} Un schéma de marquage $S$ est chaos-sécure sur un espace topologique $(\mathcal{X},\tau)$ si sa version itérative -a un comprtement chaotique sur celui-ci. -\end{definition} +a un comportement chaotique sur celui-ci. +\end{Def} Tout repose ainsi sur la capacité que l'on a à produire des fonctions dont le graphe des itérations unaires sera fortement connexe. @@ -321,11 +324,11 @@ x_i \oplus x_{i-1} \textrm{ si $i$ est pair} \right. \end{equation}\label{eq:fqq} -on peut déduire imédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos}) +on peut déduire immédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos}) que le graphe $\textsc{giu}(f_l)$ est fortement connexe. La preuve de double-stochasiticité de la matrice associée à $f_l$ est donnée en annexes~\ref{anx:marquage:dblesto}. -On dispose ainsi d'un nouvel algorithme de marquage $\epsilon$-stego-secure et +On dispose ainsi d'un nouvel algorithme de marquage $\varepsilon$-stégo-sécure et chaos-sécure. \section{Applications aux domaines fréquentiels}\label{sec:watermarking:frequentiel} @@ -334,17 +337,17 @@ dans les coefficients DCT et les DWT. \subsection{Fonction de signification pour l'embarquement dans les DCT} -On considère un hôte $x$ de taille $H \times L$ dans le domaine fréqentiel DCT. +On considère un hôte $x$ de taille $H \times L$ dans le domaine fréquentiel DCT. Dans chaque bloc de taille $8\times 8$, à chaque bit la fonction de signification $u$ associe \begin{itemize} -\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(1,1),(2,1),(1,2)\}$, -\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur +\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(1,1),(2,1),(1,2)\}$, +\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui n'est pas un des trois bits de poids faible de cette représentation, -\item -1 si c'est un bit appraissant dans la représentation binaire +\item -1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui est un des des trois bits de poids faible de cette valeur, @@ -352,12 +355,12 @@ de la valeur d'un coefficient dont les \end{itemize} Le choix de l'importance de chaque coefficient est défini grâce aux seuils $(m,M)=(-0.5,0.5)$ -permetant d'engendrer les MSBs, LSBs, et bits passifs. +permettant d'engendrer les MSBs, LSBs, et bits passifs. \subsection{Fonction de signification pour l'embarquement dans les DWT} -On considère un hôte dnas le domaine des DWT. La fonction de signification +On considère un hôte dans le domaine des DWT. La fonction de signification se concentre sur les seconds niveaux de détail (\textit{i.e.}, LH2, HL2 et HH2). Pour chaque bit, on dit qu'il est peu significatif si c'est un des trois bits de poids faible d'un coefficient de LH2, HL2 ou de HH2. @@ -365,23 +368,23 @@ Formellement à chaque bit la fonction de signification $u$ associe \begin{itemize} -\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LL2, -\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui n'est pas un des trois +\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LL2, +\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui n'est pas un des trois bits de poids faible de cette représentation, -\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui est un des trois +\item 0 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui est un des trois bits de poids faible de cette représentation, -\item 0 sinon. +\item -1 sinon. \end{itemize} Le choix de l'importance de chaque coefficient est encore défini grâce aux seuils $(m,M)=(-0.5,0.5)$ -permetant d'engendrer les MSBs, LSBs, et bits passifs. +permettant d'engendrer les MSBs, LSBs, et bits passifs. \subsection{Etude de robustesse} Cette partie synthétise une étude de robustesse de la démarche présentée ci-avant. Dans ce qui suit, {dwt}(neg), {dwt}(fl), {dct}(neg), {dct}(fl) -correpondent respectivement aux embarquements en fréquenciel +correspondant respectivement aux embarquements en fréquentiels dans les domaines DWT et DCT avec le mode de négation et celui issu de la fonction $f_l$ détaillé à l'équation~\ref{eq:fqq}. @@ -390,13 +393,13 @@ A chaque série d'expériences, un ensemble de 50 images est choisi aléatoireme de la base du concours BOSS~\cite{Boss10}. Chaque hôte est une image en $512\times 512$ en niveau de gris et la marque $y$ est une suite de 4096 bits. -La resistance à la robustesse est évaluée en appliquant successivement +La résistances à la robustesse est évaluée en appliquant successivement sur l'image marquée des attaques de découpage, de compression, de transformations géométriques. Si les différences entre $\hat{y}$ and $\varphi_m(z)$. -sont en desous d'un seuil(que l'on définit), +sont en dessous d'un seuil (que l'on définit), l'image est dite marquée (et non marquée dans le cas contraire). -Cette différence exprimée en pourcentage est rappellée pour chacune des ataques +Cette différence exprimée en pourcentage est rappelée pour chacune des attaques à la figure~\ref{fig:atq:dhc}. @@ -411,7 +414,7 @@ Cette différence exprimée en pourcentage est rappellée pour chacune des ataqu \subfigure[Compression JPEG 2000]{ \includegraphics[width=0.45\textwidth]{atq-jp2}\label{Fig:atq:jp2:curves} } - \subfigure[Modification du contrast]{ + \subfigure[Modification du contraste]{ % \includegraphics[width=0.45\textwidth]{atq-contrast.pdf}\label{Fig:atq:cont:curve}} \includegraphics[width=0.45\textwidth]{atq-contrast}\label{Fig:atq:cont:curve} } @@ -427,13 +430,13 @@ Cette différence exprimée en pourcentage est rappellée pour chacune des ataqu \end{figure} -\subsection{Evaluation de l'embarquement}\label{sub:roc} +\subsection{Évaluation de l'embarquement}\label{sub:roc} Pour évaluer le seuil qui permet de dire avec la plus grande précision si une image est marquée ou non, nous avons appliqué la démarche suivante. A partir d'un ensemble de 100 images du challenge BOSS, les trois ensembles suivants sont construits: celui des images marquées $W$, -celui contenant des imges marquées puis attaquée $\textit{WA}$, -et celui des images uniquement attaquées $A$. Les attaques sont choisiés parmi +celui contenant des images marquées puis attaquée $\textit{WA}$, +et celui des images uniquement attaquées $A$. Les attaques sont choisies parmi celles données ci dessus. Pour chaque entier $t$ entre 5 et 55 @@ -469,7 +472,7 @@ dans le domaine DWT. Pour les deux modes dans le domaine DCT, la détection est optimale pour le seuil de 44\% (correspondant aux points (0.05, 0.18) et (0.05, 0.28)). -On peut alors donner des intervales de confiance pour les attaques évaluées. +On peut alors donner des intervalles de confiance pour les attaques évaluées. L'approche est résistante à: \begin{itemize} \item tous les découpages où le pourcentage est inférieur à 85\%; @@ -487,9 +490,9 @@ L'algorithme présenté dans les sections précédentes ne permet de savoir, \textit{in fine}, que si l'image est marquée ou pas. Cet algorithme ne permet pas de retrouver le contenu de la marque à partir de l'image marquée. -C'est l'bjectif de l'algorithme présenté dans cette section et introduit +C'est l'objectif de l'algorithme présenté dans cette section et introduit dans~\cite{fgb11:ip}. -On des raisons de lisibilité, il n'est pas +Pour des raisons de lisibilité, il n'est pas présenté pas dans le formalisme de la première section et est grandement synthétisé. Il a cependant été prouvé comme étant chaos-sécure~\cite{fgb11:ip}. @@ -501,7 +504,7 @@ Commençons par quelques conventions de notations: \item $\mathbb{S}_\mathsf{k}$ est l'ensemble des stratégies unaire sur $[k]$; \item $m^0 \in \mathbb{B}^{\mathsf{P}}$ est un vecteur de $\mathsf{P}$ bits représentant la marque; -\item comme précédement, +\item comme précédemment, $x^0 \in \mathbb{B}^\mathsf{N}$ est le vecteurs des $\mathsf{N}$ bits sélectionnés où la marque est embarquée. \item $S_p \in \mathbb{S}_\mathsf{N}$ @@ -545,7 +548,7 @@ m_j^{n-1} & \text{ if }S_m^n\neq j \\ \end{array} \right. \end{equation*} -%\end{definition} +%\end{Def} \noindent où $\overline{m_j^{n-1}}$ est la négation booléenne de $m_j^{n-1}$. On impose de plus la contrainte suivante. Soit $\Im(S_p) = \{S^1_p, S^2_p, \ldots, S^l_p\}$ @@ -565,7 +568,7 @@ l'hôte et on obtient un contenu marqué. Sans attaque, le schéma doit garantir qu'un utilisateur qui dispose des bonnes clefs de création des stratégies est capable d'extraire une marque et que celle-ci est la marque insérée. -Ceci correspond respectivement aux propriétés de complétudes et de correction +Ceci correspond respectivement aux propriétés de complétude et de correction de l'approche. L'étude de ces propriétés est l'objectif de la section qui suit. @@ -578,31 +581,31 @@ L'étude de ces propriétés est l'objectif de la section qui suit. On ne donne ici que le théorème. La preuve est placée en annexes~\ref{anx:preuve:marquage:correctioncompletue}. -\begin{theorem} -La condition de l'algorithme de marquage est nécressaire et suffisante +\begin{restatable}[Correction et complétude du marquage]{theorem}{marquagecorrectioncompl} +La condition de l'algorithme de marquage est nécessaire et suffisante pour permettre l'extraction du message du média marqué. -\end{theorem} +\end{restatable} -Sous ces hypothèes, on peut donc extraire un message. +Sous ces hypothèse, on peut donc extraire un message. De plus, le cardinal $k$ de $\Im(S_p)$ est supérieur ou égal à $\mathsf{P}$. Ainsi le bit $j$ du message original $m^0$ peut être -embarqué plusieur fois dans $x^l$. -Or, en compte le nombrede fois où ce bit a été inversé dans +embarqué plusieurs fois dans $x^l$. +Or, en comptant le nombre de fois où ce bit a été inversé dans $S_m$, la valeur de $m_j$ peut se déduire en plusieurs places. Sans attaque, toutes ces valeurs sont identiques -et le messageest obtenus immédiatement. +et le message est obtenus immédiatement. Si attaque il y a, la valeur de $m_j$ peut s'obtenir en prenant la valeur -moyenne de toutes les valeurs obtenues. On a donc la correction et la complétude. +moyenne de toutes les valeurs obtenues. \subsection{Détecter si le média est marqué}\label{sub:ci2:distances} On considère un média $y$ marqué par un message $m$. Soit $y'$ une version altérée de $y$, c.-à-d. une version où certains bits on été modifiés et soit -$m'$ le message extrait de from $y'$. +$m'$ le message extrait de $y'$. Pour mesurer la distance entre $m'$ et $m$, on -considère repsectivement +considère respectivement $M$ et $M$ l'ensemble des indices de $m$ et de $m'$ où $m_i$ vaut 1 et ou $m'_1$ vaut 1. @@ -619,7 +622,7 @@ c.-à-d. celui qui permet la séparation la plus forte entre des vecteurs corrélés et des ceux qui ne le sont pas. La distance entre $m$ et $m'$ est construite selon cette mesure et produit un réel dans $[0;1]$. Si elle est inférieure à un certain -seuil (à définir), le média $y'$ est declaré +seuil (à définir), le média $y'$ est déclaré comme marqué et le message doit pouvoir être extrait. \subsection{Etude de robustesse}\label{sec:watermarking:robustesse} @@ -633,7 +636,7 @@ particulièrement peu robuste. \section{Conclusion} -Grace à la formalisation du processus de watermarking par itérations discrètes, nous avons pu dans ce chapitre montrer que le processus possédait les propriétés +Grâce à la formalisation du processus de watermarking par itérations discrètes, nous avons pu dans ce chapitre montrer que le processus possédait les propriétés attendues, à savoir stego-sécurité, chaos sécurité et une robustesse relative. Pour étendre le champ applicatif, nous avons proposé un second algorithme permettant de particulariser la marque à embarquer et donc à extraire. diff --git a/stabylo.tex b/stabylo.tex index 8801599..0e0775d 100644 --- a/stabylo.tex +++ b/stabylo.tex @@ -11,20 +11,20 @@ et UNIWARD~\cite{HFD14}. Pour détecter de la présence ou non d'un message dans une image, on peut demander l'oracle à un un \emph{stéganalyseur}~\cite{LHS08,DBLP:conf/ih/Ker05,FK12}. -Usuellement, un outil de cette fammille, après +Usuellement, un outil de cette famille, après une démarche d'apprentissage, classifie les images en fonction de caractéristiques numériques. A partir de caractéristiques de voisinage nommées -SPAM~\cite{DBLP:journals/tifs/PevnyBF10}, HUGO mesure la distortion +SPAM~\cite{DBLP:journals/tifs/PevnyBF10}, HUGO mesure la distorsion qui serait induite par la modification de chaque pixel. Similairement, -WOW et UNIWARD construisent une carte de distortion mais celle-ci est +WOW et UNIWARD construisent une carte de distorsion mais celle-ci est issue caractéristiques directionnelles calculées à partir d'ondelettes. -A partir de ces cartes de distortions, chacun de ces algorithmes selectionne -les pixels dont les modifications induisent la distortion la plus faible +A partir de ces cartes de distorsion, chacun de ces algorithmes sélectionne +les pixels dont les modifications induisent la distorsion la plus faible possible. Ceci revient à définir une fonction de signification $u$. La complexité du schéma de stéganographie est peu ou prou celle du calcul de cette carte, et elle est élevée dans le cas @@ -69,7 +69,7 @@ l'extraction à la Fig.~\ref{fig:sch:ext}. \end{figure*} -La sécurité de l'encryptage est garantie par le système asymmétrique +La sécurité de l'encryptage est garantie par le système asymétrique de Blum-Goldwasser~\cite{Blum:1985:EPP:19478.19501} basé sur le PRNG Blum Blum Shub~\cite{DBLP:conf/crypto/ShubBB82}. Ainsi, à partir d'une clef $k$ et un message \textit{mess}, @@ -81,8 +81,8 @@ le message $m$. L'idée d'embarquer dans des bords dans une image repose sur le fait que les pixels de ceux-ci représentent déjà une rupture de continuité entre pixels voisins. -Une faible modification de ceux-ci n'a donc pas un grand impact sur la qualité -de l'image, condition nécéessaire lorsqu'on prétend être indétectable. +Une faible modification de ceux-ci n'aurait donc pas un grand impact sur la qualité +de l'image, condition nécessaire lorsqu'on prétend être indétectable. STABYLO est basé sur les filtres de Canny~\cite{Canny:1986:CAE:11274.11275}, comme démarche de détection @@ -94,31 +94,31 @@ Cette détection de bords ne considère que les $b$ bits les plus significatifs (pratiquement $b$ vaut $6$ ou $7$) et un masque de sélection $T$ $T=3,5,7$). Plus élevée est la valeur de ce masque, plus grand est le nombre -de pixels de bors mais plus grossière est l'approche. +de pixels de bord mais plus grossière est l'approche. Dans le diagramme de flux, cette étape de sélection est représentée par ``x=Edge Detection(b, T, X)''. La section suivante montre comment le schéma s'adapte aux valeurs de $m$ et de $x$. -\subsection{Un embarquement adaptif}\label{sub:adaptive} +\subsection{Un embarquement adaptatif}\label{sub:adaptive} Nous argumentons que le schéma d'embarquement doit s'adapter au message $m$ et au nombre de bits disponibles pour cet embarquement. Deux stratégies sont possibles dans STABYLO. -Dans la première, dite \emph{adaptive}, le taux d'embarquement +Dans la première, dite \emph{adaptative}, le taux d'embarquement (rapport entre le nombre de bits embarqués par rapport au nombre de pixels modifiés) dépend du nombre de bits disponibles à l'issue de l'extraction des pixels de bords. Si ce nombre de bits est inférieur au double de la taille du message, celui-ci est découpé en plusieurs parties. La justification de ce rapport de 1 à 2 à donné ci dessous dans la partie STC. Dans la seconde dite \emph{fixe}, ce taux est fixe et l'algorithme augmente -iterativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits +iterrativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits de bords qu'il n'y en a dans le message. STABYLO applique alors -par défaut l'agorithme STC~\cite{DBLP:journals/tifs/FillerJF11} -pour ne modifier aussi peu que posible les bits parmi ceux dont il dispose. -Dans le cas où c'est la stratégie adaptive qui est choisie, le paramètre -$\rho$ de cet algorithme vaut 1 pour chaqun des bits. +par défaut l'algorithme STC~\cite{DBLP:journals/tifs/FillerJF11} +pour ne modifier aussi peu que possible les bits parmi ceux dont il dispose. +Dans le cas où c'est la stratégie adoptive qui est choisie, le paramètre +$\rho$ de cet algorithme vaut 1 pour chacun des bits. Dans le cas contraire, la valeur de ce paramètre varie en fonction du seuil $T$ de l'algorithme de détection de bord comme suit: $$ @@ -146,40 +146,28 @@ Dans cette section, on justifie qualificatif \og LOw cost\fg{} de STABYLO en comparant l'ordre de grandeur de son temps d'exécution avec ceux des principaux schémas existants à savoir HUGO~\cite{DBLP:conf/ih/PevnyFB10}, WOW~\cite{conf/wifs/HolubF12} et UNIWARD~\cite{HFD14}. -Chacune de ces quatre méthodes commence par calculer un carte de distortion +Chacune de ces quatre méthodes commence par calculer un carte de distorsion de l'ensemble des pixels et se termine en appliquant l'algorithme STC. Comme cette dernière étape est commune à toutes les approches, on évalue sa complexité à part. Dans tout ce qui suit, on considère une image carrée de taille $n \times n$. -Les preuves de ces théorèmes sont données en annexes~\ref{anx:preuve:cplxt}. +Les preuves de ces théorèmes sont données dans~\cite{ccg15:ij} -\begin{theorem}\label{th:cplxt:hugo} -Le schéma HUGO a une complexité de l'ordre de -$\theta(2 \times n^2(343^2 + \ln(n)))$ -\end{theorem} - -\begin{theorem}\label{th:cplxt:wow} -Le schéma WOW a une complexité de l'ordre de -$\theta(6n^4\ln(n) + n^2)$. -\end{theorem} - - -\begin{theorem}\label{th:cplxt:uniward} -Le schéma UNIWARD a une complexité dont l'ordre est supérieur à +\begin{restatable}[Complexité d'algorithmes de stéganographie]{theorem}{theocplstegano} +\label{th:cplxt:stegano} +\begin{itemize} +\item Le schéma HUGO a une complexité de l'ordre de $\theta(2 \times n^2(343^2 + \ln(n)))$ +\item Les schémas WOW et UNIWARD ont une complexité de l'ordre de $\theta(6n^4\ln(n) + n^2)$. -\end{theorem} - -\begin{theorem}\label{th:cplxt:stabylo} -Le schéma STABYLO a une complexité dont l'ordre est -$\theta((5^3+4T+1)n^2)$. -\end{theorem} - +\item Le schéma STABYLO a une complexité dont l'ordre est $\theta((5^3+4T+1)n^2)$. +\end{itemize} +\end{restatable} D'après~\cite{DBLP:journals/tifs/FillerJF11}, la complexité de STC est le l'ordre de $\theta(2^h.n)$ où $h$ -est la taille de la matrice dupliquée. Cett complexité linéaire +est la taille de la matrice dupliquée. Cette complexité linéaire est donc négligeable par rapport au reste. @@ -193,7 +181,7 @@ attribué à STABYLO. \begin{center} \includegraphics[scale=0.4]{images/complexity} \end{center} -\caption{Evaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO} +\caption{Évaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO} \label{fig:compared} \end{figure} @@ -209,10 +197,10 @@ Filler~\cite{FillerJF11}. Le schéma STABYLO a été systématiquement comparé à HUGO, EAISLSBMR~\cite{Luo:2010:EAI:1824719.1824720}, WOW et UNIWARD -pour les stratégies fixes (10\%) et adaptives. +pour les stratégies fixes (10\%) et adaptatives. Pour établir la valeur de cette dernière stratégie, le filtre de Canny a été paramétré avec une valeur de $T=3$. -Lorsque $b$ vaut 7, la taile moyenne du message pouvant être embarqué est de +Lorsque $b$ vaut 7, la taille moyenne du message pouvant être embarqué est de 16,445, \textit{i.e.}, un taux d'embarquement moyen de 6,35\%. Pour chaque image, le nombre de bits embarqué par STABYLO est mémorisé et il est demandé à chacun des autres schémas d'embarquer ce même nombre de bits. @@ -226,7 +214,7 @@ est demandé à chacun des autres schémas d'embarquer ce même nombre de bits. \hline Schéma & \multicolumn{3}{c|}{STABYLO} & \multicolumn{2}{c|}{HUGO}& \multicolumn{2}{c|}{EAISLSBMR} & \multicolumn{2}{c|}{WOW} & \multicolumn{2}{c|}{UNIWARD}\\ \hline -Strétégie & fixe & \multicolumn{2}{c|}{adapt. ($\approx$6.35\%)} & fixe & adapt. & fixe & adapt. & fixe & adapt. & fixe & adapt. \\ +Stratégie & fixe & \multicolumn{2}{c|}{adapt. ($\approx$6.35\%)} & fixe & adapt. & fixe & adapt. & fixe & adapt. & fixe & adapt. \\ \hline Ratio & 10\% & +STC(7) & +STC(6) & 10\%& $\approx$6.35\%& 10\%& $\approx$6.35\% & 10\%& $\approx$6.35\%& 10\%& $\approx$6.35\%\\ \hline @@ -236,11 +224,11 @@ Ensemble Classifier & 0.35 & 0.47 & 0.47 & 0.48 & 0.49 & 0.43 & 0.47 & 0 \end{tabular} \end{small} \end{center} -\caption{Steganalyse de STABYLO\label{table:steganalyse}.} +\caption{Stéganalyse de STABYLO\label{table:steganalyse}.} \end{table*} -Etant considéré comme le plus exact +Étant considéré comme le plus exact stéganalyseur dans le domaine spatial, Ensemble Classifier~\cite{DBLP:journals/tifs/KodovskyFH12} a été exécuté avec les caractéristiques diff --git a/stegoyousra.tex b/stegoyousra.tex index 7f2add3..fdc3bf4 100644 --- a/stegoyousra.tex +++ b/stegoyousra.tex @@ -495,7 +495,7 @@ P(i,0) \begin{table}[ht] -\caption{ Noyaux pour les dérivéees secondes en $x$ et $y$ lors de l'interpolation polynomiale\label{table:sod:diag:poly} +\caption{ Noyaux pour les dérivées secondes en $x$ et $y$ lors de l'interpolation polynomiale\label{table:sod:diag:poly} } \centering %\scriptsize @@ -571,7 +571,7 @@ de cette dernière: \] -\section{Experimentations}\label{sec:experiments} +\section{Expérimentations}\label{sec:experiments} Tout d'abord, l'ensemble du code est accessible en ligne\footnote{\url{https://github.com/stego-content/SOS}}. La Figure~\ref{fig:oneimage} représente les résultats d'embarquement de données dans @@ -612,7 +612,7 @@ concentrent les changements. Les deux méthodes présentées ici dépendent de noyaux dont la taille va jusqu'à $(2N+1)\times(2N+1)$. Cette section montre comment évaluer $N$ pour maximiser le niveau de sécurité. -Pour chaque approche, 1,000 images stegos avec +Pour chaque approche, 1,000 images stégos avec $N=2$, $4$, $6$, $8$, $10$, $12$ et $14$ et dont les supports appartiennent à l'ensemble des 10000 images du challenge BOSS. LA sécurité de l'approche a été évaluée avec le stéganalyseur @@ -741,12 +741,12 @@ compte des variations dans celle-ci. Les dérivées secondes sont certes faciles La principale contribution de ce chapitre est de proposer des fonctions de distorsion basées sur des approximations de dérivées secondes, l'idée sous-jacente étant qu'une zone où les lignes de niveau -ne sont pas clairement définies est peu prédictible. +ne sont pas clairement définies est peu prévisible. Deux approches d'approximation ont été présentées. La première basée sur un produit de convolution, exploite des noyaux déjà intégrés dans des algorithmes de détection de bords. La seconde s'appuie sur une interpolation polynomiale de l'image. -Ces deux méthodes onté été complètement implantées et leur sécurité +Ces deux méthodes ont été complètement implantées et leur sécurité face à des stéganalyseurs a été étudiée. Les résultats encouragent à poursuivre dans cette direction. \ No newline at end of file -- 2.39.5