correction prng chaos chap 5

[hdrcouchot.git] / oxford.tex

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~\ref{sec:watermarking:security:probas} 
et l'approche chaotique~\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.
On parle alors respectivement de \emph{mode} et d'\emph{adapteur de stratégies} 

\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{Def}



\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{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
$(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)
   égal au ou exclusif (xor) 
   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 > l, S^t = 0$,
 \end{itemize}
où  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.




On peut attribuer à chaque bit du média hôte $x$ sa valeur d'importance 
sous la forme d'un réel.
Ceci se fait à l'aide d'une 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{Def}

Pour alléger le discours, par la suite, on nottera $(u^k(x))$ pour $(u^k)$ 
lorsque cela n'est pas ambigüe.
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 
\emph{bits les plus significatifs  (MSBs)} de $x$,
\emph{bits les moins significatifs (LSBs)} de $x$ 
\emph{bits passifs} of $x$ définis par:
\begin{eqnarray*}
  u_M &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
    \geqslant M \textrm{ et }  k \le \mid x \mid \right) \\
  u_m &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
  \le m \textrm{ et }  k \le \mid x \mid \right) \\
   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{Def}

On peut alors définir une fonction de décompostion  
puis de recomposition pour un hôte $x$:


\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
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
avec 
\begin{itemize}
\item $u_M$, $u_m$, et  $u_p$ construits comme à la définition~\label{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}
La fonction qui associe $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
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{Def} 


\begin{Def}[Recomposition]
Soit un sextuplet 
$(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} 
$ tel que
\begin{itemize}
\item les ensembles $u_M$, $u_m$ et  $u_p$ forment une partition de  $[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 
 $e_1, \ldots, e_{\mid x \mid}$.
On peut construire le vecteur 
\[
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}} 
\]
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{Def}

Un embarquement consiste à modifier les valeurs de  
$\phi_{m}$ (de $x$) en tenant compte de $y$. 
Cela se formalise comme suit:

\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},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{Def}[Embarquement dhCI étendu]
 \label{def:dhCI:ext}
Soit $\textit{dec}(u,m,M)$ une function de décomposition,
$f$ un mode, 
$\mathcal{S}$ un adapteur de stratégie,
$x$ un hôte, 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ 
sont image par  $\textit{dec}(u,m,M)$,
$q$ un entier naturel positif
et $y$ un média numérique de taille $l=|u_m|$.

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.:

\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
$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{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]{organigramme22}
\caption{The dhCI dissimulation scheme}
\label{fig:organigramme}
\end{figure}




\subsection{Détection d'un media 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{definition}[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$ is 
$(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}

% 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. 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$.

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.

\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}



\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{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}\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é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} 

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

\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{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}


\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.

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 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}


\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'bjectif de l'algorithme présenté dans cette section et introduit 
dans~\cite{fgb11:ip}.
On 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édement, 
  $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{definition}
\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études 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{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}

Sous ces hypothèes, 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 
$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.
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.

\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'$. 

Pour mesurer la distance entre $m'$ et $m$, on 
considère repsectivement 
$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 declaré 
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}
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
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.