]> AND Private Git Repository - HindawiJournalOfChaos.git/blob - IH/iihmsp13/rcl.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
tt
[HindawiJournalOfChaos.git] / IH / iihmsp13 / rcl.tex
1
2
3 \subsection{Chaotic Iterations}
4 \label{sec:chaotic-iterations}
5
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
9
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}.$
16
17 \begin{definition}
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$:
25 \begin{equation*}
26 %\forall n\in \mathds{N}^{\ast }, \forall i\in \llbracket1;\mathsf{N}\rrbracket
27 %,x_i^n=\left\{
28 x_i^n=\left\{
29 \begin{array}{ll}
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*}
32 \end{definition}
33
34
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}.
42
43
44
45 \subsection{Devaney's chaotic dynamical systems}
46 \label{sec:Devaney}
47
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}.
52
53 %\subsubsection{Notations}
54
55 %\begin{itemize}
56 %  \item Let $(\mathcal{X},d)$ be a metric space.
57 %  \item Let $f$ be a continuous function on  $(\mathcal{X},d)$.
58 %\end{itemize}
59
60 Let $(\mathcal{X},d)$ be a metric space and $f$ a continuous function on  $(\mathcal{X},d)$.
61
62 %\subsubsection{Topological definitions used in chaos}
63
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
67 V\neq\varnothing $.
68 \label{def:chaos-devaney}
69 \end{definition}
70
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}$.
74 \end{definition}
75
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 $.
80
81 $\delta $ is called the \emph{constant of sensitivity} of $f$.
82 \end{definition}
83
84
85 It is now possible to introduce the well-established mathematical definition of
86 chaos formulated by Devaney~\cite{Devaney89},
87
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:
91 \begin{enumerate}
92   \item $f$ is regular,
93   \item $f$ is topologically transitive,
94   \item $f$ has sensitive dependence on initial conditions.
95 \end{enumerate}
96 \end{definition}
97
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
104 way.
105
106 Let us finally remark that,
107
108
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.
112 \end{theorem}
113
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}.
118
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}.
121
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. 
123
124 \subsection{Dynamics of Chaotic Iterations}\label{sec:topological}
125
126
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.
128
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.
130
131
132
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.$
138 \end{definition}
139
140 We can now define $F_f$, whose goal is to change the $k-$th component of the state $E$ by using $f$:
141
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:
144 \begin{equation*}
145 \begin{array}{ll}
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} \\
150 \end{array}
151 \end{equation*}
152 \end{definition}
153
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,
155
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}$.
162 \end{definition}
163
164 We thus iterate on the Cartesian product $\mathcal{X}_1$ constituted by the set of states and the set of strategies:
165
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}}.$
170 \end{definition}
171
172 We can remark that~\cite{bg10:ij},
173
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 
177 continuum.
178 \end{proposition}
179
180
181
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:
185
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:
189 \begin{equation*}
190 \begin{array}{cccc}
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} \\
193 \end{array}
194 \end{equation*}
195 \end{definition}
196
197
198
199
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:
203 \begin{equation*}
204 \begin{array}{cccc}
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}}
207 \end{array}
208 \end{equation*}
209 \end{definition}
210
211 We are now able to introduce the function $G_f$:
212
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:
215 \begin{equation*}
216 \begin{array}{cccc}
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)
219  \\
220 \end{array}
221 \end{equation*}
222 \end{definition}
223
224
225
226
227
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)}$.
229
230
231 With these definitions, CIs can be described by the following iterations of the discrete dynamical system:
232
233 \begin{equation}
234 \left\{
235 \begin{array}{l}
236 X^{0}\in \mathcal{X}_1\\
237 \forall k \in \mathds{N}^\ast, X^{k+1}=G_{f}(X^{k})
238 \end{array}
239 \right.
240 \end{equation}
241
242
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:
244
245
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}),$
249 where:
250 \begin{itemize}
251 \item
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$
254 \item
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[.$
257 \end{itemize}
258 are respectively two distances on $\mathds{B}^{\mathsf{N}}$ and $\mathbb{S}_\mathsf{N}$
259 ($\forall \mathsf{N} \in \mathds{N}^\ast$).
260 \end{definition}
261
262 \begin{remark}
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.
278 \end{remark}
279
280
281
282 We have proven that,
283
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}$.
286 \end{proposition}
287
288 Let us finally recall the iteration function used in \cite{guyeux10ter}.
289
290
291 \begin{definition}%[Vectorial negation]
292 The \emph{vectorial negation} is the function defined by:
293 \begin{equation*}
294 \begin{array}{cccc}
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}})\\
298 \end{array}
299 \end{equation*}
300 \end{definition}
301 %\begin{definition}[Vectorial Negation]\label{Def:vectorial-negation}
302 %\begin{equation}
303 %\begin{array}{cccc}
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}})\\
307 %\end{array}
308 %\end{equation}
309 %\end{definition}
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}. 
314 So,
315
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.
319 \end{theorem}
320