From: Jean-François Couchot Date: Thu, 17 Sep 2015 11:23:04 +0000 (+0200) Subject: validation oxford X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/e9f2cb916f164b15bce8fe96e4f5432d3df9b7b2?ds=inline;hp=d1c0e5b780e93cf63c37b5c802d675247a4d5a21 validation oxford --- diff --git a/ROC.pdf b/ROC.pdf new file mode 100644 index 0000000..c254c5f Binary files /dev/null and b/ROC.pdf differ diff --git a/annexePreuveMarquagedhci.tex b/annexePreuveMarquagedhci.tex new file mode 100644 index 0000000..57de268 --- /dev/null +++ b/annexePreuveMarquagedhci.tex @@ -0,0 +1,97 @@ + +\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} + + + +\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 +\[ + \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 +$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 +$\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 +\[ +\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} +\pi^t_j.\frac{1}{l} +\sum\limits^{l}_{k=1} +p(i =_k j, f_k(j) = i_k ). +\] + +Since +$\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 +\[ +\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} +\pi^t_j. M_{ji} \textrm{ and thus } +\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. +${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. + + +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. +\end{theorem} + +Thanks to this theorem, $M$ +has an unique stationary probability vector $\pi$. +By hypothesis, since $M$ is doubly stochastic we have +$(\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. + \end{proof} diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex new file mode 100644 index 0000000..4cb4138 --- /dev/null +++ b/annexePreuveMarquagefldblement.tex @@ -0,0 +1,64 @@ +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} +\end{array} +\right. +\end{equation}\label{eq:fqq} + +Prouvons que la matrice de Markov associée est doublement stochastique. + +the Markov chain is stochastic by construction. + +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 +$(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$. + +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 +$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 +\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)$). +\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)$) +\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)$). +\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 +$(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$. diff --git a/atq-contrast-eps-converted-to.pdf b/atq-contrast-eps-converted-to.pdf new file mode 100644 index 0000000..a70b2bb Binary files /dev/null and b/atq-contrast-eps-converted-to.pdf differ diff --git a/atq-contrast.pdf b/atq-contrast.pdf new file mode 100644 index 0000000..a31f5de Binary files /dev/null and b/atq-contrast.pdf differ diff --git a/atq-dec-eps-converted-to.pdf b/atq-dec-eps-converted-to.pdf new file mode 100644 index 0000000..779e316 Binary files /dev/null and b/atq-dec-eps-converted-to.pdf differ diff --git a/atq-dec.pdf b/atq-dec.pdf new file mode 100644 index 0000000..97aa2f4 Binary files /dev/null and b/atq-dec.pdf differ diff --git a/atq-flou-eps-converted-to.pdf b/atq-flou-eps-converted-to.pdf new file mode 100644 index 0000000..439a3c3 Binary files /dev/null and b/atq-flou-eps-converted-to.pdf differ diff --git a/atq-flou.pdf b/atq-flou.pdf new file mode 100644 index 0000000..7beee87 Binary files /dev/null and b/atq-flou.pdf differ diff --git a/atq-jp2-eps-converted-to.pdf b/atq-jp2-eps-converted-to.pdf new file mode 100644 index 0000000..a01191e Binary files /dev/null and b/atq-jp2-eps-converted-to.pdf differ diff --git a/atq-jp2.pdf b/atq-jp2.pdf new file mode 100644 index 0000000..4079a41 Binary files /dev/null and b/atq-jp2.pdf differ diff --git a/atq-jpg-eps-converted-to.pdf b/atq-jpg-eps-converted-to.pdf new file mode 100644 index 0000000..77adfc2 Binary files /dev/null and b/atq-jpg-eps-converted-to.pdf differ diff --git a/atq-jpg.pdf b/atq-jpg.pdf new file mode 100644 index 0000000..ed90e39 Binary files /dev/null and b/atq-jpg.pdf differ diff --git a/atq-redim.pdf b/atq-redim.pdf new file mode 100644 index 0000000..b76dba6 Binary files /dev/null and b/atq-redim.pdf differ diff --git a/atq-rot-eps-converted-to.pdf b/atq-rot-eps-converted-to.pdf new file mode 100644 index 0000000..21e6c59 Binary files /dev/null and b/atq-rot-eps-converted-to.pdf differ diff --git a/atq-rot.pdf b/atq-rot.pdf new file mode 100644 index 0000000..1aa8f53 Binary files /dev/null and b/atq-rot.pdf differ diff --git a/main.tex b/main.tex index f711727..2211b41 100644 --- a/main.tex +++ b/main.tex @@ -328,6 +328,14 @@ pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire. \input{annexePreuveDistribution} \input{annexePreuveStopping} +\chapter{Preuves sur le marquage de média}\label{anx:marquage} +\section{Le marquage est $\epsilon$-sego-secure} +\input{annexePreuveMarquagedhci} + +\section{Le mode $f_l$ est doublement stochastique}\label{anx:marquage:dblesto} +\input{annexePreuveMarquagefldblement} + + \backmatter \bibliographystyle{apalike} diff --git a/oxford.tex b/oxford.tex index 1f18e05..53b2dc5 100644 --- a/oxford.tex +++ b/oxford.tex @@ -1,5 +1,9 @@ \JFC{Dire que c'est une synthèse du chapitre 22 de la thèse de Tof} +This section has focused on security with regards to probabilistic behaviors. +Next section studies it in the perspective of topological ones. + + \section{Processus de marquage} @@ -229,265 +233,235 @@ $\hat{y}$ est le second membre de $G_{f_l}^q(S_y,\phi_{m})$. % est marquée, en particulier si l'image a été attaquée entre temps. % On s'intéressera aux mesures de similarité entre $x$ et $z$. -\section{Analyse de sécurité}\label{sec:security} - - - - -As far as we know, Cachin~\cite{Cachin2004} -produces the first fundamental work in information hiding security: -in the context of steganography, the attempt of an attacker to distinguish -between an innocent image and a stego-content is viewed as an hypothesis -testing problem. -Mittelholzer~\cite{Mittelholzer99} next proposed the first theoretical -framework for analyzing the security of a watermarking scheme. -Clarification between robustness and security -and classifications of watermarking attacks -have been firstly presented by Kalker~\cite{Kalker2001}. -This work has been deepened by Furon \emph{et al.}~\cite{Furon2002}, who have translated Kerckhoffs' principle (Alice and Bob shall only rely on some previously shared secret for privacy), from cryptography to data hiding. - -More recently~\cite{Cayre2005,Perez06} classified the information hiding -attacks into categories, according to the type of information the attacker (Eve) -has access to: -\begin{itemize} -\item in Watermarked Only Attack (WOA) she only knows embedded contents $z$; -\item in Known Message Attack (KMA) she knows pairs $(z,y)$ of embedded - contents and corresponding messages; -\item in Known Original Attack (KOA) she knows several pairs $(z,x)$ - of embedded contents and their corresponding original versions; -\item in Constant-Message Attack (CMA) she observes several embedded - contents $z^1$,\ldots,$z^k$ and only knows that the unknown - hidden message $y$ is the same in all contents. -\end{itemize} - -To the best of our knowledge, -KMA, KOA, and CMA have not already been studied -due to the lack of theoretical framework. -In the opposite, security of data hiding against WOA can be evaluated, -by using a probabilistic approach recalled below. - - - +\section{Analyse de sécurité (probabilistes)}\label{sec:watermarking:security:probas} -\subsection{Stego-security}\label{sub:stegosecurity} -%\input{stegosecurity} +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 +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$. -In the Simmons' prisoner problem~\cite{Simmons83}, Alice and Bob are in jail and -they want to, possibly, devise an escape plan by exchanging hidden messages in -innocent-looking cover contents. These messages are to be conveyed to one -another by a common warden named Eve, who eavesdrops all contents and can choose -to interrupt the communication if they appear to be stego-contents. +Cette définition probabiliste est rappelée ci-après. +Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle porbabiliste +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. -Stego-security, defined in this well-known context, is the highest security -class in Watermark-Only Attack setup, which occurs when Eve has only access to -several marked contents~\cite{Cayre2008}. - - -Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of -$N_0$ initial host contents, and $p(Y|K)$ the probabilistic model of $N_0$ -marked contents s.t. each host content has been marked -with the same key $K$ and the same embedding function. - -\begin{definition}[Stego-Security~\cite{Cayre2008}] -\label{Def:Stego-security} The embedding function is \emph{stego-secure} -if $\forall K \in \mathds{K}, p(Y|K)=p(X)$ is established. +\begin{definition}[Stégo-Sécurité~\cite{Cayre2008}] +\label{Def:Stego-security} +La fonction d'embarquement is \emph{stégo-sécure} +si la propriété $\forall K \in \mathds{K}, p(Y|K)=p(X)$ est établie. \end{definition} +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: +\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} -%Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of -%$N_0$ initial host contents, and $p(Y|K)$ the probabilistic model of $N_0$ -%marked contents s.t. each host content has been marked -%with the same key $K$ and the same embedding function. - -%\begin{definition}[Stego-Security] -%\label{Def:Stego-security} The embedding function is \emph{stego-secure} -%if $\forall K \in \mathds{K}, p(Y|K)=p(X)$ is established. -%\end{definition} - - Stego-security states that the knowledge of $K$ does not help to make the - difference between $p(X)$ and $p(Y)$. This definition implies the following - property: - $$p(Y|K_1)= \cdots = p(Y|K_{N_k})=p(Y)=p(X)$$ - This property is equivalent to a zero Kullback-Leibler divergence, which is the - accepted definition of the "perfect secrecy" in steganography~\cite{Cachin2004}. - - -\subsection{The negation mode is stego-secure} -To make this article self-contained, this section recalls theorems and proofs of stego-security for negation mode published in~\cite{gfb10:ip}. - -\begin{proposition} \emph{dhCI dissimulation} of Definition \ref{def:dhCI} with -negation mode and CIIS strategy-adapter is stego-secure, whereas it is not the -case when using CIDS strategy-adapter. -\end{proposition} - - -\begin{proof} On the one hand, let us suppose that $X \sim -\mathbf{U}\left(\mathbb{B}^n\right)$ when using \linebreak CIIS$(K,\_,\_,l)$. -We prove by a -mathematical induction that $\forall t \in \mathds{N}, X^t \sim -\mathbf{U}\left(\mathbb{B}^n\right)$. - -The base case is immediate, as $X^0 = X \sim -\mathbf{U}\left(\mathbb{B}^n\right)$. Let us now suppose that the statement $X^t -\sim \mathbf{U}\left(\mathbb{B}^n\right)$ holds until for some $t$. -Let $e \in -\mathbb{B}^n$ and \linebreak $\mathbf{B}_k=(0,\cdots,0,1,0,\cdots,0) \in -\mathbb{B}^n$ (the digit $1$ is in position $k$). - -So -$P\left(X^{t+1}=e\right)=\sum_{k=1}^n -P\left(X^t=e\oplus\mathbf{B}_k,S^t=k\right)$ where -$\oplus$ is again the bitwise exclusive or. -These two events are independent when -using CIIS strategy-adapter -(contrary to CIDS, CIIS is not built by using $X$), - thus: -$$P\left(X^{t+1}=e\right)=\sum_{k=1}^n -P\left(X^t=e\oplus\mathbf{B}_k\right) \times P\left(S^t=k\right).$$ - -According to the -inductive hypothesis: $P\left(X^{n+1}=e\right)=\frac{1}{2^n} \sum_{k=1}^n -P\left(S^t=k\right)$. The set of events $\left \{ S^t=k \right \}$ for $k \in -\llbracket 1;n \rrbracket$ is a partition of the universe of possible, so -$\sum_{k=1}^n P\left(S^t=k\right)=1$. Finally, -$P\left(X^{t+1}=e\right)=\frac{1}{2^n}$, which leads to $X^{t+1} \sim -\mathbf{U}\left(\mathbb{B}^n\right)$. This result is true for all $t \in -\mathds{N}$ and then for $t=l$. - -Since $P(Y|K)$ is $P(X^l)$ that is proven to be equal to $P(X)$, -we thus have established that, -$$\forall K \in [0;1], P(Y|K)=P(X^{l})=P(X).$$ -So dhCI dissimulation with CIIS -strategy-adapter is stego-secure. - -On the other hand, due to the definition of CIDS, we have \linebreak -$P(Y=(1,1,\cdots,1)|K)=0$. -%\JFC{Pourquoi? Justifier davantage là ou dans la def de CIDS} -So there is no uniform repartition for the stego-contents $Y|K$. -\end{proof} - +\section{Analyse de sécurité (chaos)}\label{sec:watermarking:security:chaos} +On rappelle uniquement la définition de chaos-sécurité +introduite dans~\cite{guyeuxphd}. -To sum up, Alice and Bob can counteract Eve's attacks in WOA setup, when using -dhCI dissimulation with CIIS strategy-adapter. To our best knowledge, this is -the second time an information hiding scheme has been proven to be stego-secure: -the former was the spread-spectrum technique in natural marking -configuration with $\eta$ parameter equal to 1 \cite{Cayre2008}. +\begin{definition}[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} +Tout repose ainsi sur la capacité que l'on a à produire des fonctions +dont le graphe des itérations unaires sera fortement connexe. +Ceci a déjà été traité au chapitre~\ref{chap:carachaos}. +La seule complexité est l'adaptabilité de la fonction au nombre $l$ de LSBs. + +On considère par exemple 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{ si $i$ est impair} \\ +x_i \oplus x_{i-1} \textrm{ si $i$ est pair} +\end{array} +\right. +\end{equation}\label{eq:fqq} + +on peut déduire imé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 +chaos-sécure. + +\section{Applications aux domaines fréquentiels} +Le schéma d'algorithme présenté dans ce chapitre a été appliqué au marquage d'images +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. +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 + 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 +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, +\item 0 sinon. +\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. +\subsection{Fonction de signification pour l'embarquement dans les DWT} -\subsection{A new class of $\varepsilon$-stego-secure schemes} +On considère un hôte dnas 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. +Formellement à chaque bit +la fonction de signification $u$ associe -Let us prove that, -\begin{theorem}\label{th:stego} -Let $\epsilon$ be positive, -$l$ be any size of LSCs, -$X \sim \mathbf{U}\left(\mathbb{B}^l\right)$, -$f_l$ be an image mode s.t. -$\Gamma(f_l)$ is strongly connected and -the Markov matrix associated to $f_l$ -is doubly stochastic. -In the instantiated \emph{dhCI dissimulation} algorithm -with any uniformly distributed (u.d.) strategy-adapter -that is independent from $X$, -there exists some positive natural number $q$ s.t. -$|p(X^q)- p(X)| < \epsilon$. -\end{theorem} +\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 + 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 + bits de poids faible de cette représentation, +\item 0 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. + + +\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 +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}. + +A chaque série d'expériences, un ensemble de 50 images est choisi aléatoirement +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 +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), +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 +à la figure~\ref{fig:atq:dhc}. -\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 -\[ - \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 -$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 -$\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 -\[ -\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} -\pi^t_j.\frac{1}{l} -\sum\limits^{l}_{k=1} -p(i =_k j, f_k(j) = i_k ). -\] +\begin{figure}[ht] + \centering + \subfigure[Découpage]{ + \includegraphics[width=0.5\textwidth]{atq-dec}\label{Fig:atq:dec:curves} + } + \subfigure[Compression JPEG]{ + \includegraphics[width=0.45\textwidth]{atq-jpg}\label{Fig:atq:jpg:curves} + } + \subfigure[Compression JPEG 2000]{ + \includegraphics[width=0.45\textwidth]{atq-jp2}\label{Fig:atq:jp2:curves} + } + \subfigure[Modification du contrast]{ + % \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} + } + \subfigure[Accentuation des bords]{ + % \includegraphics[width=0.45\textwidth]{atq-flou.pdf}\label{Fig:atq:sh:curve}} + \includegraphics[width=0.45\textwidth]{atq-flou}\label{Fig:atq:sh:curve} + } + \subfigure[Rotation]{ + % \includegraphics[width=0.45\textwidth]{atq-rot.pdf}\label{Fig:atq:rot:curve}} + \includegraphics[width=0.45\textwidth]{atq-rot}\label{Fig:atq:rot:curve} + } +\caption{Illustration de la robustesse}\label{fig:atq:dhc} +\end{figure} -Since -$\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 -\[ -\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} -\pi^t_j. M_{ji} \textrm{ and thus } -\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. -${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. - - -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. -\end{theorem} +\subsection{Evaluation 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 +celles données ci dessus. -Thanks to this theorem, $M$ -has an unique stationary probability vector $\pi$. -By hypothesis, since $M$ is doubly stochastic we have -$(\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. - \end{proof} +Pour chaque entier $t$ entre 5 et 55 +et chaque image $x \in \textit{WA} \cup A$, +on calcule la différence entre $\hat{y}$ et $\varphi_m(z)$. +L'image est dite marquée si cette différence est en dessous du seuil $t$ considéré +\begin{itemize} +\item si elle est dite marquée et si $x$ appartient à $\textit{WA}$ + c'est un vrai cas positif (TP); +\item si elle est dite non marquée et si $x$ appartient cependant à $\textit{WA}$ + c'est un faux cas négatif (FN); +\item si elle est dite marquée et si $x$ appartient cependant à $\textit{A}$ + c'est un faux cas positif (FP); +\item enfin si elle est dite non marquée et si $x$ appartient à $\textit{A}$ + c'est un vrai cas négatif (TN). +\end{itemize} -This section has focused on security with regards to probabilistic behaviors. -Next section studies it in the perspective of topological ones. +\begin{figure}[ht] +\begin{center} +\includegraphics[width=7cm]{ROC} +\end{center} +\caption{Courbes ROC de seuils de détection}\label{fig:roc:dwt} +\end{figure} +La courbe ROC construite à partir des points de coordonnées (TP,FP) issus +de ces seuils est +donnée à la figure~\ref{fig:roc:dwt}. +Pour la fonction $f_l$ et pour la fonction négation respectivement, +la détection est optimale pour le seuil de 45\% correspondant au point (0.01, 0.88) +et pour le seuil de 46\% correspondant au point (0.04, 0.85) +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. +L'approche est résistante à: +\begin{itemize} +\item tous les découpages où le pourcentage est inférieur à 85\%; +\item les compression dont le ratio est supérieur à 82\% dans le domaine + DWT et 67\% dans celui des DCT; +\item les modifications du contraste lorsque le renforcement est dans + $[0.76,1.2]$ dans le domaine DWT et $[0.96,1.05]$ dans le domaine DCT; +\item toutes les rotations dont l'angle est inférieur à 20 degrés dans le domaine DCT et + celles dont l'angle est inférieur à 13 degrés dans le domaine DWT. +\end{itemize} -%\subsection{Security in KMA, KOA and CMA setups} -%\input{KMOA.tex}