3 \subsection{Chaotic Iterations}
4 \label{sec:chaotic-iterations}
6 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and
7 $V_{i}$ is for the $i^{th}$ component of a vector $V$. Finally, the following notation
8 is used: $\llbracket0;N\rrbracket=\{0,1,\hdots,N\}$.\newline
10 Let us consider a \emph{system} of a finite number $\mathsf{N}$ of elements (or
11 \emph{cells}), so that each cell has a boolean \emph{state}. A sequence of length
12 $\mathsf{N}$ of boolean states of the cells corresponds to a particular
13 \emph{state of the system}. A sequence that elements belong into $\llbracket
14 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
15 strategies is denoted by $\mathbb{S}.$
18 \label{Def:chaotic iterations}
19 The set $\mathds{B}$ denoting $\{0,1\}$, let
20 $f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be a function
21 and $S\in \mathbb{S}$ be a strategy.
22 The so-called \emph{chaotic iterations} are
23 defined by $x^0\in \mathds{B}^{\mathsf{N}}$ and $\forall (n,i) \in
24 \mathds{N}^{\ast} \times \llbracket0;\mathsf{N-1}\rrbracket$:
26 %\forall n\in \mathds{N}^{\ast }, \forall i\in \llbracket1;\mathsf{N}\rrbracket
30 x_i^{n-1} & \text{ if }S^n\neq i, \\
31 \left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i.\end{array}\right.\end{equation*}
35 In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is
36 \textquotedblleft iterated\textquotedblright . Note that in a more general
37 formulation, $S^n$ can be a subset of components and $f(x^{n-1})_{S^{n}}$ can
38 be replaced by $f(x^{k})_{S^{n}}$, where $k<n$, describing for example, delays
39 transmission (see \cite{Bahi2002,bcv06:ij}). For the
40 general definition of such chaotic iterations, see,
41 \emph{e.g.},~\cite{Robert1986}.
45 \subsection{Devaney's chaotic dynamical systems}
48 Some topological definitions and properties taken from the
49 mathematical theory of chaos are recalled in this section.
50 %It is important to understand these notions which will be used in
51 %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}.
53 %\subsubsection{Notations}
56 % \item Let $(\mathcal{X},d)$ be a metric space.
57 % \item Let $f$ be a continuous function on $(\mathcal{X},d)$.
60 Let $(\mathcal{X},d)$ be a metric space and $f$ a continuous function on $(\mathcal{X},d)$.
62 %\subsubsection{Topological definitions used in chaos}
64 \begin{definition}[Topological transitivity]
65 $f$ is said to be \emph{topologically transitive} if, for any pair
66 of open sets $U,V\subset \mathcal{X}$, there exists $k>0$ such that $f^{k}(U)\cap
68 \label{def:chaos-devaney}
71 \begin{definition}[Regularity]
72 $(\mathcal{X},f)$ is said to be \emph{regular} if the set of
73 periodic points is dense in $\mathcal{X}$.
76 \begin{definition}[Sensitivity]
77 $f$ has \emph{sensitive dependence on initial conditions} if there exists $\delta >0$ such that, for any $x\in
78 \mathcal{X}$ and any neighborhood $V$ of $x$, there exist $y\in V$ and
79 $n\geqslant 0$ such that $d\left(f^{n}(x),f^{n}(y)\right)>\delta $.
81 $\delta $ is called the \emph{constant of sensitivity} of $f$.
85 It is now possible to introduce the well-established mathematical definition of
86 chaos formulated by Devaney~\cite{Devaney89},
88 \begin{definition}[Chaotic function]
89 A function $f:\mathcal{X}\longrightarrow \mathcal{X}$ is said to be
90 \emph{chaotic} on $\mathcal{X}$ if:
93 \item $f$ is topologically transitive,
94 \item $f$ has sensitive dependence on initial conditions.
98 When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting
99 Devaney: ``it is unpredictable because of the sensitive dependence on initial
100 conditions. It cannot be broken down or simplified into two subsystems which do
101 not interact because of topological transitivity. And in the midst of this
102 random behavior, we nevertheless have an element of regularity''. Fundamentally
103 different behaviors are consequently possible and occur in an unpredictable
106 Let us finally remark that,
109 \begin{theorem}[Banks~\cite{Banks92}]\label{theo:banks}
110 If a function is regular and topologically transitive on a metric space, then the
111 function is sensitive on initial conditions.
114 %The main interest of the Banks theorem is to reduce the properties to check when
115 %we want to prove that a function on a metric space is chaotic.
116 %This theorm will be used in the
117 %Section~\ref{sec:SCISMM-chaos-security}~\vpageref{sec:SCISMM-chaos-security}.
119 %This theorem reduces the number of proofs when establishing the chaotic behavior of an iterate function on a metric space.
120 %We will use it, for instance, in Section~\ref{sec:SCISMM-chaos-security}.
122 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.
124 \subsection{Dynamics of Chaotic Iterations}\label{sec:topological}
127 \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.
129 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.
133 \begin{definition}[Discrete boolean metric]
134 \label{def:discret-boolean-metric}
135 The \emph{discrete boolean metric} is the
136 application $\delta: \mathds{B} \longrightarrow \mathds{B}$ defined by
137 $\delta(x,y)=0\Leftrightarrow x=y.$
140 We can now define $F_f$, whose goal is to change the $k-$th component of the state $E$ by using $f$:
142 \begin{definition}[Function $F_{f}$]
143 Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the function \emph{$F_{f}$} is defined by:
146 F_{f}: & \llbracket 0;\mathsf{N-1}\rrbracket \times
147 \mathds{B}^{\mathsf{N}} \longrightarrow \mathds{B}^{\mathsf{N}} \\
148 & (k,E) \longmapsto \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
149 (k,j)}\right)_{j\in \llbracket 0;\mathsf{N-1}\rrbracket} \\
154 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,
156 \begin{definition}[Strategy]
157 \label{def:strategy-adapter}
158 Let $\mathsf{k} \in \mathds{N}^\ast$.
159 A \emph{strategy} is a sequence which elements belong into $\llbracket 0, \mathsf{k-1} \rrbracket$.
160 The set of all strategies with terms in $\llbracket 0, \mathsf{k-1} \rrbracket$
161 is denoted by $\mathbb{S}_\mathsf{k}$.
164 We thus iterate on the Cartesian product $\mathcal{X}_1$ constituted by the set of states and the set of strategies:
166 \begin{definition}[Phase space]
167 The phase space used for chaotic iterations is denoted by $\mathcal{X}_1$ and
168 defined by $\mathcal{X}_1=\mathbb{S}_\mathsf{N} \times
169 \mathds{B}^{\mathsf{N}}.$
172 We can remark that~\cite{bg10:ij},
174 \begin{proposition}%[Cardinality of $\mathcal{X}_1$]
175 \label{prop:cardinality-X1}
176 The phase space $\mathcal{X}_1$ has, at least, the cardinality of the
182 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.
183 To do so, we will use $F_f$ and two other functions, namely the \emph{initial} and the \emph{shift} functions.
184 The initial function returns the first term of a given strategy-adapter whereas the shift function removes it:
186 \begin{definition}[Initial function]
187 Let $\mathsf{k} \in \mathds{N}^\ast$.
188 The \emph{initial function} is the map $i_\mathsf{k}$ defined by:
191 i_\mathsf{k}: & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \llbracket 0, \mathsf{k-1} \rrbracket \\
192 & (S^{n})_{n\in \mathds{N}} & \longmapsto & S^{0} \\
200 \begin{definition}[Shift function]
201 Let $\mathsf{k} \in \mathds{N}^\ast$.
202 The \emph{shift function} is the map $\sigma_\mathsf{k}$ defined by:
205 \sigma_\mathsf{k} : & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \mathbb{S}_\mathsf{k}\\
206 & (S^{n})_{n\in \mathds{N}} & \longmapsto & (S^{n+1})_{n\in \mathds{N}}
211 We are now able to introduce the function $G_f$:
213 \begin{definition}[Map $G_{f}$]
214 Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the map \emph{$G_{f}$} is defined by:
217 G_{f}: & \mathcal{X}_1 & \longrightarrow & \mathcal{X}_1 \\
218 & \left( S,E\right) & \longmapsto &\left( \sigma_\mathsf{N} (S),F_{f}(i_\mathsf{N}(S),E)\right)
228 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)}$.
231 With these definitions, CIs can be described by the following iterations of the discrete dynamical system:
236 X^{0}\in \mathcal{X}_1\\
237 \forall k \in \mathds{N}^\ast, X^{k+1}=G_{f}(X^{k})
243 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:
246 \begin{definition}[Distance $d_1$ on $\mathcal{X}_1$]\label{def:distance-on-X1}
247 $\forall (S,E),(\check{S},\check{E} )\in \mathcal{X}_1,$
248 $d_1((S,E);(\check{S},\check{E}))=d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})+d_{\mathbb{S}_\mathsf{N}}(S,\check{S}),$
252 $\displaystyle{d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})}=\displaystyle{\sum_{k=0}^{\mathsf{N-1}}\delta
253 (E_{k},\check{E}_{k})} \in \llbracket 0 ; \mathsf{N} \rrbracket$
255 $\displaystyle{d_{\mathbb{S}_\mathsf{N}}(S,\check{S})}=\displaystyle{\dfrac{9}{\mathsf{N}}\sum_{k=0}^{\infty
256 }\dfrac{|S^{k}-\check{S}^{k}|}{10^{k+1}}} \in [0 ; 1[.$
258 are respectively two distances on $\mathds{B}^{\mathsf{N}}$ and $\mathbb{S}_\mathsf{N}$
259 ($\forall \mathsf{N} \in \mathds{N}^\ast$).
263 This new distance has been introduced in \cite{bg10:ij}
264 to satisfy the following
265 requirements. When the number of different cells between two systems is
266 increasing, then their distance should increase too. In addition, if two systems
267 present the same cells and their respective strategies start with the same
268 terms, then the distance between these two points must be small, because the
269 evolution of the two systems will be the same for a while. The distance presented
270 above follows these recommendations.
271 Indeed, if the floor value $\lfloor
272 d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$
273 cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the
274 differences between strategies $S$ and $\check{S}$. More precisely, this floating
275 part is less than $10^{-k}$ if and only if the first $k$ terms of the two
276 strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the
277 $k^{th}$ terms of the two strategies are different.
284 \begin{proposition}\label{Prop:continuite}
285 $G_f$ is a continuous function on $(\mathcal{X}_1,d_1)$, for all $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$.
288 Let us finally recall the iteration function used in \cite{guyeux10ter}.
291 \begin{definition}%[Vectorial negation]
292 The \emph{vectorial negation} is the function defined by:
295 f_{0} : & \mathbb{B}^\mathsf{N} & \longrightarrow & \mathbb{B}^\mathsf{N}\\
296 & (b_0,\cdots,b_\mathsf{N-1}) & \longmapsto &
297 (\overline{b_0},\cdots,\overline{b_\mathsf{N-1}})\\
301 %\begin{definition}[Vectorial Negation]\label{Def:vectorial-negation}
304 %f_0\ :\ & \mathbb{B}^N & \longrightarrow & \mathbb{B}^N \\
305 %& (b_1,\cdots,b_\mathsf{N}) & \longmapsto &
306 %(\overline{b_1},\cdots,\overline{b_\mathsf{N}})\\
310 %It is then checked in \cite{bg10:ij} that i
311 In the metric space $(\mathcal{X}_1,d_1)$, $G_{f_0}$ satisfies the three
312 conditions for Devaney's chaos: regularity, transitivity, and
313 sensibility to the initial condition. %~\cite{bg10:ij}.
316 %the following result.
317 \begin{theorem}%[$G_{f_0}$ is a chaotic map]
318 $G_{f_0}$ is a chaotic map on $(\mathcal{X}_1,d_1)$ according to the Devaney's formulation.