tt

[HindawiJournalOfChaos.git] / IH / iihmsp11.tex

\section{Steganography: a Class of Algorithms having Secure Properties~\cite{bcg11b:ip}}


This section summarizes~\cite{bcg11b:ip}, in which
 a new class of non-blind information hiding
algorithms based on chaotic iterations has been proposed, and
its stego-security and topological security has been proven.  

\subsection{Introduction}\label{sec:intro}

The work~\cite{bcg11b:ip} focuses on non-blind  binary information hiding scheme: 
the  original host  is  required  to  extract the  binary hidden
information. This  context is indeed not
as restrictive as it could primarily appear.
Firstly, it allows to prove 
the authenticity of a document sent  through the  Internet 
(the original document is stored whereas the stego content is sent). 
Secondly, Alice and Bob can establish an hidden channel into a
streaming video 
(Alice and Bob both have the same movie, and  Alice hide information into 
the frame number $k$  iff the binary digit
number $k$ of its hidden message is  1).
Thirdly, based on a similar idea, a same
given image can be marked  several times by using various secret parameters
owned both by Alice and Bob. Thus more than one bit can be embedded into a given
image  by using  dhCI  dissimulation. Lastly,  non-blind watermarking  is
useful in  network's anonymity and intrusion  detection \cite{Houmansadr09}, and
to protect digital data sending through the Internet \cite{P1150442004}.

Before~\cite{bcg11b:ip},  stego-security~\cite{Cayre2008} and topological security 
were only proven 
on the spread spectrum watermarking~\cite{Cox97securespread,HuangFang},
and on the dhCI algorithm, which is notably based on iterating  
the negation function (see Section~\ref{sec:iihmsp10}).
We argued in~\cite{bcg11b:ip} that other functions can provide algorithms as secure as the dhCI one.
This work has then generalized the algorithm recalled in Section~\ref{sec:iihmsp10} and formalized all
its stages. Due to this formalization, it has then been possible to adress the proofs of the two
security properties for a large class of steganography approaches in~\cite{bcg11b:ip}.  





\subsection{Formalization of Steganographic Methods}
\label{sec:formalization}


The data hiding scheme presented in previous works does not constrain media to have 
a constant size. It is indeed sufficient to provide a function and a strategy 
that may be  parametrized with the size of the elements to modify. 
Parametrized strategies have already been introduced in a previous 
section, leading to the notion of \emph{strategy-adapter}. 
The \emph{mode} notion defined below achieves the same goal
but for the iteration function~\cite{bcg11b:ip} (until now, only the negation function
has been regarded).  

\begin{Def}[Mode]
\label{def:mode}
A map $f$, which associates to any $n \in \mathds{N}$ an application 
$f_n : \mathds{B}^n \rightarrow \mathds{B}^n$, is called a \emph{mode}.
\end{Def}

For instance, the \emph{negation mode} is defined by the map that
assigns to every integer $n \in \mathds{N}^*$ the function 
${\neg}_n:\mathds{B}^n \to \mathds{B}^n, 
{\neg}_n(x_1, \hdots, x_n) \mapsto (\overline{x_1}, \hdots, \overline{x_n})$.


We now use the previously introduced \emph{signification function} 
to attach a weight to each term defining a digital media,
w.r.t. its position $t$, leading to the following notion of
a decomposition function~\cite{bcg11b:ip}.



\begin{Def}[Decomposition function]
Let $(u^k)^{k \in \mathds{N}}$ 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 \mathds{N}}$.
\end{Def} 


\begin{Def}[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)_{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{Def}

The embedding consists in 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~\cite{bcg11b:ip}:


\begin{Def}[Embedding 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 image of $(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
by  the recomposition function $\textit{rec}$.
\end{Def}

We have thus been able in~\cite{bcg11b:ip} to reformulate the \emph{dhCI} information hiding scheme, as follows:

\begin{Def}[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)$,
$q$ be a positive natural number,  
and $y$ be a digital media of size $l=|u_m|$.


The \emph{dhCI dissimulation}  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}:\mathds{B}^{l} \rightarrow \mathds{B}^{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 ^{\mathds{N}}$.

\item We iterate $G_{f_l}$ with initial configuration $(S_y,\phi_{m})$.
\item $\hat{y}$  is the $q$-th term.
\end{itemize}
\end{Def}


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{figure}[h!]
\centering
\includegraphics[width=10cm]{IH/organigramme22.pdf}
\caption{The dhCI dissimulation scheme}
\label{fig:organigramme}
\end{figure}


We are then left to show how to formally check
whether a given digital media $z$ 
results from the dissimulation of $y$ into the digital media $x$~\cite{bcg11b:ip}. 

\begin{Def}[Marked content]
Let $\textit{dec}(u,m,M)$ be a decomposition function,
$f$ be a mode, 
$\mathcal{S}$ be a strategy adapter, 
$q$ be a positive natural number,  
and  
$y$ be a digital media, 
\linebreak $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ be the 
image by $\textit{dec}(u,m,M)$  of  a digital media $x$. 

Then $z$ is \emph{marked} with $y$ if
the image by $\textit{dec}(u,m,M)$ of $z$ is 
$(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$ where 
$\hat{y}$ is the right member of $G_{f_l}^q(S_y,\phi_{m})$.
\end{Def}


Various decision strategies are obviously  possible to determine whether a given
image $z$ is  marked or not, depending  on the eventuality
that the considered image may have  been attacked.
For example, a  similarity percentage between $x$
and  $z$ can  be  computed, and  the result  can  be compared  to a  given
threshold. Other  possibilities are the use of  ROC curves or
the definition of a null hypothesis problem.
The next section, always extracted from~\cite{bcg11b:ip}, 
recalls some security properties and shows how the 
\emph{dhCI dissimulation} algorithm verifies them.





\subsection{Security Analysis}\label{sec:security}


We have proven in~\cite{bcg11b:ip}, using the stochastic matrix theorem, that,

\begin{Th}\label{th:stego}
Let $\epsilon$ be positive,
$l$ be any size of LSCs, 
$X   \sim \mathcal{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 
which is independent from $X$,  
there exists some positive natural number $q$ s.t.
$|p(X^q)- p(X)| < \epsilon$. 
\end{Th}


\begin{Pre}   
See~\cite{bcg11b:ip}.
 \end{Pre}

Since $p(Y| K)$ is $p(X^q)$ the method is then stego-secure.
We have then focused on topological security properties, and have deduced
from the characterisation recalled in Theorem~\ref{Th:Caracterisation des  IC chaotiques} that,

\begin{Prop}
Functions $f  : \mathds{B}^{n} \to
\mathds{B}^{n}$ such that the graph $\Gamma(f)$ is strongly connected lead to topologically secure 
\emph{dhCI dissimulation} algorithms.
\end{Prop}




%\subsection{Instantiation of  Steganographic Methods}
\label{instantiating}

Theorem~\ref{th:stego} relies on a u.d.   
strategy-adapter that is independent from the cover, and on an image mode 
$f_l$ whose iteration graph  $\Gamma(f_l)$ is strongly
connected and whose  Markov matrix 
is doubly stochastic. 
We have shown in~\cite{bcg11b:ip} that the CIIS strategy 
adapter~\cite{gfb10:ip} has the required 
properties and have mentioned that \cite{wcbg11:ip} has presented an iterative approach 
(which has been recalled in Section~\ref{sec:prac})
to 
generate image modes $f_l$ such that  
$\Gamma(f_l)$ is strongly connected.
Among these maps, it is obvious to check which verifies or not
the doubly stochastic constrain. 

% 
% \subsection{Conclusion}\label{sec:concl}
% 
% This work has presented a new class of information hiding
% algorithms which generalizes 
% algorithm~\cite{gfb10:ip} reduced to the negation mode.
% Its complete formalization has allowed to prove the stego-security 
% and topological security properties.
% As far as we know, this is the first time a whole class of algorithm 
% has been proven to have these two properties. 
% 
% In future work, our intention is to study the robustness of this class of 
% dhCI dissimulation schemes.
% We are to find the optimized parameters (modes, stretegy adapters, signification coefficients, iterations numbers\ldots) giving 
% the strongest robustness 
% (depending on the chosen representation domain), theoretically and practically
% by realizing comprehensive simulations.
% Finally these algorithms will be compared to other existing ones, among other
% things by regarding whether these algorithms are chaotic or not.