From 1f464e74c8a635f445b2acf2825ee2b61405e46e Mon Sep 17 00:00:00 2001 From: couchot Date: Tue, 15 Sep 2015 09:09:47 +0200 Subject: [PATCH] =?utf8?q?oxford:=20jusqu'=C3=A0=20la=20s=C3=A9curit=C3=A9?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- oxford.tex | 555 ++++++++++++++++++++++++++++++----------------------- 1 file changed, 320 insertions(+), 235 deletions(-) diff --git a/oxford.tex b/oxford.tex index 6855f14..1f18e05 100644 --- a/oxford.tex +++ b/oxford.tex @@ -1,5 +1,8 @@ \JFC{Dire que c'est une synthèse du chapitre 22 de la thèse de Tof} + +\section{Processus de marquage} + 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$. @@ -9,16 +12,19 @@ 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} -\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}$ @@ -26,7 +32,7 @@ dans lui même. qui associe à chaque entier naturel $\mathsf{N}$ la suite $S \in \llbracket 1, n\rrbracket^{\mathds{N}}$. -\end{definition} +\end{Def} On définit par exemple l'adapteur CIIS (\emph{Chaotic Iterations with Independent Strategy}) @@ -45,42 +51,7 @@ $(S^t)^{t \in \mathds{N}}$ définie par: 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. - -% 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,27 +60,21 @@ 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. 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 @@ -124,13 +89,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 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 +111,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 @@ -175,32 +140,29 @@ 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} +$(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} -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$. 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, $f$ un mode, @@ -213,196 +175,319 @@ 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 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$. -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} +\section{Analyse de sécurité}\label{sec:security} -%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|$. +As far as we know, Cachin~\cite{Cachin2004} +produces the first fundamental work in information hiding security: +in the context of steganography, the attempt of an attacker to distinguish +between an innocent image and a stego-content is viewed as an hypothesis +testing problem. +Mittelholzer~\cite{Mittelholzer99} next proposed the first theoretical +framework for analyzing the security of a watermarking scheme. +Clarification between robustness and security +and classifications of watermarking attacks +have been firstly presented by Kalker~\cite{Kalker2001}. +This work has been deepened by Furon \emph{et al.}~\cite{Furon2002}, who have translated Kerckhoffs' principle (Alice and Bob shall only rely on some previously shared secret for privacy), from cryptography to data hiding. -%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. +More recently~\cite{Cayre2005,Perez06} classified the information hiding +attacks into categories, according to the type of information the attacker (Eve) +has access to: +\begin{itemize} +\item in Watermarked Only Attack (WOA) she only knows embedded contents $z$; +\item in Known Message Attack (KMA) she knows pairs $(z,y)$ of embedded + contents and corresponding messages; +\item in Known Original Attack (KOA) she knows several pairs $(z,x)$ + of embedded contents and their corresponding original versions; +\item in Constant-Message Attack (CMA) she observes several embedded + contents $z^1$,\ldots,$z^k$ and only knows that the unknown + hidden message $y$ is the same in all contents. +\end{itemize} -%\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}$. +To the best of our knowledge, +KMA, KOA, and CMA have not already been studied +due to the lack of theoretical framework. +In the opposite, security of data hiding against WOA can be evaluated, +by using a probabilistic approach recalled below. -%\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. +\subsection{Stego-security}\label{sub:stegosecurity} +%\input{stegosecurity} +In the Simmons' prisoner problem~\cite{Simmons83}, Alice and Bob are in jail and +they want to, possibly, devise an escape plan by exchanging hidden messages in +innocent-looking cover contents. These messages are to be conveyed to one +another by a common warden named Eve, who eavesdrops all contents and can choose +to interrupt the communication if they appear to be stego-contents. +Stego-security, defined in this well-known context, is the highest security +class in Watermark-Only Attack setup, which occurs when Eve has only access to +several marked contents~\cite{Cayre2008}. -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. +Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of +$N_0$ initial host contents, and $p(Y|K)$ the probabilistic model of $N_0$ +marked contents s.t. each host content has been marked +with the same key $K$ and the same embedding function. -\begin{figure}[ht] -\centering -%\includegraphics[width=8.5cm]{organigramme2.pdf} -\includegraphics[width=8.5cm]{organigramme2.eps} -\caption{The dhCI dissimulation scheme} -\label{fig:organigramme} -\end{figure} +\begin{definition}[Stego-Security~\cite{Cayre2008}] +\label{Def:Stego-security} The embedding function is \emph{stego-secure} +if $\forall K \in \mathds{K}, p(Y|K)=p(X)$ is established. +\end{definition} + + + + + +%Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of +%$N_0$ initial host contents, and $p(Y|K)$ the probabilistic model of $N_0$ +%marked contents s.t. each host content has been marked +%with the same key $K$ and the same embedding function. + +%\begin{definition}[Stego-Security] +%\label{Def:Stego-security} The embedding function is \emph{stego-secure} +%if $\forall K \in \mathds{K}, p(Y|K)=p(X)$ is established. +%\end{definition} + Stego-security states that the knowledge of $K$ does not help to make the + difference between $p(X)$ and $p(Y)$. This definition implies the following + property: + $$p(Y|K_1)= \cdots = p(Y|K_{N_k})=p(Y)=p(X)$$ + This property is equivalent to a zero Kullback-Leibler divergence, which is the + accepted definition of the "perfect secrecy" in steganography~\cite{Cachin2004}. + + +\subsection{The negation mode is stego-secure} +To make this article self-contained, this section recalls theorems and proofs of stego-security for negation mode published in~\cite{gfb10:ip}. + +\begin{proposition} \emph{dhCI dissimulation} of Definition \ref{def:dhCI} with +negation mode and CIIS strategy-adapter is stego-secure, whereas it is not the +case when using CIDS strategy-adapter. +\end{proposition} + + +\begin{proof} On the one hand, let us suppose that $X \sim +\mathbf{U}\left(\mathbb{B}^n\right)$ when using \linebreak CIIS$(K,\_,\_,l)$. +We prove by a +mathematical induction that $\forall t \in \mathds{N}, X^t \sim +\mathbf{U}\left(\mathbb{B}^n\right)$. + +The base case is immediate, as $X^0 = X \sim +\mathbf{U}\left(\mathbb{B}^n\right)$. Let us now suppose that the statement $X^t +\sim \mathbf{U}\left(\mathbb{B}^n\right)$ holds until for some $t$. +Let $e \in +\mathbb{B}^n$ and \linebreak $\mathbf{B}_k=(0,\cdots,0,1,0,\cdots,0) \in +\mathbb{B}^n$ (the digit $1$ is in position $k$). + +So +$P\left(X^{t+1}=e\right)=\sum_{k=1}^n +P\left(X^t=e\oplus\mathbf{B}_k,S^t=k\right)$ where +$\oplus$ is again the bitwise exclusive or. +These two events are independent when +using CIIS strategy-adapter +(contrary to CIDS, CIIS is not built by using $X$), + thus: +$$P\left(X^{t+1}=e\right)=\sum_{k=1}^n +P\left(X^t=e\oplus\mathbf{B}_k\right) \times P\left(S^t=k\right).$$ + +According to the +inductive hypothesis: $P\left(X^{n+1}=e\right)=\frac{1}{2^n} \sum_{k=1}^n +P\left(S^t=k\right)$. The set of events $\left \{ S^t=k \right \}$ for $k \in +\llbracket 1;n \rrbracket$ is a partition of the universe of possible, so +$\sum_{k=1}^n P\left(S^t=k\right)=1$. Finally, +$P\left(X^{t+1}=e\right)=\frac{1}{2^n}$, which leads to $X^{t+1} \sim +\mathbf{U}\left(\mathbb{B}^n\right)$. This result is true for all $t \in +\mathds{N}$ and then for $t=l$. + +Since $P(Y|K)$ is $P(X^l)$ that is proven to be equal to $P(X)$, +we thus have established that, +$$\forall K \in [0;1], P(Y|K)=P(X^{l})=P(X).$$ +So dhCI dissimulation with CIIS +strategy-adapter is stego-secure. + +On the other hand, due to the definition of CIDS, we have \linebreak +$P(Y=(1,1,\cdots,1)|K)=0$. +%\JFC{Pourquoi? Justifier davantage là ou dans la def de CIDS} +So there is no uniform repartition for the stego-contents $Y|K$. +\end{proof} + + + +To sum up, Alice and Bob can counteract Eve's attacks in WOA setup, when using +dhCI dissimulation with CIIS strategy-adapter. To our best knowledge, this is +the second time an information hiding scheme has been proven to be stego-secure: +the former was the spread-spectrum technique in natural marking +configuration with $\eta$ parameter equal to 1 \cite{Cayre2008}. + + + + + +\subsection{A new class of $\varepsilon$-stego-secure schemes} + +Let us prove that, +\begin{theorem}\label{th:stego} +Let $\epsilon$ be positive, +$l$ be any size of LSCs, +$X \sim \mathbf{U}\left(\mathbb{B}^l\right)$, +$f_l$ be an image mode s.t. +$\Gamma(f_l)$ is strongly connected and +the Markov matrix associated to $f_l$ +is doubly stochastic. +In the instantiated \emph{dhCI dissimulation} algorithm +with any uniformly distributed (u.d.) strategy-adapter +that is independent from $X$, +there exists some positive natural number $q$ s.t. +$|p(X^q)- p(X)| < \epsilon$. +\end{theorem} + + +\begin{proof} +Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and +$\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value +of any binary number in $\Bool^{l}$. +The probability $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ for $e_j \in \Bool^{l}$ is thus equal to +$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$. +Let $i \in \llbracket 0, 2^l -1 \rrbracket$, +the probability $p(\textit{deci}(X^{t+1})= i)$ is +\[ + \sum\limits^{2^l-1}_{j=0} +\sum\limits^{l}_{k=1} +p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) +\] +\noindent +where $ i =_k j $ is true iff the binary representations of +$i$ and $j$ may only differ for the $k$-th element, +and where +$i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of +$i$. + +Next, due to the proposition's hypotheses on the strategy, +$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to +$\frac{1}{l}.p(\textit{deci}(X^t) = j , i =_k j, f_k(j) = i_k)$. +Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the +iterative process and thus does not depend on $X^t$, we have +\[ +\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} +\pi^t_j.\frac{1}{l} +\sum\limits^{l}_{k=1} +p(i =_k j, f_k(j) = i_k ). +\] + +Since +$\frac{1}{l} +\sum\limits^{l}_{k=1} +p(i =_k j, f_k(j) = i_k ) +$ is equal to $M_{ji}$ where $M$ is the Markov matrix associated to + $f_l$ we thus have +\[ +\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0} +\pi^t_j. M_{ji} \textrm{ and thus } +\pi^{t+1} = \pi^{t} M. +\] -Next section shows how to check whether a media contains a mark. +% The calculus of $p(X^{t+1} = e)$ is thus equal to +% $\pi^{t+1}_i$. + +First of all, +since the graph $\Gamma(f)$ is strongly connected, +then for all vertices $i$ and $j$, a path can +be found to reach $j$ from $i$ in at most $2^l$ steps. +There exists thus $k_{ij} \in \llbracket 1, 2^l \rrbracket$ s.t. +${M}_{ij}^{k_{ij}}>0$. +As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that +${M}_{ij}^{l\times k_{ij}}>0$, +we can conclude that, if +$k$ is the least common multiple of $\{k_{ij} \big/ i,j \in \llbracket 1, 2^l \rrbracket \}$ thus +$\forall i,j \in \llbracket 1, 2^l \rrbracket, {M}_{ij}^{k}>0$ and thus +$M$ is a regular stochastic matrix. + + +Let us now recall the following stochastic matrix theorem: +\begin{theorem}[Stochastic Matrix] + If $M$ is a regular stochastic matrix, then $M$ + has an unique stationary probability vector $\pi$. Moreover, + if $\pi^0$ is any initial probability vector and + $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$ + converges to $\pi$ as $t$ tends to infinity. +\end{theorem} + +Thanks to this theorem, $M$ +has an unique stationary probability vector $\pi$. +By hypothesis, since $M$ is doubly stochastic we have +$(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$ +and thus $\pi = (\frac{1}{2^l},\dots,\frac{1}{2^l})$. +Due to the matrix theorem, there exists some +$q$ s.t. +$|\pi^q- \pi| < \epsilon$ +and the proof is established. +Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure +provided the strategy-adapter is uniformly distributed. + \end{proof} + +This section has focused on security with regards to probabilistic behaviors. +Next section studies it in the perspective of topological ones. + + + +%\subsection{Security in KMA, KOA and CMA setups} +%\input{KMOA.tex} -- 2.39.5