-\JFC{Dire que c'est une synthèse du chapitre 22 de la thèse de Tof}
+La propriété de régularité des fonctions chaotiques est à l'origine du marquage de documents numériques: de tout média, même tronqué, on peut réextraire la
+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 (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}.
+
+On remarque cependant que l'algorithme formalisé dans ces sections ne permet
+d'embarquer \textit{in fine} qu'un bit qui est vrai si l'image est marquée
+et faux dans le cas contraire.
+Il ne permet pas d'extraire le contenu du message initial à partir de
+l'image marquée. La section~\ref{sec:watermarking:extension}
+propose une solution à ce problème.
+
+Les trois premières sections de ce chapitre sont une reformulation
+du chapitre 22 de~\cite{guyeux10}. Elles ont été publiées à~\cite{bcg11:ij}.
+L'extension a quant à elle été publiée dans~\cite{bcfg+13:ip}.
+
+
+
+\section{Processus de marquage binaire}\label{sec:watermarking:formulation}
Par la suite, le message numérique qu'on cherche à embarquer est
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}
-\begin{definition}[Mode]
+\subsection{Embarquement}
+
+
+\begin{Def}[Mode]
\label{def:mode}
Soit $\mathsf{N}$ un entier naturel.
Un mode est une application de $\mathds{B}^{\mathsf{N}}$
dans lui même.
-\end{definition}
+\end{Def}
-\begin{definition}[Adapteur de Stratégie]
+\begin{Def}[Adapteur de Stratégie]
\label{def:strategy-adapter}
Un \emph{adapteur de stratégie} est une fonction $\mathcal{S}$
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}}$.
-\end{definition}
+ $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)
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.
-
-% Les paramère Parameters of CIIS strategy-adapter will be instantiate as follows:
-% $K$ is the secret embedding key, $y$ is the secret message,
-% $\alpha$ is the threshold of the piecewise linear chaotic map,
-% which can be set as $K$ or can act as a second secret key.
-% Lastly, $l$ is for the iteration number bound:
-% enlarging its value improve the chaotic behavior of the scheme,
-% but the time required to achieve the embedding grows too.
-
-% Another strategy-adapter is the
-% \emph{Chaotic Iterations with Dependent Strategy} (CIDS)
-% with parameters $(l,X) \in \mathds{N}\times \mathds{B}^\mathds{N}$,
-% which is the function that maps any $ n \in \mathds{N}$ to
-% the sequence $\left(S^t\right)^{t \in \mathds{N}}$ defined by:
-% \begin{itemize}
-% \item $\forall t \leqslant l$, if $t \leqslant l$ and $X^t = 1$,
-% then $S^t=t$, else $S^t=1$.
-% \item $\forall t > l, S^t = 0$.
-% \end{itemize}
-
-
-
-
-% Let us notice that the terms of $x$ that may be replaced by terms issued
-% from $y$ are less important than other: they could be changed
-% without be perceived as such. More generally, a
-% \emph{signification function}
-% attaches a weight to each term defining a digital media,
-% w.r.t. its position $t$:
-
-% \begin{definition}[Signification function]
-% A \emph{signification function}
-% $(u^k)^{k \in \Nats}$. % with a limit equal to 0.
-% \end{definition}
-
-
+On remarque que cette stratégie est unaire.
sous la forme d'un réel.
Ceci se fait à l'aide d'une fonction de signification.
-%We first notice that terms of $x$ that may be replaced by terms issued
-%from $y$ are less important than other: they could be changed
-%without being perceived as such. More generally, a
-%\emph{signification function}
-%attaches a weight to each terms defining a digital media,
-%depending on its position $t$, as follows.
-\begin{definition}[Fonction de signification ]
+\begin{Def}[Fonction de signification ]
Une \emph{fonction de signification }
est une fonction $u$ qui a toute
séquence finie de bit $x$ associe la séquence
$(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{definition}
+\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{definition}[Signification des bits]\label{def:msc,lsc}
+\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:
u_p &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et }
u^k \in ]m;M[ \textrm{ et } k \le \mid x \mid \right)
\end{eqnarray*}
- \end{definition}
+ \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$:
-\begin{definition}[Fonction de décomposition ]
+\begin{Def}[Fonction de décomposition ]
Soit $u$ une fonction de signification,
$m$ et $M$ deux réels t.q $m < M$.
Tout hôte $x$ peut se décomposer en
pour chaque hôte $x$ est la \emph{fonction de décomposition}, plus tard notée
$\textit{dec}(u,m,M)$ puisqu'elle est paramétrée par
$u$, $m$ and $M$.
-\end{definition}
+\end{Def}
-\begin{definition}[Recomposition]
+\begin{Def}[Recomposition]
Soit un sextuplet
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in
\mathfrak{N} \times
\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
La fonction qui associe $x$ à chaque sextuplet
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ défini comme ci-dessus est appelée
\emph{fonction de recomposition}.
-\end{definition}
+\end{Def}
Un embarquement consiste à modifier les valeurs de
$\phi_{m}$ (de $x$) en tenant compte de $y$.
Cela se formalise comme suit:
-\begin{definition}[Embedding media]
+\begin{Def}[Embarquement de message]
Soit une fonction de décomposition $\textit{dec}(u,m,M)$,
$x$ un support,
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ son image par $\textit{dec}(u,m,M)$,
et $y$ un média numérique de taille $|u_m|$.
Le média $z$ résultant de l'embarquement d'$y$ dans $x$ est l'image de
-$(u_M,u_m,u_p,\phi_{M},g(\phi_{m},y),\phi_{p})$
-par la fonction de recomposition $\textit{rec}$ avec
-$g : \Bool^{|u_m|} \times \Bool^{|u_m|} \to \Bool^{|u_m|} $
-est la fonction de modification des bits de $u_m$ selon $y$.
-\end{definition}
-
-Dans l'embaquement LSB,
-$u$ est la fonction qui asocie 0 aux bits de poids faible de chaque pixel et 1 ailleur,
-$m$ et $M$ valent respectivement 0 et 1 et
-$g$ remplace (\teixtit{i.e.}, écrase) tous les bits de $u_m$ par ceux de $y$.
+$(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
+par la fonction de recomposition $\textit{rec}$.
+% avec
+% $g : \Bool^{|u_m|} \times \Bool^{|u_m|} \to \Bool^{|u_m|} $
+% est la fonction de modification des bits de $u_m$ selon $y$.
+\end{Def}
+
On peut étendre l'algorithme dhCI~\cite{gfb10:ip} d'embarquement de message comme suit:
-\begin{definition}[]
+\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,
L'algorithme d'embarquement de message associe à chaque
couple $(x,y)$ le média $z$ résultat de l'embarquement de
-$\hat{y}$ dans $x$, t. q.
-%%%%%%%%%%%%%%%%%%%%%%%%
+$\hat{y}$ dans $x$, t. q.:
+
\begin{itemize}
-\item We instantiate the mode $f$ with parameter $l=|u_m|$, leading to
- the function $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$.
-\item We instantiate the strategy adapter $\mathcal{S}$
-with parameter $y$ (and some other ones eventually).
-This instantiation leads to the strategy $S_y \in \llbracket 1;l\rrbracket ^{\Nats}$.
-
-\item We iterate $G_{f_l}$ with initial configuration $(S_y,\phi_{m})$.
-\item $\hat{y}$ is finally the $q$-th term of these iterations.
+\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 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
+ à l'équation~(\ref{eq:sch:unaire}).
+\item $\hat{y}$ est le second membre du $q^{\textrm{ème}}$ terme obtenu.
\end{itemize}
-\end{definition}
-
-
-To summarize, iterations are realized on the LSCs of the
-host content
-(the mode gives the iterate function,
-the strategy-adapter gives its strategy),
-and the last computed configuration is re-injected into the host content,
-in place of the former LSCs.
-
-
-
-%\begin{definition}[Significance of coefficients]\label{def:msc,lsc}
-%Let $(u^k)^{k \in \Nats}$ be a signification function,
-%$m$ and $M$ be two reals s.t. $m < M$. Then
-%the \emph{most significant coefficients (MSCs)} of $x$ is the finite
-% vector $u_M$,
-%the \emph{least significant coefficients (LSCs)} of $x$ is the
-%finite vector $u_m$, and
-%the \emph{passive coefficients} of $x$ is the finite vector $u_p$ such that:
-%\begin{eqnarray*}
-% u_M &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k
-% \geqslant M \textrm{ and } k \le \mid x \mid \right) \\
-% u_m &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k
-% \le m \textrm{ and } k \le \mid x \mid \right) \\
-% u_p &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ and }
-%u^k \in ]m;M[ \textrm{ and } k \le \mid x \mid \right)
-%\end{eqnarray*}
-% \end{definition}
-
-%For a given host content $x$,
-%MSCs are then ranks of $x$ that describe the relevant part
-%of the image, whereas LSCs translate its less significant parts.
-%We are then ready to decompose an host $x$ into its coefficients and
-%then to recompose it. Next definitions formalize these two steps.
-
-%\begin{definition}[Decomposition function]
-%Let $(u^k)^{k \in \Nats}$ be a signification function,
-%$\mathfrak{B}$ the set of finite binary sequences,
-%$\mathfrak{N}$ the set of finite integer sequences,
-%$m$ and $M$ be two reals s.t. $m < M$.
-%Any host $x$ may be decomposed into
-%$$
-%(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})
-%\in
-%\mathfrak{N} \times
-%\mathfrak{N} \times
-%\mathfrak{N} \times
-%\mathfrak{B} \times
-%\mathfrak{B} \times
-%\mathfrak{B}
-%$$
-%where
-%\begin{itemize}
-%\item $u_M$, $u_m$, and $u_p$ are coefficients defined in Definition
-%\ref{def:msc,lsc};
-%\item $\phi_{M} = \left( x^{u^1_M}, x^{u^2_M}, \ldots,x^{u^{|u_M|}_M}\right)$;
-% \item $\phi_{m} = \left( x^{u^1_m}, x^{u^2_m}, \ldots,x^{u^{|u_m|}_m} \right)$;
-% \item $\phi_{p} =\left( x^{u^1_p}, x^{u^2_p}, \ldots,x^{u^{|u_p|}_p}\right) $.
-% \end{itemize}
-%The function that associates the decomposed host to any digital host is
-%the \emph{decomposition function}. It is
-%further referred as $\textit{dec}(u,m,M)$ since it is parametrized by
-%$u$, $m$, and $M$. Notice that $u$ is a shortcut for $(u^k)^{k \in \Nats}$.
-%\end{definition}
-
-
-%\begin{definition}[Recomposition]
-%Let
-%$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in
-%\mathfrak{N} \times
-%\mathfrak{N} \times
-%\mathfrak{N} \times
-%\mathfrak{B} \times
-%\mathfrak{B} \times
-%\mathfrak{B}
-%$ s.t.
-%\begin{itemize}
-%\item the sets of elements in $u_M$, elements in $u_m$, and
-%elements in $u_p$ are a partition of $\llbracket 1, n\rrbracket$;
-%\item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$, and $|u_p| = |\varphi_p|$.
-%\end{itemize}
-%One may associate the vector
-%$$x =
-%\sum_{i=1}^{|u_M|} \varphi^i_M . e_{{u^i_M}} +
-%\sum_{i=1}^{|u_m|} \varphi^i_m .e_{{u^i_m}} +
-%\sum_{i=1}^{|u_p|} \varphi^i_p. e_{{u^i_p}}
-%$$
-%\noindent where $e_i$ is the sequence whose $j-$th term is equal to $\overline{\Delta(i,j)}$, \emph{i.e.}, $(e_i)_{i \in \mathds{N}}$ is the usual basis of the $\mathds{R}-$vectorial space $\left(\mathds{R}^\mathds{N}, +, .\right)$.
-%The function that associates $x$ to any
-%$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ following the above constraints
-%is called the \emph{recomposition function}.
-%\end{definition}
-
-%The embedding consists to the replacement of the values of
-%$\phi_{m}$ of $x$'s LSCs by $y$.
-%It then composes the two decomposition and
-%recomposition functions seen previously. More formally:
-
-
-%\begin{definition}[Embedding digital media]
-%Let $\textit{dec}(u,m,M)$ be a decomposition function,
-%$x$ be a host content,
-%$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ be its image by $\textit{dec}(u,m,M)$,
-%and $y$ be a digital media of size $|u_m|$.
-%The digital media $z$ resulting on the embedding of $y$ into $x$ is
-%% the
-%% result of the \emph{embedding} of $y$ in $x$ if
-%% $$
-%% \forall n \in \llbracket1, |x|\rrbracket , z^n = \left\{
-%% \begin{array}{ll}
-%% x^n & \textrm{if } \phi^n_m > m,\\
-%% y^n & \textrm{else.}
-%% \end{array}
-%% \right.
-%% $$
-%%
-%% In other words, $z$ is
-%the image of $(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
-%by the recomposition function $\textit{rec}$.
-%\end{definition}
-
-%We can now define the information hiding scheme called \emph{dhCI}:
-
-%\begin{definition}[Data hiding dhCI]
-% \label{def:dhCI}
-%Let $\textit{dec}(u,m,M)$ be a decomposition function,
-%$f$ be a mode,
-%$\mathcal{S}$ be a strategy adapter,
-%$x$ be an host content,\linebreak
-%$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ be its image by $\textit{dec}(u,m,M)$,
-%and $y$ be a digital media of size $l=|u_m|$.
-
-
-%The \emph{dhCI dissimulation} is the application that maps any
-%$(x,y)$ to the digital media $z$ resulting on the embedding of
-%$\hat{y}$ into $x$, s.t.
-
-%\begin{itemize}
-%\item We instantiate the mode $f$ with parameter $l=|u_m|$, leading to
-% the function $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$.
-%\item We instantiate the strategy adapter $\mathcal{S}$
-%with parameter $y$ (and some other ones eventually).
-%This instantiation leads to the strategy $S_y \in \llbracket 1;l\rrbracket ^{\Nats}$.
-
-%\item We iterate $G_{f_l}$ with initial configuration $(S_y,\phi_{m})$.
-%\item $\hat{y}$ is finally the $l$-th term of these iterations.
-%\end{itemize}
-%\end{definition}
-
-
-%To summarize, some iterations are realized on the LSCs of the
-%host content
-%(the mode gives the iterate function,
-%the strategy-adapter gives its strategy),
-%and the last computed state is re-injected into the host content,
-%in place of the former LSCs.
-
-
-
-
-
-
-Notice that in order to preserve the unpredictable behavior of the system,
-the size of the digital medias is not fixed.
-This approach is thus self adapted to any media, and more particularly to
-any size of LSCs.
-However this flexibility enlarges the complexity of the presentation:
-we had to give Definitions~\ref{def:mode} and~\ref{def:strategy-adapter}
-respectively of mode and strategy adapter.
+\end{Def}
+
+
+La figure~\ref{fig:organigramme} synthétise la démarche.
\begin{figure}[ht]
\centering
%\includegraphics[width=8.5cm]{organigramme2.pdf}
-\includegraphics[width=8.5cm]{organigramme2.eps}
+\includegraphics[width=8.5cm]{organigramme22}
\caption{The dhCI dissimulation scheme}
\label{fig:organigramme}
\end{figure}
-Next section shows how to check whether a media contains a mark.
+
+
+\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
+la marque à embarquer $y$, le support $x$ et que l'on a face à soit un média
+$z$.
+
+
+\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
+$q$ un entier naturel strictement positif,
+$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$ 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{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.
+% On s'intéressera aux mesures de similarité entre $x$ et $z$.
+
+\section{Analyse de sécurité (probabilistes)}\label{sec:watermarking:security:probas}
+
+
+Récemment~\cite{Cayre2005,Perez06} ont proposé des classes de sécurité pour le
+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 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{Def}[Stégo-Sécurité~\cite{Cayre2008}]
+\label{Def:Stego-security}
+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{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 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{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é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)| < \varepsilon$.
+\end{restatable}
+
+
+
+\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}.
+
+
+\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 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.
+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 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 $\varepsilon$-stégo-sécure et
+chaos-sécure.
+
+\section{Applications aux domaines fréquentiels}\label{sec:watermarking:frequentiel}
+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é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 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 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,
+\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)$
+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 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.
+Formellement à chaque bit
+la fonction de signification $u$ associe
+
+\begin{itemize}
+\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 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 -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)$
+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)
+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}.
+
+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 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 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 rappelée pour chacune des attaques
+à la figure~\ref{fig:atq:dhc}.
+
+
+\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 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}
+ }
+ \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}
+
+
+\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 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
+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}
+
+
+\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 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\%;
+\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}
+
+
+\section{Embarquons d'avantage qu'1 bit}\label{sec:watermarking:extension}
+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'objectif de l'algorithme présenté dans cette section et introduit
+dans~\cite{fgb11:ip}.
+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}.
+
+
+
+Commençons par quelques conventions de notations:
+\begin{itemize}
+\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é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}$
+ est la \emph{stratégie de place} et définit quel
+ élément de $x$ est modifié à chaque itération;
+ \item $S_c \in \mathbb{S}_\mathsf{P}$ est la \textbf{stratégie de choix}
+ qui définit quel indice du vecteur de marque est embarqué à chaque
+ itération;
+ \item $S_m \in \mathbb{S}_\mathsf{P}$ est la \textbf{stratégie de mélange}
+ qui précise quel élément de la marque est inversé à chaque itération.
+\end{itemize}
+
+% In what follows, $x^0$ and $m^0$ are sometimes replaced by
+% $x$ and $m$ for the sake of brevity,
+% when such abridge does not introduce confusion.
+
+
+% \subsection{The $\CID$ scheme}\label{sub:ci2:scheme}
+Le processus itératif modifiant $x$ est défini comme suit.
+Pour chaque $(n,i,j) \in
+\mathds{N}^{\ast} \times \llbracket 0;\mathsf{N}-1\rrbracket \times \llbracket
+0;\mathsf{P}-1\rrbracket$, on a:
+\begin{equation*}
+\left\{
+\begin{array}{l}
+x_i^n=\left\{
+\begin{array}{ll}
+x_i^{n-1} & \text{ if }S_p^n\neq i \\
+m_{S_c^n}^{n-1} & \text{ if }S_p^n=i.
+\end{array}
+\right.
+\\
+\\
+m_j^n=\left\{
+\begin{array}{ll}
+m_j^{n-1} & \text{ if }S_m^n\neq j \\
+ & \\
+\overline{m_j^{n-1}} & \text{ if }S_m^n=j.
+\end{array}
+\right.
+\end{array}
+\right.
+\end{equation*}
+%\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\}$
+l'ensemble de cardinalité $k \leq l$ (les doublons sont supprimés).
+qui contient la liste des indices $i$, $1 \le i \le p$,
+tels que $x_i$ a été modifié.
+On considère $\Im(S_c)_{|D}= \{S^{d_1}_c, S^{d_2}_c, \ldots, S^{d_k}_c\}$
+où
+$d_i$ est la dernière date où l'élément $i \in \Im(S_p)$ a été modifié.
+Cet ensemble doit être égal à $\llbracket 0 ;\mathsf{P} -1 \rrbracket$.
+
+Pour peu que l'on sache satisfaire la contrainte précédente,
+on remplace $x $ par $x^l \in \mathbb{B}^{\mathsf{N}}$ dans
+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étude et de correction
+de l'approche.
+L'étude de ces propriétés est l'objectif de la section qui suit.
+
+
+
+
+
+
+\subsection{Correction et complétude du schéma}\label{sub:ci2:discussion}
+
+On ne donne ici que le théorème. La preuve est placée en annexes~\ref{anx:preuve:marquage:correctioncompletue}.
+
+\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{restatable}
+
+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é 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 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.
+
+\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 $y'$.
+
+Pour mesurer la distance entre $m'$ et $m$, on
+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.
+
+Beaucoup de mesures de similarité~\cite{yule1950introduction,Anderberg-Cluster-1973,Rifqi:2000:DPM:342947.342970}, dépendent des ensembles
+$a$, $b$, $c$ et $d$ définis par
+$a = |M \cap M' |$,
+$b = |M \setminus M' |$,
+$c = |M' \setminus M|$, and
+$d = |\overline{M} \cap \overline{M'}|$
+
+Selon ~\cite{rifq/others03} la mesure de Fermi-Dirac $S_{\textit{FD}}$
+est celle dont le pouvoir de discrimination est le plus fort,
+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 déclaré
+comme marqué et le message doit pouvoir être extrait.
+
+\subsection{Etude de robustesse}\label{sec:watermarking:robustesse}
+La méthode d'expérimentation de robustesse appliquée à la section précédente
+pourrait être réappliquée ici et nous pourrions obtenir, grâce aux courbes de
+ROC une valeur seuil pour déterminer si une marque est présente ou pas.
+Dans~\cite{bcfg+13:ip}, nous n'avons cependant pas poussé
+la démarche plus loin que de l'embarquement
+dans les bits de poids faible en spatial et l'on sait que ceci est
+particulièrement peu robuste.
+
+
+\section{Conclusion}
+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.
+Le chapitre suivant s'intéresse au marquage, mais dans un autre domaine que celui des images.
+
