abstract, conclusion

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

\subsection{Chaotic Iterations}
\label{sec:chaotic-iterations}

In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and
$V_{i}$ is for the $i^{th}$ component of a vector $V$. Finally, the following notation
is used: $\llbracket0;N\rrbracket=\{0,1,\hdots,N\}$.\newline

Let us consider a \emph{system} of a finite number $\mathsf{N}$ of elements (or
\emph{cells}), so that each cell has a boolean \emph{state}. A sequence of length
$\mathsf{N}$ of boolean states of the cells corresponds to a particular
\emph{state of the system}. A sequence that elements belong into $\llbracket
0;\mathsf{N-1} \rrbracket $, \emph{i.e.}, an element of $\llbracket 0; \mathsf{N-1}\rrbracket^\mathds{N}$, is called a \emph{strategy}. The set of all
strategies is denoted by $\mathbb{S}.$

\begin{definition}
\label{Def:chaotic iterations}
The set $\mathds{B}$ denoting $\{0,1\}$, let
$f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be a function
and $S\in \mathbb{S}$ be a strategy.
The so-called \emph{chaotic iterations} are
defined by $x^0\in \mathds{B}^{\mathsf{N}}$ and $\forall (n,i) \in
\mathds{N}^{\ast} \times \llbracket0;\mathsf{N-1}\rrbracket$:
\begin{equation*}
%\forall n\in \mathds{N}^{\ast }, \forall i\in \llbracket1;\mathsf{N}\rrbracket
%,x_i^n=\left\{
x_i^n=\left\{
\begin{array}{ll}
x_i^{n-1} & \text{ if }S^n\neq i, \\
\left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i.\end{array}\right.\end{equation*}
\end{definition}


In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is
\textquotedblleft iterated\textquotedblright . Note that in a more general
formulation, $S^n$ can be a subset of components and $f(x^{n-1})_{S^{n}}$ can
be replaced by $f(x^{k})_{S^{n}}$, where $k<n$, describing for example, delays
transmission (see \cite{Bahi2002,bcv06:ij}). For the
general definition of such chaotic iterations, see,
\emph{e.g.},~\cite{Robert1986}.



\subsection{Devaney's chaotic dynamical systems}
\label{sec:Devaney}

Some topological definitions and properties taken from the
mathematical theory of chaos are recalled in this section.
%It is important to understand these notions which will be used in
%the rest of this article especially in the Section~\ref{sec:SCISMM-topological-model}~\vpageref{sec:SCISMM-topological-model} and the Section~\ref{sec:SCISMM-chaos-security}~\vpageref{sec:SCISMM-chaos-security}.

%\subsubsection{Notations}

%\begin{itemize}
%  \item Let $(\mathcal{X},d)$ be a metric space.
%  \item Let $f$ be a continuous function on  $(\mathcal{X},d)$.
%\end{itemize}

Let $(\mathcal{X},d)$ be a metric space and $f$ a continuous function on  $(\mathcal{X},d)$.

%\subsubsection{Topological definitions used in chaos}

\begin{definition}[Topological transitivity]
 $f$ is said to be \emph{topologically transitive} if, for any pair
of open sets $U,V\subset \mathcal{X}$, there exists $k>0$ such that $f^{k}(U)\cap
V\neq\varnothing $.
\label{def:chaos-devaney}
\end{definition}

\begin{definition}[Regularity]
$(\mathcal{X},f)$ is said to be \emph{regular} if the set of
periodic points is dense in $\mathcal{X}$.
\end{definition}

\begin{definition}[Sensitivity]
$f$ has \emph{sensitive dependence on initial conditions} if there exists $\delta >0$ such that, for any $x\in
\mathcal{X}$ and any neighborhood $V$ of $x$, there exist $y\in V$ and
$n\geqslant 0$ such that $d\left(f^{n}(x),f^{n}(y)\right)>\delta $.

$\delta $ is called the \emph{constant of sensitivity} of $f$.
\end{definition}


It is now possible to introduce the well-established mathematical definition of
chaos formulated by Devaney~\cite{Devaney89},

\begin{definition}[Chaotic function]
A function $f:\mathcal{X}\longrightarrow \mathcal{X}$ is said to be
\emph{chaotic} on $\mathcal{X}$ if:
\begin{enumerate}
  \item $f$ is regular,
  \item $f$ is topologically transitive,
  \item $f$ has sensitive dependence on initial conditions.
\end{enumerate}
\end{definition}

When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting
Devaney: ``it is unpredictable because of the sensitive dependence on initial
conditions. It cannot be broken down or simplified into two subsystems which do
not interact because of topological transitivity. And in the midst of this
random behavior, we nevertheless have an element of regularity''. Fundamentally
different behaviors are consequently possible and occur in an unpredictable
way.

Let us finally remark that,


\begin{theorem}[Banks~\cite{Banks92}]\label{theo:banks}
If a function is regular and topologically transitive on a metric space, then the
function is sensitive on initial conditions.
\end{theorem}

%The main interest of the Banks theorem is to reduce the properties to check when
%we want to prove that a function on a metric space is chaotic. 
%This theorm will be used in the
%Section~\ref{sec:SCISMM-chaos-security}~\vpageref{sec:SCISMM-chaos-security}.

%This theorem reduces the number of proofs when establishing the chaotic behavior of an iterate function on a metric space.
%We will use it, for instance, in Section~\ref{sec:SCISMM-chaos-security}.

Let us now study the original relation between chaotic iterations and Devaney's chaos. This relation will be used in the context of information hiding security. 

\subsection{Dynamics of Chaotic Iterations}\label{sec:topological}


\noindent In this section, we give the outline proofs we have previously obtained, establishing the topological properties of chaotic iterations \cite{gfb10:ip,guyeux10ter,bg10:ij}. As our scheme is inspired by this work, the proofs detailed in this document will follow a same canvas.

Let us firstly introduce some notations and terminologies in a view to describe chaotic iterations as an iteration function on a metric space. First of all, we show that CIs consist in the operation of a specific function $F_f$ on some components of a system. This can be described by using a discrete Boolean metric, as follows.



\begin{definition}[Discrete boolean metric]
\label{def:discret-boolean-metric}
The \emph{discrete boolean metric} is the
application $\delta: \mathds{B} \longrightarrow \mathds{B}$ defined by
$\delta(x,y)=0\Leftrightarrow x=y.$
\end{definition}

We can now define $F_f$, whose goal is to change the $k-$th component of the state $E$ by using $f$:

\begin{definition}[Function $F_{f}$]
Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the function \emph{$F_{f}$} is defined by:
\begin{equation*}
\begin{array}{ll}
F_{f}: & \llbracket 0;\mathsf{N-1}\rrbracket \times
\mathds{B}^{\mathsf{N}} \longrightarrow \mathds{B}^{\mathsf{N}} \\
 & (k,E) \longmapsto \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
(k,j)}\right)_{j\in \llbracket 0;\mathsf{N-1}\rrbracket} \\
\end{array}
\end{equation*}
\end{definition}

As recalled before, the components to update are given by a ``strategy'', \emph{i.e.}, a sequence of integers bounded by the size of the system. This can be formulated as follows,

\begin{definition}[Strategy]
\label{def:strategy-adapter}
Let $\mathsf{k} \in \mathds{N}^\ast$. 
A \emph{strategy} is a sequence which elements belong into $\llbracket 0, \mathsf{k-1} \rrbracket$.
The set of all strategies with terms in $\llbracket 0, \mathsf{k-1} \rrbracket$
is denoted by  $\mathbb{S}_\mathsf{k}$.
\end{definition}

We thus iterate on the Cartesian product $\mathcal{X}_1$ constituted by the set of states and the set of strategies:

\begin{definition}[Phase space]
The phase space used for chaotic iterations is denoted by $\mathcal{X}_1$ and
defined by $\mathcal{X}_1=\mathbb{S}_\mathsf{N} \times
\mathds{B}^{\mathsf{N}}.$
\end{definition}

We can remark that~\cite{bg10:ij},

\begin{proposition}%[Cardinality of $\mathcal{X}_1$]
\label{prop:cardinality-X1}
The phase space $\mathcal{X}_1$ has, at least, the cardinality of the 
continuum.
\end{proposition}



It still remains to describe CIs as a discrete dynamical system $x^{n+1} = G_f(x^n)$ on $\mathcal{X}_1$ for a function $G_f$ to define.
To do so, we will use $F_f$ and two other functions, namely the \emph{initial} and the \emph{shift} functions.
The initial function returns the first term of a given strategy-adapter whereas the shift function removes it:

\begin{definition}[Initial function]
Let $\mathsf{k} \in \mathds{N}^\ast$. 
The \emph{initial function} is the map $i_\mathsf{k}$ defined by:
\begin{equation*}
\begin{array}{cccc}
i_\mathsf{k}: & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \llbracket 0, \mathsf{k-1} \rrbracket \\
   & (S^{n})_{n\in \mathds{N}} & \longmapsto & S^{0} \\
\end{array}
\end{equation*}
\end{definition}




\begin{definition}[Shift function]
Let $\mathsf{k} \in \mathds{N}^\ast$. 
The \emph{shift function} is the map $\sigma_\mathsf{k}$ defined by:
\begin{equation*}
\begin{array}{cccc}
\sigma_\mathsf{k} : & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \mathbb{S}_\mathsf{k}\\
         & (S^{n})_{n\in \mathds{N}} & \longmapsto & (S^{n+1})_{n\in \mathds{N}}
\end{array}
\end{equation*}
\end{definition}

We are now able to introduce the function $G_f$:

\begin{definition}[Map $G_{f}$]
Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the map \emph{$G_{f}$} is defined by:
\begin{equation*}
\begin{array}{cccc}
G_{f}: & \mathcal{X}_1 & \longrightarrow & \mathcal{X}_1 \\
 & \left( S,E\right) & \longmapsto &\left( \sigma_\mathsf{N} (S),F_{f}(i_\mathsf{N}(S),E)\right)
 \\
\end{array}
\end{equation*}
\end{definition}





In other words, one iteration consists in a shift of strategy $S$ and a replacement of the $i_\mathsf{N}(S)$ cell with $f(E)_{i_\mathsf{N}(S)}$.


With these definitions, CIs can be described by the following iterations of the discrete dynamical system:

\begin{equation}
\left\{
\begin{array}{l}
X^{0}\in \mathcal{X}_1\\
\forall k \in \mathds{N}^\ast, X^{k+1}=G_{f}(X^{k})
\end{array}
\right.
\end{equation}


We need a metric space in order to study the topological behavior of the CIs. This is why a new distance $d_1$ between two points has been defined in~\cite{bg10:ij} by:


\begin{definition}[Distance $d_1$ on  $\mathcal{X}_1$]\label{def:distance-on-X1}
$\forall (S,E),(\check{S},\check{E} )\in \mathcal{X}_1,$
$d_1((S,E);(\check{S},\check{E}))=d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})+d_{\mathbb{S}_\mathsf{N}}(S,\check{S}),$
where:
\begin{itemize}
\item
$\displaystyle{d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})}=\displaystyle{\sum_{k=0}^{\mathsf{N-1}}\delta
(E_{k},\check{E}_{k})} \in \llbracket 0 ; \mathsf{N} \rrbracket$
\item
$\displaystyle{d_{\mathbb{S}_\mathsf{N}}(S,\check{S})}=\displaystyle{\dfrac{9}{\mathsf{N}}\sum_{k=0}^{\infty
}\dfrac{|S^{k}-\check{S}^{k}|}{10^{k+1}}} \in [0 ; 1[.$
\end{itemize}
are respectively two distances on $\mathds{B}^{\mathsf{N}}$ and $\mathbb{S}_\mathsf{N}$
($\forall \mathsf{N} \in \mathds{N}^\ast$).
\end{definition}

\begin{remark}
This new distance has been introduced in \cite{bg10:ij}
 to satisfy the following
requirements. When the number of different cells between two systems is
increasing, then their distance should increase too. In addition, if two systems
present the same cells and their respective strategies start with the same
terms, then the distance between these two points must be small, because the
evolution of the two systems will be the same for a while. The distance presented
above follows these recommendations. 
Indeed, if the floor value $\lfloor
d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$
cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the
differences between strategies $S$ and $\check{S}$. More precisely, this floating
part is less than $10^{-k}$ if and only if the first $k$ terms of the two
strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the
$k^{th}$ terms of the two strategies are different.
\end{remark}



We have proven that,

\begin{proposition}\label{Prop:continuite}
$G_f$ is a continuous function on $(\mathcal{X}_1,d_1)$, for all $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$.
\end{proposition}

Let us finally recall the iteration function used in \cite{guyeux10ter}.


\begin{definition}%[Vectorial negation]
The \emph{vectorial negation} is the function defined by:
\begin{equation*}
\begin{array}{cccc}
f_{0} : & \mathbb{B}^\mathsf{N} & \longrightarrow & \mathbb{B}^\mathsf{N}\\
& (b_0,\cdots,b_\mathsf{N-1}) & \longmapsto &
(\overline{b_0},\cdots,\overline{b_\mathsf{N-1}})\\
\end{array}
\end{equation*}
\end{definition}
%\begin{definition}[Vectorial Negation]\label{Def:vectorial-negation}
%\begin{equation}
%\begin{array}{cccc}
%f_0\ :\ & \mathbb{B}^N & \longrightarrow & \mathbb{B}^N \\
%& (b_1,\cdots,b_\mathsf{N}) & \longmapsto &
%(\overline{b_1},\cdots,\overline{b_\mathsf{N}})\\
%\end{array}
%\end{equation}
%\end{definition}
%It is then checked in \cite{bg10:ij} that i
In the metric space $(\mathcal{X}_1,d_1)$, $G_{f_0}$  satisfies the three
conditions for Devaney's chaos: regularity, transitivity, and
sensibility to the initial condition. %~\cite{bg10:ij}. 
So,

%the following result.
\begin{theorem}%[$G_{f_0}$ is a chaotic map]
$G_{f_0}$ is a chaotic map on $(\mathcal{X}_1,d_1)$ according to the Devaney's formulation.
\end{theorem}