tt

[HindawiJournalOfChaos.git] / IH / iihmsp13 / ci2.tex

% It first synthesizes notations (Sec.~\ref{sec:ci2:notations}), and the scheme is 
% next formally presented as an iterative process (Sec.~\ref{sub:ci2:scheme}).
% %A discussion (Sec.~\ref{sub:ci2:discussion}) 
% %on the correctness and completeness of this algorithm follows these sections.
% Finally, the last part shows how to decide whether an host image is watermarked or not. 




\subsection{Notations used for \CID}\label{sec:ci2:notations}




\begin{itemize}
\item $x^0 \in \mathbb{B}^\mathsf{N}$ is vector of the $\mathsf{N}$ 
  selected bits of a given host
  media where the watermark will be embedded.
  It is expressed as a vector of $\mathsf{N}$ Boolean values.
  In this work and in experimentations,  $x^0$ is defined as 
  the LSBs of the host. 

  \item $m^0 \in \mathbb{B}^\mathsf{P}$ is the watermark message to embed into $x^0$. 
    This is a  vector of $\mathsf{P}$ Boolean values.
  \item $S_p \in \mathbb{S}_\mathsf{N}$ is a strategy called \textbf{place strategy}. Intuitively, this sequence
    defines which element of $x$ is modified at each iteration. 
  \item $S_c \in \mathbb{S}_\mathsf{P}$ is a strategy called \textbf{choice strategy}. It
    defines which element of the watermark is embedded at each iteration.  
  \item Lastly, $S_m \in \mathbb{S}_\mathsf{P}$ is a strategy called \textbf{mixing strategy}. This sequence gives which element of the watermark is switched at each iteration.  
\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}


With this material and for all 
$(n,i,j)$ in 
$\mathds{N}^{\ast} \times \llbracket 0;\mathsf{N}-1\rrbracket \times \llbracket
0;\mathsf{P}-1\rrbracket$,
the $\CID$ algorithm is defined by:

\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{definition}
\noindent where $\overline{m_j^{n-1}}$ is the Boolean negation of $m_j^{n-1}$.
% It can be also remarked that simple are realized on the vector $m$ with the
% strategy $S_m$ as explained in Section~\ref{sec:chaotic iterations}. 
The stego-content is the Boolean vector $y = x^l \in \mathbb{B}^{\mathsf{N}}$ provided the following constraints are applied:

 
\begin{enumerate}
\item The number $l$ of iterations is sufficiently large (see details
below).
\item \label{itm2:Sc} Let  $\Im(S_p)$ be the set 
  $ \{S^1_p, S^2_p, \ldots,  S^l_p\}$ of cardinality $k$, $k \leq l$  (repetitions are removed in a
set).  
  This set contains all the elements of $x$ that have been modified 
  along the iteration process.
  Let us consider $\Im(S_c)_{|D}$ defined by 
  $\{S^{d_1}_c, S^{d_2}_c, \ldots,  S^{d_k}_c\}$
  where 
  $d_i$ is the last iteration that has modified the element $i \in \Im(S_p)$.   
  We require that this set is equal
  to $\llbracket 0 ;\mathsf{P} -1 \rrbracket$.
\end{enumerate}



Let us discuss the constraints given above.
The first one implies that the number of iterations is greater than a 
given threshold. This requirement has both practical and theoretical reasons.
Theoretically speaking, the ability to 
successfully pass statistical tests is
directly linked to this number of iterations.
And, in practice, this value is bounded 
by the size of the host content.
%\CG{Parler d'entropie, d'exposant de Lyapounov pour ce nombre d'itérations}
%\JFC{en deduire une borne suffisante pour itérer. Pratiquement j'ai fais 
%4 fois la taille du support}.
The second constrain, for its part, addresses the method's completeness and correctness, as detailed below. 

\subsection{Correctness and Completeness Studies}\label{sub:ci2:discussion}


Without attack, the scheme has to ensure that the user can always extract a 
message and that this latter is the watermark, provided the user has the 
correct keys. These two demands 
correspond respectively to the study
of completeness and of correctness
for the proposed approach. 
To achieve this study, let us firstly prove the following assessment.


\begin{proposition}
In section~\ref{sub:ci2:scheme}, item  \ref{itm2:Sc}
is a  necessary and sufficient condition
to allow message to be extracted 
from the host.
\end{proposition}
\begin{proof}
For sufficiency, let $d_i$ be the last iteration (date) the element $i \in \Im(S_p)$
of $x$ has been modified:% is defined by 
$$
d_i = \max\{j | S^j_p = i \}.
$$ 
Let $D=\{d_i|i \in \Im(S_p) \}$.
The set $\Im(S_c)_{|D}$ is thus 
the restriction of  the image of $S_c$ to $D$.


The host that results from this iteration scheme is thus
$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ where 
$x^l_i$ is either $x^{d_i}_i$ if $i$ belongs to $\Im(S_p)$ or $x^0_i$ otherwise.
Moreover, for each $i \in \Im(S_p)$, the element $x^{d_i}_i$ is equal to 
$m^{d_i-1}_{S^{d_i}_c}$. 
Thanks to constraint \ref{itm2:Sc}, all the indexes 
$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ belong to 
$\Im(S_c)_{|D}$.
Let then $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ s.t.
$S^{d_i}_c=j$. 
Thus we have all the elements $m^._j$ of the vector $m$.
Let us focus now on some  $m^{d_i-1}_j$.
Thus the value of $m^0_j$ can be  immediately
deduced by counting in $S_c$ how many
times the component $j$ has been switched 
before $d_i-1$.  

Let us focus now on necessity. 
If $\Im(S_c)_{|D} \subsetneq 
\llbracket 0 ;\mathsf{P} -1 \rrbracket$,
there exist some $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ that 
do not belong to $\Im(S_c)_{|\Im(S_p)}$. 
Thus $m_j$ is  not present in $x^l$ and the message cannot be extracted.
\end{proof}

When the constraint \ref{itm2:Sc} is satisfied, we obtain a scheme
that always finds the original message provided the watermarked media 
has not been modified. 
In that context, correctness and completeness are established. 


Thanks to constraint~\ref{itm2:Sc}, the cardinality $k$ of
$\Im(S_p)$ is larger than $\mathsf{P}$. 
Otherwise the cardinality of $D$  would be smaller than $\mathsf{P}$ 
and similar to the cardinality of $\Im(S_c)_{|D}$,
which is contradictory.

One bit of index $j$ of the original message $m^0$
is thus embedded at least twice in $x^l$. 
By counting the number of times this bit has been switched in $S_m$, the value of 
$m_j$ can be deduced in many places. 
Without attack, all these values are equal and the message is immediately 
obtained.
 After an attack,  the value of $m_j$ is obtained as mean value of all 
its occurrences. 
The scheme is thus complete.
Notice that if the cover is not attacked, the returned message is always equal to the original 
due to the definition of the mean function.


\subsection{Deciding whether a Media is Watermarked}\label{sub:ci2:distances}

Let us consider  a media $y$ that is watermarked with a message $m$. 
Let us consider  $y'$ that is an altered version of $y$, \textit{i.e.}, where 
some bits have been modified.
Let $m'$ be the message that is extracted from $y'$. 

Let us now check how  far the extracted message $m'$ is from $m$.
To achieve this, let us consider 
$M = \{ i | m_i = 1 \}$ of the Boolean vector message $m$ and similarly 
the set $M'$ for the message $m'$. 
Most of similarity measures %, e.g.~\cite{yule1950introduction}  %,Anderberg-Cluster-1973,Rifqi:2000:DPM:342947.342970},
depend on the functions $a$, $b$, $c$, and
$d$, all from 
$\mathbb{B}^{\mathsf{P}}  \times \mathbb{B}^{\mathsf{P}}$ to $\mathbb{N}$,
and respectively equal to
$a(m,m') = |M \cap M' |$, 
$b(m,m') = |M \setminus M' |$,
$c(m,m') = |M' \setminus M|$, and
$d(m,m') = |\overline{M} \cap \overline{M'}|$
($|S|$ and $\overline{S}$ respectively 
denote  the cardinality 
and the complementary 
of any set $S$).
In what follows $a$, $b$, $c$, and $d$ respectively stand for 
$a(m,m')$, $b(m,m')$, $c(m,m')$, and $d(m,m')$.

According 
to~\cite{rifq/others03} %,DBLP:conf/ipmu/LesotR10} 
the Fermi-Dirac measure $S_{\textit{FD}}$
is the one that has higher discrimination power, \textit{i.e.}, 
which  allows a clear separation between correlated vectors and 
uncorrelated ones. 
The measure is recalled hereafter with
respect to the previously defined scalars $a$, $b$, and $c$.

\begin{eqnarray*}
S_{\textit{FD}}(\varphi) &= &
\dfrac{F_{\textit{FD}}(\varphi) -F_{\textit{FD}}(\frac{\pi}{2})}
{F_{\textit{FD}}(0) -F_{\textit{FD}}(\frac{\pi}{2})},\\
F_{\textit{FD}}(\varphi) &= &
\dfrac{1}{1+\exp(\dfrac{\varphi - \varphi_0}{\gamma})},\\
%\varphi &= &\arctan(\dfrac{b+c}{a})
\end{eqnarray*}
\noindent where $\varphi = \arctan(\dfrac{b+c}{a})$, $\varphi_0$ is $\pi/4$, and $\gamma$ is 0.1.

The distance between $m$ and $m'$ is then computed as 
$1-S_{\textit{FD}}(m,m')$ and is thus a real number in $[0;1]$.
If such a distance is behind a threshold, $y'$ will be
declared as watermarked and not watermarked otherwise.
Next section presents a practical evaluation of this approach.