tt

[HindawiJournalOfChaos.git] / IH / ciw1.tex

\section{The $\mathcal{CIW}_1$  Chaotic Iteration based Watermarking Process}
\label{sec:ciw1}
\subsection{Using chaotic iterations as information hiding schemes}
\label{sec:data-hiding-algo-chaotic iterations}

\subsubsection{Presentation of the dhCI process}

We have proposed in~\cite{gfb10:ip,bcg11b:ip} a data hiding protocol based 
on chaotic iterations. The process, referred as dhCI, consisted in
iterating $\mathcal{G}_{f_0}$ on least significant coefficients of a cover medium.
Each property exhibited by \r
the dynamical system will then be possessed too by the watermarking scheme.\r
\r


The same original image was supposed to be shared by the sender and 
the receiver, the sender either iterates or not CIs on these coefficients,
depending on whether the binary information to transfer was 0 or 1, while
the receiver computed the differences between its stored image and the 
received one. 
For further explanations, see~\cite{gfb10:ip,bcg11b:ip}. 

The first deepened study of such a dhCI algorithm was published
in~\cite{guyeux10ter}. The aims were to 
prove that a particular instance of the dhCI algorithm, called the
$\mathcal{CIW}_1$  process,  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 has been realized in~\cite{Guyeux2012}
 while the stego-security has been proven later in~\cite{gfb10:ip}).
To be able to recall the $\mathcal{CIW}_1$ scheme, we must firstly define the 
significance of a given coefficient. 


\subsubsection{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 taken
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]{.32\linewidth}
  \centering
  \centerline{\includegraphics[width=3.75cm]{IH/img/lena512}}
  \centerline{(a) Lena.}
\end{minipage}
\begin{minipage}[b]{.32\linewidth}
  \centering
    \centerline{\includegraphics[width=3.75cm]{IH/img/lena_msb_678}}
  \centerline{(b) MSCs of Lena.}
\end{minipage}
\hfill
\begin{minipage}[b]{0.32\linewidth}
  \centering
    \centerline{\includegraphics[width=3.75cm]{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}
\label{trucMachin}
We have proposed in SECRYPT10~\cite{guyeux10ter} to 
study a particular instance of the dhCI class, which
considers the negation function as iteration mode.
The resulting chaotic iterations watermarking\footnote{Watermarking means here that only a binary information, like the presence of a copyright, can be extracted.} process has been denoted by
$\mathcal{CIW}_1$ in this publication. 
It operates as follows. 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[width=4cm]{IH/Medias/lena512}}\hspace{0.5cm}
\subfigure[Watermark.]{\label{invad}\includegraphics[width=1cm]{IH/iihmsp13/exp/invader}}\hspace{0.5cm}
\subfigure[Watermarked Lena.]{\includegraphics[width=4cm]{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}$ is large enough. 




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

Before being able to present the security study we performed on it, we must firstly recall the notion of security usually considered
in information hiding and its difference with robustness.

\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
article the two following definitions:  

\begin{Def}[Security~\cite{Kalker2001}]\label{def:security}
Watermarking security
% \footnote{Remark that when robustness is required in information hiding, the community tends to 
% speak about digital watermarking, while researchers prefer to say
% steganography when security is regarded. Similarly, some authors 
% speak about watermarking when the hidden information is only one bit,
% while steganography is for larger messages, even if such use of 
% the terminologies is less common. Such ambiguities come from the fact
% that no clear common definitions of steganography and digital watermarking have been accepted by the whole community, and that 
% this community is indeed split in various subcommunities that do not
% communicate together. So, in this 
% manuscript, security will always refer to mathematical proofs while
% robustness will be related to brute-force attacks. Steganography,
% watermarking, as well as steganalysis will however be used with various
% significations that can be deduced from the context.}  
 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 security 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 such that 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 is stego-secure, while CIDS does not satisfy this security property.
\end{Prop}



\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~\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 previously, 
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.




\subsection{Lyapunov exponent evaluation}%~\cite{bfg12:ip}}

The Lyapunov exponent of the 
$\mathcal{CIW}_1$ algorithm has been computed in~\cite{bfg12:ip},
to improve our knowledge of its topological security. It is equal
to $\ln{\mathsf{N}}$, where $\mathsf{N}$ stands for the number of
LSCs chosen in the implementation of the algorithm.

To evaluate this Lyapunov exponent,\r
 chaotic iterations must be described by a differentiable function on $\mathds{R}$. 
To do so, \r
a topological semiconjugacy between the phase space $\mathcal{X}$ and\r
$\mathds{R}$ has been written.
As this proof is simply a rewriting in the digital watermarking field
of an unpublished result on chaotic iterations obtained in~\cite{Guyeux2012}, and as Section~\ref{sec:lyapCIS2} provides a Lyapunov exponent 
evaluation for a completely different algorithm,
we will not say any more about this publication.


\r