tt

[HindawiJournalOfChaos.git] / IH / iihmsp10.tex

\section{Chaotic iterations versus Spread-spectrum: chaos and stego security~\cite{gfb10:ip}}
\label{sec:iihmsp10}
The first investigations in steganography since our thesis was published in
IIH-MSP'10, 6-th Int. Conf. on Intelligent Information Hiding and
Multimedia Signal Processing~\cite{gfb10:ip}, whose contribution is summarized in this section.


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

Information hiding has recently become a major digital technology~\cite{1411349,Xie09:BASecurity}, especially with the increasing importance and widespread distribution of digital media through the Internet.
Spread-spectrum data-hiding techniques have been widely studied in recent years
under the scope of security. These techniques encompass several schemes, such as 
Improved Spread Spectrum~(ISS), Circular Watermarking~(CW), and Natural 
Watermarking~(NW). Some of these schemes have revealed various 
security issues. On the contrary, it has
been proven in~\cite{Cayre2008} that the Natural Watermarking technique is 
stego-secure. This stego-security is one of the security classes defined 
in~\cite{Cayre2008}. In this paper, probabilistic models are used to 
categorize the security of data hiding algorithms in the Watermark Only 
Attack~(WOA) framework.

We have explained at the beginning of this manuscript
that any algorithm can be rewritten as an iterative
process, leading to the possibility to study its
topological behavior. As a concrete example, 
we have shown in~\cite{gfb10:ip} that the security level of these information hiding algorithms can be studied into a 
novel framework based on unpredictability, as it is understood in the 
theory of chaos~\cite{Devaney}. To do so and in the continuation of our thesis, a new class of security has been 
introduced in~\cite{gfb10:ip}, namely the topological security. This new class can be used to study 
some categories of attacks that are difficult to investigate in the existing 
security approach. It also enriches the variety of qualitative and quantitative 
tools that evaluate how strong the security is, thus reinforcing the confidence 
that can be added in a given scheme. 

In addition of being stego-secure, we have proven during our thesis and published later in~\cite{gfb10:ip} that 
Natural Watermarking technique is topologically secure. Moreover, this technique 
possesses additional properties of unpredictability, namely, strong transitivity,
topological mixing, and a constant of sensitivity equal to $\frac{N}{2}$.
However NW are not expansive, which is problematic in the Constant-Message 
Attack (CMA) and Known Message Attack (KMA) setups~\cite{GuyeuxThese10}. In this section, it is recalled  
by using the new topological security framework, that a more secure scheme than NW 
can be found to withstand attacks in these setups. This scheme, introduced in~\cite{guyeux10ter}, is 
based another time on the chaotic iterations. The aim of~\cite{gfb10:ip} was to 
prove that this algorithm is stego-secure and topologically secure, to study its
qualitative and quantitative properties of unpredictability, and then to compare
it with Natural Watermarking (the topological study was realized at the end of
our thesis while the stego-security has been proven later in~\cite{gfb10:ip}).







\subsection{Using chaotic iterations as information hiding schemes}
\label{sec:data-hiding-algo-chaotic iterations}

To explain how to use chaotic iterations for information hiding, we must firstly define the 
significance of a given coefficient. This definition, given in our thesis,
has been published later (in Secrypt'2011~\cite{fgb11:ip}).

\paragraph{Most and least significant coefficients}\label{sec:msc-lsc}



We first notice that terms of the original content $x$ that may be replaced by terms issued
from the watermark $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,
depending on its position $t$.

\begin{Def}%[Signification function]
A \emph{signification function} is a real sequence 
$(u^k)^{k \in \mathds{N}}$. % with a limit equal to 0.
\end{Def}


\begin{Ex}\label{Exemple LSC}
Let us consider a set of    
grayscale images stored into portable graymap format (P3-PGM):
each pixel ranges between 256 gray levels, \textit{i.e.},
is memorized with eight bits.
In that context, we consider 
$u^k = 8 - (k  \mod  8)$  to be the $k$-th term of a signification function 
$(u^k)^{k \in \mathds{N}}$. 
Intuitively, in each group of eight bits (\textit{i.e.}, for each pixel) 
the first bit has an importance equal to 8, whereas the last bit has an
importance equal to 1. This is compliant with the idea that
changing the first bit affects more the image than changing the last one.
\end{Ex}

\begin{Def}%[Significance of coefficients]
\label{def:msc,lsc}
Let $(u^k)^{k \in \mathds{N}}$ be a signification function, 
$m$ and $M$ be two reals s.t. $m < M$. 
\begin{itemize}
\item The \emph{most significant coefficients (MSCs)} of $x$ is the finite 
  vector  $$u_M = \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k 
    \geqslant M \textrm{ and }  k \le \mid x \mid \right);$$
 \item The \emph{least significant coefficients (LSCs)} of $x$ is the 
finite vector 
$$u_m = \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k 
  \le m \textrm{ and }  k \le \mid x \mid \right);$$
 \item The \emph{passive coefficients} of $x$ is the finite vector 
   $$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{itemize}
 \end{Def}

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.
These two definitions are illustrated on Figure~\ref{fig:MSCLSC},
 where the significance function $(u^k)$ is defined as in Example \ref{Exemple LSC}, $M=5$, and $m=6$.



\begin{figure}[htb]


\begin{minipage}[b]{.98\linewidth}
  \centering
  \centerline{\includegraphics[width=3.cm]{IH/img/lena512}}
  \centerline{(a) Lena.}
\end{minipage}
\begin{minipage}[b]{.49\linewidth}
  \centering
    \centerline{\includegraphics[width=3.cm]{IH/img/lena_msb_678}}
  \centerline{(b) MSCs of Lena.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.49\linewidth}
  \centering
    \centerline{\includegraphics[width=3.cm]{IH/img/lena_lsb_1234_facteur17}}
  
 %\centerline{\epsfig{figure=img/lena_lsb_1234_facteur17.pdf,width=4cm}}
  \centerline{(c) LSCs of Lena ($\times 17$).}
\end{minipage}
%
\caption{Most and least significant coefficients of Lena.}
\label{fig:MSCLSC}
%
\end{figure}





\subsubsection{Presentation of the $\mathcal{CIW}_1$ dhCI scheme}

We have proposed in SECRYPT10~\cite{guyeux10ter} to use chaotic iterations as an information hiding scheme.
It has been called dhCI (for data hiding based on chaotic 
iterations) in our thesis, but it is denoted as
$\mathcal{CIW}_1$ in later publications. 
It operates as follows (see Figure~\ref{fig:DWT}). Let:


\begin{itemize}
  \item $(K,N) \in [0;1]\times \mathds{N}$ be an embedding key,
  \item $X \in \mathbb{B}^\mathsf{N}$ be the $\mathsf{N}$ least significant coefficients (LSCs) of a given cover media $C$,
  \item $(S^n)_{n \in \mathds{N}} \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$ be a strategy, which depends on the message to hide $M \in [0;1]$ and $K$, 
  \item $f_0 : \mathbb{B}^\mathsf{N} \rightarrow \mathbb{B}^\mathsf{N}$ be the vectorial logical negation.
\end{itemize}



\begin{figure}[h!]
\centering
\subfigure[Original Lena.]{\includegraphics[scale=0.3]{IH/Medias/lena512}}\hspace{1cm}\subfigure[Watermarked Lena.]{\includegraphics[scale=0.3]{IH/Medias/lena512marqueDWT}}
\caption{Data hiding with chaotic iterations}
\label{fig:DWT}
\end{figure}


So the watermarked media is $C$ whose LSCs are replaced by $Y_K=X^{N}$, where:

\begin{equation*}
\left\{
 \begin{array}{l}
X^0 = X\\
\forall n < N, X^{n+1} = G_{f_0}\left(X^n\right).\\
\end{array} \right.
\end{equation*}

In the following section, two ways to generate $(S^n)_{n \in \mathds{N}}$ are given, namely
Chaotic Iterations with Independent Strategy~(CIIS) and Chaotic Iterations with Dependent
Strategy~(CIDS). In CIIS, the strategy is independent from the cover media $X$,
whereas in CIDS the strategy will be dependent on $X$. These 
strategies have been introduced in~\cite{gfb10:ip}. Their stego-security are studied in Section~\ref{sec:chaotic iterations-security-level} and their topological security in Section~\ref{sec:topological security-evaluation}.






\subsubsection{Examples of strategies}
\label{sec:ciis-cids-example}
\paragraph{CIIS strategy}

Let us first introduce the Piecewise Linear Chaotic Map~(PLCM, see~\cite{Shujun1}), defined by:

\begin{Def}[PLCM]\label{Def:PLCM}
\begin{equation*}
F(x,p)=\left\{
 \begin{array}{ccc}
x/p & \text{if} & x \in [0;p] \\
(x-p)/(\frac{1}{2} - p) & \text{if} & x \in \left[ p; \frac{1}{2} \right]
\\
F(1-x,p) & \text{else.} & \\
\end{array} \right.
\end{equation*}
\end{Def}


\noindent where $p \in \left] 0; \frac{1}{2} \right[$ is a ``control parameter''. Contrary to well-known chaotic maps like the logistic
map, this PLCM is unbiased and does not present obvious security
flaws~\cite{Shujun1}.

We define the general term of the strategy $(S^n)_n$ in CIIS setup by
the following expression: $S^n = \left \lfloor \mathsf{N} \times K^n \right \rfloor +
1$, where:

\begin{equation*}\label{eq:PLCM-for-strategy}
\left\{
 \begin{array}{l}
p \in \left[ 0 ; \frac{1}{2} \right] \\
K^0 = M \otimes K\\
K^{n+1} = F(K^n,p), \forall n \leq N_0\\ \end{array} \right.
\end{equation*}



\noindent in which $\otimes$ denotes the bitwise exclusive or (XOR) between two floating part numbers (\emph{i.e.}, between their binary digits representation). Lastly, to be certain to enter into the chaotic regime of PLCM~\cite{Shujun1}, the strategy can be preferably defined by: $S^n = \left \lfloor \mathsf{N} \times K^{n+D} \right \rfloor + 1$, where $D \in \mathds{N}$. 




\paragraph{CIDS strategy}\label{sec:cids-example}
The same notations as above are used.
We define CIDS strategy as in~\cite{gfb10:ip}: $\forall k \leqslant N$,  
\begin{itemize}
\item if $k \leqslant \mathsf{N}$ and $X^k = 1$, then $S^k=k$,
\item else $S^k=1$.
\end{itemize}
In this situation, if $N \geqslant \mathsf{N}$, then only two watermarked contents are possible with the scheme proposed in Section~\ref{sec:data-hiding-algo-chaotic iterations}, namely: $Y_K=(0,0,\cdots,0)$ and $Y_K=(1,0,\cdots,0)$.


\subsection{Security versus robustness}\label{sec:chaotic iterations-security-level}


\subsubsection{Presentation}

Even if security and robustness are neighboring concepts without clearly
established definitions~\cite{Perez-Freire06}, robustness is often considered
to be mostly concerned with blind elementary attacks, whereas security is not
limited to certain specific attacks. Indeed, security encompasses robustness
and intentional attacks~\cite{Kalker2001,ComesanaPP05bis}. The best attempt to
give an elegant and concise definition for each of these two terms was
proposed in \cite{Kalker2001}. Following Kalker, we will consider in this
research work the two following definitions:  

\begin{Def}[Security~\cite{Kalker2001}]\label{def:security}
Watermarking security refers to the
inability by unauthorized users to have access to the raw watermarking channel
[...] to remove, detect and estimate, write or modify the raw watermarking
bits.
\end{Def}

\begin{Def}[Robustness~\cite{Kalker2001}]\label{def:robustness}
Robust watermarking is a mechanism to create a communication channel that is
multiplexed into original content [...] It is required that, firstly, the
perceptual degradation of the marked content [...] is minimal and, secondly,
that the capacity of the watermark channel degrades as a smooth function of the
degradation of the marked content. 
\end{Def}


\subsubsection{Classification of attacks}
\label{sec:attack-classes}

In the steganography framework, attacks have been classified
in~\cite{Cayre2008} as follows.


\begin{Def}
Watermark-Only Attack (WOA) occurs when an attacker has only access to several watermarked contents.
\end{Def}

\begin{Def}
Known-Message Attack (KMA) occurs when an attacker has access to several pairs of watermarked contents and
corresponding hidden messages.
\end{Def}

\begin{Def}
Known-Original Attack (KOA) is when an attacker has access to several pairs of watermarked contents and
their corresponding original versions.
\end{Def}

\begin{Def}
Constant-Message Attack (CMA) occurs when the attacker observes several watermarked contents and only knows that the
unknown hidden message is the same in all contents.
\end{Def}


A synthesis of this classification is given in
Table~\ref{table:attack-classification}.
\begin{table}[h]
\begin{center}

 \begin{tabular}{|c||c|c|c|}
  \hline
   \textbf{Class} &  \textbf{Original content} &  \textbf{Stego content} & 
   \textbf{Hidden message}\\
    \hline 
    \hline 
 \textbf{WOA} &   &    $\times$ & \\
  \hline
 \textbf{KMA}  & & $\times$ & $\times$ \\
  \hline
 \textbf{KOA} & $\times$ & $\times$ & \\
 \hline
 \textbf{CMA} & & & $\times$ \\
  \hline 
  \end{tabular}
  \caption{Watermarking attacks classification in context of~\cite{Kalker2001}}
  \label{table:attack-classification}
  \end{center}
  \end{table}



\subsubsection{Definition of stego-security}\label{sec:stego-security-definition}
\r
\r
In the Simmons' prisoner problem~\cite{Simmons83}, Alice and Bob are in jail and\r
they want to,  possibly, devise an escape plan by  exchanging hidden messages in\r
innocent-looking  cover contents.  These  messages  are to  be  conveyed to  one\r
another by a common warden named Eve, who eavesdrops all contents and can choose\r
to interrupt the communication if they appear to be stego-contents.\r
\r
Stego-security,  defined in  this well-known  context, is  the  highest security\r
class in Watermark-Only  Attack setup, which occurs when Eve  has only access to\r
several marked contents~\cite{Cayre2008}.\r
\r
\r
Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of\r
$N_0$ initial  host contents,  and $p(Y|K)$ the  probabilistic model  of $N_0$\r
marked contents s.t. each host  content has  been marked\r
with the same key $K$ and the same embedding function.\r
\r
\begin{Def}[Stego-Security~\cite{Cayre2008}]\r
\label{Def:Stego-security}  The embedding  function  is \emph{stego-secure}\r
if  $\forall K \in \mathds{K}, p(Y|K)=p(X)$ is established.\r
\end{Def}\r
\r
\r
\r
 Stego-security  states that  the knowledge  of  $K$ does  not help  to make  the\r
 difference  between $p(X)$ and  $p(Y)$.  This  definition implies  the following\r
 property:\r
 $$p(Y|K_1)= \cdots = p(Y|K_{N_k})=p(Y)=p(X)$$ \r
 This property is equivalent to  a zero Kullback-Leibler divergence, which is the\r
 accepted definition of the "perfect secrecy" in steganography~\cite{Cachin2004}.\r
\r


\subsection{Security evaluation}


\subsubsection{Evaluation of the stego-security}
\label{sec:stego-security-proof}

We have proven in~\cite{gfb10:ip} the following proposition. 

\begin{Prop}
CIIS are stego-secure, while CIDS do not satisfy this security property.
\end{Prop}

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



\subsubsection{Evaluation of the topological security}
\label{sec:topological security-evaluation}

To check whether an information hiding scheme $S$ is topologically secure or not, we have proposed in our thesis, and published later
in~\cite{gfb10:ip}, to write
$S$ as an iterate process $x^{n+1}=f(x^n)$ on a metric space $(\mathcal{X},d)$. As recalled in the first 
chapter of this manuscript, this formulation is always possible. So,

\begin{Def}%[topological security]
\label{Def:topological security-definition}
An information hiding scheme $S$ is said to be topologically secure on
$(\mathcal{X},d)$ if its iterative process has a chaotic
behavior according to Devaney.
\end{Def}



Due to the chaos properties of the so-called chaotic iterations, 
we have then deduced in~\cite{gfb10:ip} that,

\begin{Prop}
CIIS and CIDS are topologically secure.
\end{Prop}

We have then deduced qualitative and quantitative
properties of topological security for this information
hiding scheme in~\cite{gfb10:ip}: it is expansive (with a constant of 
expansiveness equal to 1), topologically mixing,
etc. These properties can measure the
disorder generated by our scheme, giving by doing so an important information about the
unpredictability level of such a process, which helps to compare it
to other data hiding methods. Such a comparison is outlined in 
the next section~\cite{gfb10:ip}.



\subsection{Comparison between spread-spectrum and chaotic
iterations}\label{sec:comparison-application-context}

The consequences of topological mixing for data hiding are multiple. Firstly, 
security can be largely improved by considering
the number of iterations as a secret key. An attacker
will reach all of the possible media when iterating without this key.
Additionally, he cannot benefit from a KOA setup, by studying media in the
neighborhood of the original cover. Moreover, as in a topological mixing
situation, it is possible that any hidden message (the initial condition), is
sent to the same fixed watermarked content (with different numbers of
iterations), the interest to be in a KMA setup is drastically reduced. Lastly, as
all of the watermarked contents are possible for a given hidden message, depending
on the number of iterations, CMA attacks will fail.



The property of expansiveness reinforces drastically the sensitivity in the aims of reducing the benefits that Eve can obtain from an attack in KMA or KOA setup. For example, it is impossible to have an estimation of the watermark by moving the message (or the cover) as a cursor in situation of expansiveness: this cursor will be too much sensitive and the changes will be too important to be useful. 
On the contrary, a very large constant of expansiveness $\varepsilon$ is unsuitable: the cover media will be strongly altered whereas the watermark would be undetectable. 
Finally, spread-spectrum is relevant when a discrete and secure data hiding technique is required in WOA setup. However, this technique should not be used in KOA and KMA setup, due to its lack of expansiveness.