X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1ba923d87cf3028fb3f60f0b411e155f48767aeb..1211b0e6440c89499806c173f2907ddb4f00afc1:/oxford.tex diff --git a/oxford.tex b/oxford.tex index 6855f14..ebdc417 100644 --- a/oxford.tex +++ b/oxford.tex @@ -1,4 +1,27 @@ -\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$. @@ -6,32 +29,35 @@ 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) @@ -39,48 +65,13 @@ $(S^t)^{t \in \mathds{N}}$ définie par: entre les décompositions binaires sur 32 bits des réels $y$ et $K$ (il est aussi compris entre 0 et 1), \item $\forall t \leqslant l, K^{t+1} = F(K^t,\alpha)$, - \item $\forall t \leqslant l, S^t = \left \lfloor n \times K^t \right \rfloor + 1$, + \item $\forall t \leqslant l, S^t = \left \lfloor \mathsf{N} \times K^t \right \rfloor + 1$, \item $\forall t > l, S^t = 0$, \end{itemize} -où est la fonction chaotique linéaire par morceau~\cite{Shujun1}. +où $F$ est la fonction chaotique linéaire par morceau~\cite{Shujun1}. Les paramètres $K$ et $\alpha$ de cet adapteur de stratégie peuvent être vus comme des clefs. - -% 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. @@ -89,30 +80,24 @@ 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. -%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: @@ -124,13 +109,13 @@ $u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivements des 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 @@ -146,10 +131,10 @@ 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{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 @@ -160,7 +145,7 @@ $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in \mathfrak{B} $ tel que \begin{itemize} -\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[n]$; +\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[\mathsf{N}]$; \item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$ et $|u_p| = |\varphi_p|$. \end{itemize} Soit la base canonique sur l'espace vectoriel $\mathds{R}^{\mid x \mid}$ composée des vecteurs @@ -175,34 +160,31 @@ x = 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, @@ -213,196 +195,450 @@ 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. -%%%%%%%%%%%%%%%%%%%%%%%% +$\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. +