1 \documentclass[a4paper,11pt]{comjnl}
\r
2 %\documentclass{comjnl}
\r
7 % Added packages (Nicolas Friot)
\r
11 \usepackage{amsfonts}
\r
12 \usepackage{dsfont} %Pour mathds
\r
13 % % Pour avoir des intervalles d'entiers
\r
14 \usepackage{stmaryrd}
\r
16 \usepackage{multirow}
\r
17 %\usepackage{graphicx}
\r
23 \usepackage[english]{varioref}
\r
25 %%%%%%%%%%%% ATTENTION : A VIRER POUR LA SOUMISSION
\r
26 \usepackage[linkcolor=blue,colorlinks=true,citecolor=blue]{hyperref}
\r
27 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
31 %\copyrightyear{2009} \vol{00} \issue{0} \DOI{000}
\r
37 %\title[Modelling Bidders in Sequential Automated Auctions]{Modelling Bidders in
\r
38 %Sequential Automated Auctions}
\r
40 \title[Information Hiding by Chaotic Iterations, Security and
\r
41 Robustness]{Information Hiding by Chaotic Iterations\\Security and Robustness}
\r
43 %\author{Kumaara Velan}
\r
45 % \author{Jacques M. Bahi\textsuperscript{1}, Nicolas Friot\textsuperscript{1},
\r
46 % Christophe Guyeux\textsuperscript{1}, and Kamel
\r
47 % Mazouzi\textsuperscript{2}~*\\\tiny * Authors in alphabetic order.}
\r
49 \author{* Jacques M. Bahi}
\r
50 \email{\{jacques.bahi,christophe.guyeux,kamel.mazouzi\}@univ-fcomte.fr\\nicolas.friot@lifc.univ-fcomte.fr\\\vspace{0.5cm}*
\r
51 Authors are cited in alphabetic order.}
\r
53 \author{Nicolas Friot}
\r
54 \author{Christophe Guyeux}
\r
56 \affiliation{Computer Science Laboratory LIFC}
\r
57 \author{Kamel Mazouzi}
\r
58 \affiliation{M\'esocentre de calcul de Franche-Comt\'e\\University of
\r
59 Franche-Comt\'e, 16 route de Gray, Besan\c con, France\\
\r
62 %\\\tiny Authors in alphabetic order.
\r
64 % \affiliation{Intelligent Systems and Networks Group, Department of
\r
65 % Electrical and Electronic Engineering, Imperial College, London
\r
66 % SW7 2BT, UK} \email{kumaara.velan@imperial.ac.uk}
\r
68 % \affiliation{\textsuperscript{1}Computer Science Laboratory LIFC\\
\r
69 % %, University of Franche-Comt\'e\\
\r
70 % %16 route de Gray, Besan\c con, France\\
\r
72 % \textsuperscript{2}M\'esocentre de calcul de Franche-Comt\'e\\
\r
73 % University of Franche-Comt\'e, 16 route de Gray, Besan\c con, France
\r
76 %\email{\{jacques.bahi,christophe.guyeux,kamel.mazouzi\}@univ-fcomte.fr\\nicolas.friot@lifc.univ-fcomte.fr}
\r
79 %\shortauthors{K. Velan}
\r
80 \shortauthors{J. M. Bahi, N. Friot, C. Guyeux, and K. Mazouzi}
\r
81 % \shortauthors{N. Friot}
\r
82 % \shortauthors{C. Guyeux}
\r
83 % \shortauthors{K. Mazouzi}
\r
85 % \received{00 January 2009}
\r
86 % \revised{00 Month 2009}
\r
91 %\category{C.2}{Computer Communication Networks}{Computer Networks}
\r
92 %\category{C.4}{Performance of Systems}{Analytical Models}
\r
93 %\category{G.3}{Stochastic Processes}{Queueing Systems}
\r
94 %\terms{Internet Technologies, E-Commerce}
\r
95 % \keywords{Automated Auctions; Analytical Models; Autonomic
\r
96 % Systems; Internet Technologies; E-Commerce; Queueing Systems}
\r
98 \keywords{Information hiding; Chaos; Security; Robustness.
\r
104 In this paper, recent contributions in the field of chaos-based information hiding security is summed up and deepened.
\r
105 Additionally, two variants of an information hiding scheme based on chaotic iterations are recalled and their security proofs are completed.
\r
106 Among other things, new evaluations of qualitative and quantitative properties of security concerning the improved version of our algorithm are proposed.
\r
107 The security notions used here encompass the probabilistic stego-security against watermark-only attacks, and the topological chaos-security to face known message, known original, and constant-message attacks.
\r
108 Finally, a complete and original evaluation of the robustness of the first variant in spatial domain is given, encompassing several kinds of attacks against a set of hundreds of watermarked medias.
\r
114 %%%%%%%%%%%% ATTENTION : A VIRER POUR LA SOUMISSION
\r
120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\r
122 \section{Introduction}\label{sec:introduction}
\r
125 Information hiding has recently become a major security technology, especially with the increasing importance and widespread distribution of digital media through the Internet.
\r
126 It includes several techniques, among which are digital watermarking and steganography. On the one hand, the aim of digital watermarking is to embed a piece of information into digital documents, like pictures or movies, for a large panel of reasons, such as: copyright protection, control utilization, data description, integrity checking, or content authentication. Digital watermarking must have an essential characteristic called robustness against attacks. On the other hand, steganography consisting in the deployment of an hidden channel in public exchanges, requires security properties guaranteeing that the channel is undetectable.
\r
128 Robustness and security are thus two major concerns in information hiding.
\r
129 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.
\r
130 Indeed, security encompasses robustness and intentional attacks~\cite{Kalker2001,ComesanaPP05bis}.
\r
131 The best attempt to give an elegant and concise definition for each of these two terms was proposed in \cite{Kalker2001}.
\r
132 Following Kalker, we will consider in this research work that:
\r
134 watermarking is a mechanism to create a communication channel that is
\r
135 multiplexed into original content [...]. It is required that, firstly, the
\r
136 perceptual degradation of the marked content [...] is minimal and, secondly,
\r
137 that the capacity of the watermark channel degrades as a smooth function of the
\r
138 degradation of the marked content. [...]. Watermarking security refers to the
\r
139 inability by unauthorized users to have access to the raw watermarking channel.
\r
140 [...] to remove, detect and estimate, write or modify the raw watermarking
\r
144 In the framework of watermarking and steganography, security has seen several important developments since the last decade~\cite{BarniBF03,Cayre2005,Ker06}.
\r
145 The first fundamental work in security was made by Cachin in the context of steganography~\cite{Cachin2004}.
\r
146 Cachin interprets the attempts of an attacker to distinguish between an innocent image and a stego-content as a hypothesis testing problem.
\r
147 In this document, the basic properties of a stegosystem are defined using the notions of entropy, mutual information, and relative entropy.
\r
148 Mittelholzer, inspired by the work of Cachin, proposed the first theoretical framework for analyzing the security of a watermarking scheme~\cite{Mittelholzer99}.
\r
149 These efforts to bring a theoretical framework for security in steganography and watermarking have been followed up by Kalker, who tries to clarify the concepts (robustness versus security), and the classifications of watermarking attacks~\cite{Kalker2001}.
\r
150 This work has been deepened by Furon \emph{et al.}, who have translated Kerckhoffs' principle (Alice and Bob shall only rely on some previously shared secret for privacy), from cryptography to data hiding~\cite{Furon2002}.
\r
151 They used Diffie and Hellman methodology, and Shannon's cryptographic framework~\cite{Shannon49}, to classify the watermarking attacks into categories, according to the type of information Eve has access to~\cite{Cayre2005,Perez06}, namely: Watermarked Only Attack (WOA), Known Message Attack (KMA), Known Original Attack (KOA), and Constant-Message Attack (CMA).
\r
152 Levels of security have been recently defined in these setups.
\r
153 The highest level of security in WOA is called stego-security \cite{Cayre2008}, whereas chaos-security tends to improve the ability to withstand attacks in KMA, KOA, and CMA setups \cite{gfb10:ip}.
\r
156 This paper is both an overview of our contributions in the field of information hiding~\cite{gfb10:ip,guyeuxThese10,guyeux10ter}, an extension of our researches concerning the security of chaotic iterations based schemes, and a complete study of their robustness. In \cite{gfb10:ip,guyeuxThese10}, we have shown that the security level of such algorithms can be studied into a novel framework based on unpredictability, as it is understood in the mathematical theory of chaos~\cite{Devaney}. To do so, a new class of security has been introduced, namely the chaos-security. This new class can be used to study some categories of attacks that are difficult to investigate in the existing security approach: namely, the KMA, KOA, and CMA setups. It also enriches the variety of qualitative and quantitative tools that evaluate how strong the security is, thus reinforcing the confidence that can be had in a given scheme.
\r
158 We have applied this framework in concrete examples. For instance, we have proven in~\cite{guyeuxThese10,ih10} that Natural Watermarking (NW) technique is chaos-secure. Moreover, this technique possesses additional properties of unpredictability, namely, strong transitivity, topological mixing, and a constant of sensitivity equal to $\frac{N}{2}$. However NW are not expansive, which is problematic in the CMA and KMA setups~\cite{guyeuxThese10,ih10}.
\r
159 This is why a new information hiding scheme has been introduced in~\cite{guyeux10ter}, which is based on the so-called chaotic iterations. Its security has been established in \cite{gfb10:ip}. However, this former algorithm allow to embed only one bit. So this scheme has been improved in \cite{fgb11:ip}, in a version that allows to embed $n$ bits, while preserving the highest levels of security.
\r
161 In this research work, all of these contributions are regrouped together. This summary is the first contribution of this paper. The security study of the new version of our information hiding scheme is deepened, by giving qualitative and quantitative measures of its level of chaos-security. This second contribution encompasses the evaluation of the constant of sensibility, and the qualitative properties of strong transitivity and indecomposability. Finally, a complete and rigorous evaluation of the robustness of the algorithm is proposed as a third contribution. This study has been initiated in \cite{guyeux10ter}, but only on one given image and for a small number of attacks. We have extend this work by using hundreds of images and a large variety of parameters and attacks.
\r
163 The remainder of this document is organized as follows.
\r
164 In Section \ref{sec:basic-recalls}, some basic recalls concerning both chaotic iterations and Devaney's chaos are given, and the relation unifying them is recalled.
\r
165 In Section \ref{section:IH based on CIs} is presented the first version, denoted by $CI_1$, of our information hiding scheme.
\r
166 The next section is devoted to the security study of $CI_1$, encompassing both the stego-security and the chaos-security.
\r
167 Then, in Section \ref{section:robustness-ci-1}, a complete and rigorous evaluation of the robustness of $CI_1$, realized by using the ``M\'{e}socentre de calcul de Franche-Comt\'{e}'', is given.
\r
169 This research work ends by a conclusion section where our contribution is
\r
170 summarized and intended future researches are presented.
\r
176 \section{Basic Recalls}
\r
177 \label{sec:basic-recalls}
\r
180 \subsection{Chaotic Iterations}
\r
181 \label{sec:chaotic-iterations}
\r
183 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and
\r
184 $V_{i}$ is for the $i^{th}$ component of a vector $V$. Finally, the following notation
\r
185 is used: $\llbracket0;N\rrbracket=\{0,1,\hdots,N\}$.\newline
\r
187 Let us consider a \emph{system} of a finite number $\mathsf{N}$ of elements (or
\r
188 \emph{cells}), so that each cell has a boolean \emph{state}. A sequence of length
\r
189 $\mathsf{N}$ of boolean states of the cells corresponds to a particular
\r
190 \emph{state of the system}. A sequence that elements belong into $\llbracket
\r
191 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
\r
192 strategies is denoted by $\mathbb{S}.$
\r
195 \label{Def:chaotic iterations}
\r
196 The set $\mathds{B}$ denoting $\{0,1\}$, let
\r
197 $f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be a function
\r
198 and $S\in \mathbb{S}$ be a strategy.
\r
199 The so-called \emph{chaotic iterations} are
\r
200 defined by $x^0\in \mathds{B}^{\mathsf{N}}$ and $\forall (n,i) \in
\r
201 \mathds{N}^{\ast} \times \llbracket0;\mathsf{N-1}\rrbracket$:
\r
203 %\forall n\in \mathds{N}^{\ast }, \forall i\in \llbracket1;\mathsf{N}\rrbracket
\r
207 x_i^{n-1} & \text{ if }S^n\neq i, \\
\r
208 \left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i.\end{array}\right.\end{equation*}
\r
212 In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is
\r
213 \textquotedblleft iterated\textquotedblright . Note that in a more general
\r
214 formulation, $S^n$ can be a subset of components and $f(x^{n-1})_{S^{n}}$ can
\r
215 be replaced by $f(x^{k})_{S^{n}}$, where $k<n$, describing for example, delays
\r
216 transmission (see \cite{Bahi2002,bcv06:ij}). For the
\r
217 general definition of such chaotic iterations, see,
\r
218 \emph{e.g.},~\cite{Robert1986}.
\r
222 \subsection{Devaney's chaotic dynamical systems}
\r
223 \label{sec:Devaney}
\r
225 Some topological definitions and properties taken from the
\r
226 mathematical theory of chaos are recalled in this section.
\r
227 %It is important to understand these notions which will be used in
\r
228 %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}.
\r
230 %\subsubsection{Notations}
\r
233 % \item Let $(\mathcal{X},d)$ be a metric space.
\r
234 % \item Let $f$ be a continuous function on $(\mathcal{X},d)$.
\r
237 Let $(\mathcal{X},d)$ be a metric space and $f$ a continuous function on $(\mathcal{X},d)$.
\r
239 %\subsubsection{Topological definitions used in chaos}
\r
241 \begin{definition}[Topological transitivity]
\r
242 $f$ is said to be \emph{topologically transitive} if, for any pair
\r
243 of open sets $U,V\subset \mathcal{X}$, there exists $k>0$ such that $f^{k}(U)\cap
\r
244 V\neq\varnothing $.
\r
245 \label{def:chaos-devaney}
\r
248 \begin{definition}[Regularity]
\r
249 $(\mathcal{X},f)$ is said to be \emph{regular} if the set of
\r
250 periodic points is dense in $\mathcal{X}$.
\r
253 \begin{definition}[Sensitivity]
\r
254 $f$ has \emph{sensitive dependence on initial conditions} if there exists $\delta >0$ such that, for any $x\in
\r
255 \mathcal{X}$ and any neighborhood $V$ of $x$, there exist $y\in V$ and
\r
256 $n\geqslant 0$ such that $d\left(f^{n}(x),f^{n}(y)\right)>\delta $.
\r
258 $\delta $ is called the \emph{constant of sensitivity} of $f$.
\r
262 It is now possible to introduce the well-established mathematical definition of
\r
263 chaos formulated by Devaney~\cite{Devaney89},
\r
265 \begin{definition}[Chaotic function]
\r
266 A function $f:\mathcal{X}\longrightarrow \mathcal{X}$ is said to be
\r
267 \emph{chaotic} on $\mathcal{X}$ if:
\r
269 \item $f$ is regular,
\r
270 \item $f$ is topologically transitive,
\r
271 \item $f$ has sensitive dependence on initial conditions.
\r
275 When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting
\r
276 Devaney: ``it is unpredictable because of the sensitive dependence on initial
\r
277 conditions. It cannot be broken down or simplified into two subsystems which do
\r
278 not interact because of topological transitivity. And in the midst of this
\r
279 random behavior, we nevertheless have an element of regularity''. Fundamentally
\r
280 different behaviors are consequently possible and occur in an unpredictable
\r
283 Let us finally remark that,
\r
286 \begin{theorem}[Banks~\cite{Banks92}]\label{theo:banks}
\r
287 If a function is regular and topologically transitive on a metric space, then the
\r
288 function is sensitive on initial conditions.
\r
291 %The main interest of the Banks theorem is to reduce the properties to check when
\r
292 %we want to prove that a function on a metric space is chaotic.
\r
293 %This theorm will be used in the
\r
294 %Section~\ref{sec:SCISMM-chaos-security}~\vpageref{sec:SCISMM-chaos-security}.
\r
296 %This theorem reduces the number of proofs when establishing the chaotic behavior of an iterate function on a metric space.
\r
297 %We will use it, for instance, in Section~\ref{sec:SCISMM-chaos-security}.
\r
299 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.
\r
301 \subsection{Dynamics of Chaotic Iterations}\label{sec:topological}
\r
304 \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.
\r
306 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.
\r
310 \begin{definition}[Discrete boolean metric]
\r
311 \label{def:discret-boolean-metric}
\r
312 The \emph{discrete boolean metric} is the
\r
313 application $\delta: \mathds{B} \longrightarrow \mathds{B}$ defined by
\r
314 $\delta(x,y)=0\Leftrightarrow x=y.$
\r
317 We can now define $F_f$, whose goal is to change the $k-$th component of the state $E$ by using $f$:
\r
319 \begin{definition}[Function $F_{f}$]
\r
320 Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the function \emph{$F_{f}$} is defined by:
\r
323 F_{f}: & \llbracket 0;\mathsf{N-1}\rrbracket \times
\r
324 \mathds{B}^{\mathsf{N}} \longrightarrow \mathds{B}^{\mathsf{N}} \\
\r
325 & (k,E) \longmapsto \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
\r
326 (k,j)}\right)_{j\in \llbracket 0;\mathsf{N-1}\rrbracket} \\
\r
331 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,
\r
333 \begin{definition}[Strategy]
\r
334 \label{def:strategy-adapter}
\r
335 Let $\mathsf{k} \in \mathds{N}^\ast$.
\r
336 A \emph{strategy} is a sequence which elements belong into $\llbracket 0, \mathsf{k-1} \rrbracket$.
\r
337 The set of all strategies with terms in $\llbracket 0, \mathsf{k-1} \rrbracket$
\r
338 is denoted by $\mathbb{S}_\mathsf{k}$.
\r
341 We thus iterate on the Cartesian product $\mathcal{X}_1$ constituted by the set of states and the set of strategies:
\r
343 \begin{definition}[Phase space]
\r
344 The phase space used for chaotic iterations is denoted by $\mathcal{X}_1$ and
\r
345 defined by $\mathcal{X}_1=\mathbb{S}_\mathsf{N} \times
\r
346 \mathds{B}^{\mathsf{N}}.$
\r
349 We can remark that~\cite{bg10:ij},
\r
351 \begin{proposition}%[Cardinality of $\mathcal{X}_1$]
\r
352 \label{prop:cardinality-X1}
\r
353 The phase space $\mathcal{X}_1$ has, at least, the cardinality of the
\r
359 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.
\r
360 To do so, we will use $F_f$ and two other functions, namely the \emph{initial} and the \emph{shift} functions.
\r
361 The initial function returns the first term of a given strategy-adapter whereas the shift function removes it:
\r
363 \begin{definition}[Initial function]
\r
364 Let $\mathsf{k} \in \mathds{N}^\ast$.
\r
365 The \emph{initial function} is the map $i_\mathsf{k}$ defined by:
\r
367 \begin{array}{cccc}
\r
368 i_\mathsf{k}: & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \llbracket 0, \mathsf{k-1} \rrbracket \\
\r
369 & (S^{n})_{n\in \mathds{N}} & \longmapsto & S^{0} \\
\r
377 \begin{definition}[Shift function]
\r
378 Let $\mathsf{k} \in \mathds{N}^\ast$.
\r
379 The \emph{shift function} is the map $\sigma_\mathsf{k}$ defined by:
\r
381 \begin{array}{cccc}
\r
382 \sigma_\mathsf{k} : & \mathbb{S}_{\mathsf{k}} & \longrightarrow & \mathbb{S}_\mathsf{k}\\
\r
383 & (S^{n})_{n\in \mathds{N}} & \longmapsto & (S^{n+1})_{n\in \mathds{N}}
\r
388 We are now able to introduce the function $G_f$:
\r
390 \begin{definition}[Map $G_{f}$]
\r
391 Given a function $f:\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$, the map \emph{$G_{f}$} is defined by:
\r
393 \begin{array}{cccc}
\r
394 G_{f}: & \mathcal{X}_1 & \longrightarrow & \mathcal{X}_1 \\
\r
395 & \left( S,E\right) & \longmapsto &\left( \sigma_\mathsf{N} (S),F_{f}(i_\mathsf{N}(S),E)\right)
\r
405 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)}$.
\r
408 With these definitions, CIs can be described by the following iterations of the discrete dynamical system:
\r
413 X^{0}\in \mathcal{X}_1\\
\r
414 \forall k \in \mathds{N}^\ast, X^{k+1}=G_{f}(X^{k})
\r
420 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:
\r
423 \begin{definition}[Distance $d_1$ on $\mathcal{X}_1$]\label{def:distance-on-X1}
\r
424 $\forall (S,E),(\check{S},\check{E} )\in \mathcal{X}_1,$
\r
425 $d_1((S,E);(\check{S},\check{E}))=d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})+d_{\mathbb{S}_\mathsf{N}}(S,\check{S}),$
\r
429 $\displaystyle{d_{\mathds{B}^{\mathsf{N}}}(E,\check{E})}=\displaystyle{\sum_{k=0}^{\mathsf{N-1}}\delta
\r
430 (E_{k},\check{E}_{k})} \in \llbracket 0 ; \mathsf{N} \rrbracket$
\r
432 $\displaystyle{d_{\mathbb{S}_\mathsf{N}}(S,\check{S})}=\displaystyle{\dfrac{9}{\mathsf{N}}\sum_{k=0}^{\infty
\r
433 }\dfrac{|S^{k}-\check{S}^{k}|}{10^{k+1}}} \in [0 ; 1[.$
\r
435 are respectively two distances on $\mathds{B}^{\mathsf{N}}$ and $\mathbb{S}_\mathsf{N}$
\r
436 ($\forall \mathsf{N} \in \mathds{N}^\ast$).
\r
440 This new distance has been introduced in \cite{bg10:ij}
\r
441 to satisfy the following
\r
442 requirements. When the number of different cells between two systems is
\r
443 increasing, then their distance should increase too. In addition, if two systems
\r
444 present the same cells and their respective strategies start with the same
\r
445 terms, then the distance between these two points must be small, because the
\r
446 evolution of the two systems will be the same for a while. The distance presented
\r
447 above follows these recommendations.
\r
448 Indeed, if the floor value $\lfloor
\r
449 d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$
\r
450 cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the
\r
451 differences between strategies $S$ and $\check{S}$. More precisely, this floating
\r
452 part is less than $10^{-k}$ if and only if the first $k$ terms of the two
\r
453 strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the
\r
454 $k^{th}$ terms of the two strategies are different.
\r
459 We have proven that,
\r
461 \begin{proposition}\label{Prop:continuite}
\r
462 $G_f$ is a continuous function on $(\mathcal{X}_1,d_1)$, for all $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$.
\r
465 Let us finally recall the iteration function used in \cite{guyeux10ter}.
\r
468 \begin{definition}%[Vectorial negation]
\r
469 The \emph{vectorial negation} is the function defined by:
\r
471 \begin{array}{cccc}
\r
472 f_{0} : & \mathbb{B}^\mathsf{N} & \longrightarrow & \mathbb{B}^\mathsf{N}\\
\r
473 & (b_0,\cdots,b_\mathsf{N-1}) & \longmapsto &
\r
474 (\overline{b_0},\cdots,\overline{b_\mathsf{N-1}})\\
\r
478 %\begin{definition}[Vectorial Negation]\label{Def:vectorial-negation}
\r
480 %\begin{array}{cccc}
\r
481 %f_0\ :\ & \mathbb{B}^N & \longrightarrow & \mathbb{B}^N \\
\r
482 %& (b_1,\cdots,b_\mathsf{N}) & \longmapsto &
\r
483 %(\overline{b_1},\cdots,\overline{b_\mathsf{N}})\\
\r
487 %It is then checked in \cite{bg10:ij} that i
\r
488 In the metric space $(\mathcal{X}_1,d_1)$, $G_{f_0}$ satisfies the three
\r
489 conditions for Devaney's chaos: regularity, transitivity, and
\r
490 sensibility to the initial condition. %~\cite{bg10:ij}.
\r
493 %the following result.
\r
494 \begin{theorem}%[$G_{f_0}$ is a chaotic map]
\r
495 $G_{f_0}$ is a chaotic map on $(\mathcal{X}_1,d_1)$ according to the Devaney's formulation.
\r
499 \section{A First CIs Watermarking Process called $CI_1$}
\r
500 \label{section:IH based on CIs}
\r
504 In this section is explained how CIs can be used as an information hiding scheme.
\r
506 \subsection{Most and Least Significant Coefficients}\label{sec:msc-lsc}
\r
510 We first take into account the fact that, in a watermarking process, terms of the original content $x$ that may be replaced by terms issued
\r
511 from the watermark $y$ are less important than other: they could be changed
\r
512 without be perceived as such. More generally, a
\r
513 \emph{signification function}
\r
514 attaches a weight to each term defining a digital media,
\r
515 depending on its position $t$ \cite{todo}.
\r
517 \begin{definition}[Signification function]
\r
518 A \emph{signification function} is a real sequence
\r
519 $(u^k)^{k \in \mathds{N}}$. % with a limit equal to 0.
\r
523 \begin{example}\label{Exemple LSC}
\r
524 Let us consider a set of
\r
525 grayscale images stored into portable graymap format (P3-PGM):
\r
526 each pixel ranges between 256 gray levels, \textit{i.e.},
\r
527 is memorized with eight bits.
\r
528 In that context, we consider
\r
529 $u^k = 8 - (k \mod 8)$ to be the $k$-th term of a signification function
\r
530 $(u^k)^{k \in \mathds{N}}$.
\r
531 Intuitively, in each group of eight bits (\textit{i.e.}, for each pixel)
\r
532 the first bit has an importance equal to 8, whereas the last bit has an
\r
533 importance equal to 1. This is compliant with the idea that
\r
534 changing the first bit affects more the image than changing the last one.
\r
537 \begin{definition}[Significance of coefficients]
\r
538 \label{def:msc,lsc}
\r
539 Let $(u^k)^{k \in \mathds{N}}$ be a signification function,
\r
540 $m$ and $M$ be two reals s.t. $m < M$.
\r
542 \item The \emph{most significant coefficients (MSCs)} of $x$ is the finite
\r
543 vector $$u_M = \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k
\r
544 \geqslant M \textrm{ and } k \le \mid x \mid \right);$$
\r
545 \item The \emph{least significant coefficients (LSCs)} of $x$ is the
\r
547 $$u_m = \left( k ~ \big|~ k \in \mathds{N} \textrm{ and } u^k
\r
548 \le m \textrm{ and } k \le \mid x \mid \right);$$
\r
549 \item The \emph{passive coefficients} of $x$ is the finite vector
\r
550 $$u_p = \left( k ~ \big|~ k \in \mathds{N} \textrm{ and }
\r
551 u^k \in ]m;M[ \textrm{ and } k \le \mid x \mid \right).$$
\r
555 For a given host content $x$,
\r
556 MSCs are then ranks of $x$ that describe the relevant part
\r
557 of the image, whereas LSCs translate its less significant parts.
\r
558 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$.
\r
560 \begin{figure*}[htb]
\r
563 \begin{minipage}[b]{.98\linewidth}
\r
565 \centerline{\includegraphics[width=6.cm]{img/lena512}}
\r
566 %\centerline{\epsfig{figure=img/lena512.pdf,width=4cm}}
\r
567 \centerline{(a) Original Lena.}
\r
569 \begin{minipage}[b]{.49\linewidth}
\r
571 \centerline{\includegraphics[width=6.cm]{img/lena_msb_678}}
\r
572 %\centerline{\epsfig{figure=img/lena_msb_678.pdf,width=4cm}}
\r
573 \centerline{(b) MSCs of Lena.}
\r
576 \begin{minipage}[b]{0.49\linewidth}
\r
578 \centerline{\includegraphics[width=6.cm]{img/lena_lsb_1234_facteur17}}
\r
580 %\centerline{\epsfig{figure=img/lena_lsb_1234_facteur17.pdf,width=4cm}}
\r
581 \centerline{(c) LSCs of Lena ($\times 17$).}
\r
584 \caption{Most and least significant coefficients of Lena.}
\r
599 \subsection{Presentation of the Scheme}
\r
601 We have proposed in \cite{guyeux10ter} to use chaotic iterations as an information hiding scheme, as follows.
\r
604 \item $(K,N) \in [0;1]\times \mathds{N}$ be an embedding key,
\r
605 \item $X \in \mathbb{B}^\mathsf{N}$ be the $\mathsf{N}$ LSCs of a cover $C$,% $X$ be the initial state $X_0$,
\r
606 \item $(S^n)_{n \in \mathds{N}} \in \llbracket 0, \mathsf{N-1}
\r
607 \rrbracket^{\mathds{N}}$ be a strategy, which depends on the message to hide $M \in [0;1]$ and $K$,
\r
608 \item $f_0 : \mathbb{B}^\mathsf{N} \rightarrow \mathbb{B}^\mathsf{N}$ be the vectorial logical negation.
\r
612 So the watermarked media is $C$ whose LSCs are replaced by $Y_K=X^{N}$, where:
\r
618 \forall n < N, X^{n+1} = G_{f_0}\left(X^n\right).\\
\r
619 \end{array} \right.
\r
623 Two ways to generate $(S^n)_{n \in \mathds{N}}$ are given in \cite{trx}, namely
\r
624 Chaotic Iterations with Independent Strategy~(CIIS) and Chaotic Iterations with Dependent
\r
626 In CIIS, the strategy is independent from the cover media $C$, whereas in CIDS the strategy will be dependent on $C$.
\r
630 \subsection{CIIS Strategy}
\r
631 \label{CIIS strategy}
\r
632 Let us firstly give the definition of the Piecewise Linear Chaotic Map~(PLCM, see~\cite{Shujun1}):
\r
634 %\begin{definition}%[PLCM]
\r
635 %The \emph{Piecewise Linear Chaotic Map} is defined by
\r
639 x/p & \text{if} & x \in [0;p], \\
\r
640 (x-p)/(\frac{1}{2} - p) & \text{if} & x \in \left[ p; \frac{1}{2} \right],
\r
642 F(1-x,p) & \text{else,} & \\
\r
643 \end{array} \right.
\r
648 \noindent where $p \in \left] 0; \frac{1}{2} \right[$ is a ``control parameter''.
\r
650 The general term of the strategy $(S^n)_n$ in CIIS setup is defined by
\r
651 the following expression: $S^n = \left \lfloor \mathsf{N} \times K^n \right \rfloor +
\r
657 p \in \left[ 0 ; \frac{1}{2} \right] \\
\r
658 K^0 = M \otimes K\\
\r
659 K^{n+1} = F(K^n,p), \forall n \leq N_0, \end{array} \right.
\r
664 \noindent in which $\otimes$ denotes the bitwise exclusive or (XOR) between two floating part numbers (\emph{i.e.}, between their binary digits representations).
\r
667 \subsection{CIDS Strategy}
\r
669 The same notations as above are used.
\r
670 We define CIDS strategy as follows: $\forall k \leqslant N$,
\r
672 \item if $k \leqslant \mathsf{N}$ and $X^k = 1$, then $S^k=k$,
\r
673 \item else $S^k=1$.
\r
675 In this situation, if $N \geqslant \mathsf{N}$, then only two watermarked contents are possible with the information hiding scheme proposed previously, namely: $Y_K=(0,0,\cdots,0)$ and $Y_K=(1,0,\cdots,0)$.
\r
678 \subsection{PSNR evaluation}\label{section:psnr-ci-1}
\r
680 To realize the evaluation of the PSNR of $CI_1$, we have used the same
\r
681 architecture as described in
\r
682 Section~\ref{section:architecture-presentation}~\vpageref{section:architecture-presentation}.
\r
684 It has to be noted that in the $CI_1$ watermarking process, the embedding key
\r
685 correspond to the strategy associated to the number of iterations.
\r
687 Executing the $CI_1$ process on 1000 images, on the one hand with a constant
\r
688 embedding key and one the other hand with a key generated randomly we have
\r
689 obtain the results described in the
\r
690 table~\ref{table:psnr-ci1}~\vpageref{table:psnr-ci1}, an average of and a standard deviation of has been obtained for the PSNR.\newline
\r
697 \begin{tabular}{|c||c|c|c|}
\r
699 \textbf{Strategies} & \textbf{PSNR: average} & \textbf{PSNR: standard
\r
703 \textbf{Constant strategy} & $21.6653$ & $0.03604$ \\
\r
705 \textbf{Random strategy} & $13.3909$ & $10.5690$ \\
\r
710 \caption{PSNR evaluation of the $CI_1$ process (tests on 1000 images).}
\r
712 \label{table:psnr-ci1}
\r
715 Let us now focus on some security aspects of information hiding schemes. In particular, we aim to explain why chaos is relevant in this field.
\r
717 \section{Information hiding security: $CI_1$}
\r
718 \label{section:IH-security}
\r
720 \subsection{Classification of Attacks}\label{sec:attack-classes}
\r
722 In the steganography framework, attacks have been classified
\r
723 in~\cite{Cayre2008} as follows.
\r
727 Watermark-Only Attack (WOA) occurs when an attacker has only access to several watermarked contents.
\r
731 Known-Message Attack (KMA) occurs when an attacker has access to several pairs of watermarked contents and
\r
732 corresponding hidden messages.
\r
736 Known-Original Attack (KOA) is when an attacker has access to several pairs of watermarked contents and
\r
737 their corresponding original versions.
\r
741 Constant-Message Attack (CMA) occurs when the attacker observes several watermarked contents and only knows that the
\r
742 unknown hidden message is the same in all contents.
\r
745 The synthesis of this classification is illustrated in the
\r
746 Table~\ref{table:attack-classification}~\vpageref{table:attack-classification}.
\r
752 \begin{tabular}{|c||c|c|c|}
\r
754 \textbf{Attacks} & \textbf{Original content} & \textbf{Stego
\r
755 content} & \textbf{Hidden message}\\
\r
758 \textbf{Watermark-Only Attack} & & $\times$ & \\
\r
760 \textbf{Known-Message Attack} & & $\times$ & $\times$ \\
\r
762 \textbf{ Kown-Original Attack} & $\times$ & $\times$ & \\
\r
764 \textbf{Constant-Message Attack} & & & $\times$ \\
\r
767 \caption{Attacks in Kalker's context~\cite{Kalker2001}}
\r
769 \label{table:attack-classification}
\r
773 \subsection{Stego-Security of $CI_1$}\label{sec:stego-security}
\r
775 In the prisoner problem of Simmons~\cite{Simmons83,DBLP:conf/ih/BergmairK06}
\r
777 Figure~\ref{fig:simmons-prisonner-problem}~\vpageref{fig:simmons-prisonner-problem}, Alice and Bob are in jail, and they want to, possibly, devise an escape plan by exchanging hidden messages in innocent-looking cover contents. These messages are to be conveyed to one another by a common warden, Eve, who over-drops all contents and can choose to interrupt the communication if they appear to be stego-contents.
\r
781 %\includegraphics[width=10.5cm]{./img/prisoner-problem.png}
\r
782 \includegraphics[width=15cm]{./img/prisoner-problem}
\r
784 \caption{Simmons' prisoner problem~\cite{Simmons83}}
\r
785 \label{fig:simmons-prisonner-problem}
\r
788 The stego-security, defined in this
\r
789 framework, is the highest security level in WOA setup~\cite{Cayre2008}.
\r
790 To recall it, we need the following notations:
\r
792 \item $\mathds{K}$ is the set of embedding keys,
\r
793 \item $p(X)$ is the probabilistic model of $N_0$ initial host contents,
\r
794 \item $p(Y|K_1)$ is the probabilistic model of $N_0$ watermarked contents.
\r
797 Furthermore, it is supposed in this context that each host content has been watermarked with the same secret key $K_1$ and the same embedding function $e$.
\r
800 It is now possible to define the notion of stego-security:
\r
802 \begin{definition}[Stego-Security]
\r
803 \label{Def:Stego-security}
\r
804 The embedding function $e$ is \emph{stego-secure} if and only if:
\r
805 $$\forall K_1 \in \mathds{K}, p(Y|K_1)=p(X).$$
\r
808 To the best of our knowledge, until now, only two schemes have been proven to be stego-secure.
\r
809 On the one hand, the authors of \cite{Cayre2008} have established that the spread spectrum technique called Natural Watermarking is stego-secure when its distortion parameter $\eta$ is equal to $1$.
\r
810 On the other hand, it has been proven in~\cite{gfb10:ip} that:
\r
812 \begin{proposition}
\r
813 Chaotic Iterations with Independent Strategy (CIIS) are stego-secure.
\r
814 \label{prop:CIIS-stego-security}
\r
820 Let us suppose that $X \sim
\r
821 \mathbf{U}\left(\mathbb{B}^N\right)$ in a CIIS setup.
\r
822 We will prove by a mathematical induction that $\forall n \in \mathds{N}, X^n \sim
\r
823 \mathbf{U}\left(\mathbb{B}^N\right)$. The base case is immediate, as $X^0 = X \sim
\r
824 \mathbf{U}\left(\mathbb{B}^N\right)$. Let us now suppose that the statement
\r
826 \mathbf{U}\left(\mathbb{B}^N\right)$ holds for some $n$.
\r
827 Let $e \in \mathbb{B}^N$ and $\mathbf{B}_k=(0,\cdots,0,1,0,\cdots,0) \in \mathbb{B}^N$ (the digit $1$ is in position $k$).
\r
829 So $P\left(X^{n+1}=e\right)=\sum_{k=1}^N
\r
830 P\left(X^n=e+\mathbf{B}_k,S^n=k\right).$
\r
832 These two events are independent in CIIS setup, thus:
\r
834 $P\left(X^{n+1}=e\right)=\sum_{k=1}^N
\r
835 P\left(X^n=e+\mathbf{B}_k\right) \times P\left(S^n=k\right)$.
\r
837 %According to the recurrence hypothesis ($X^n \sim
\r
838 %\mathbf{U}\left(\mathbb{B}^N\right)$):
\r
839 According to the inductive hypothesis:
\r
842 %P\left(X^{n+1}=e\right) & =\sum_{k=1}^N
\r
843 %\frac{1}{2^N} \times P\left(S^n=k\right) \\
\r
844 %& =\frac{1}{2^N} \sum_{k=1}^N
\r
845 % P\left(S^n=k\right)\\
\r
849 $P\left(X^{n+1}=e\right)=\frac{1}{2^N} \sum_{k=1}^N
\r
850 P\left(S^n=k\right)$.
\r
852 The set of events $\left \{ S^n=k \right \}$ for $k \in \llbracket 1;N
\r
853 \rrbracket$ is a partition of the universe of possible, so
\r
854 $\sum_{k=1}^N P\left(S^n=k\right)=1$.
\r
856 %Evaluate now $ P\left(S^n=k\right)$.
\r
858 %We have: $K^0 = M \otimes K \sim
\r
859 %\mathbf{U}\left([0;1]\right)$, so $K^\prime=F\left( K^0,p \right) \sim
\r
860 %\mathbf{U}\left([0;1]\right)$, because for PLCMs, ``Uniform input generate
\r
861 %uniform output''~\cite{Lasota}.
\r
862 %Well with an immediate proof by recurrence we have:
\r
863 %$K^n \sim \mathbf{U}\left([0;1]\right)$. As $S^n = \left \lfloor N \times X^n
\r
864 %\right \rfloor + 1$ we can deduce that: $S^n \sim
\r
865 %\mathbf{U}\left([1;N]\right)$. Therefore: $ P\left(S^n=k\right)=\frac{1}{N}$.
\r
868 %\begin{array}{llr}
\r
869 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
\r
870 % P\left(S^n=k\right) & \\
\r
871 % & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} & \\
\r
872 % & =\frac{1}{2^N} & \\
\r
876 %$\begin{array}{llr}
\r
877 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
\r
878 % P\left(S^n=k\right) & \\
\r
879 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} &
\r
880 % =\frac{1}{2^N} \\
\r
882 $P\left(X^{n+1}=e\right)=\frac{1}{2^N}$, which leads to $X^{n+1} \sim
\r
883 \mathbf{U}\left(\mathbb{B}^N\right)$.
\r
884 This result is true $\forall n \in \mathds{N}$, we thus have proven that, $$\forall K \in [0;1], Y_K=X^{N_0} \sim
\r
885 \mathbf{U}\left(\mathbb{B}^N\right) \text{ when } X \sim
\r
886 \mathbf{U}\left(\mathbb{B}^N\right)$$
\r
890 Section~\ref{CIIS strategy} are stego-secure.
\r
893 We will now prove that,
\r
895 \begin{proposition}
\r
897 Chaotic Iterations with Dependent Strategy (CIDS) are not stego-secure.
\r
901 Due to the definition of CIDS, we have $P(Y_K=(1,1,\cdots,1))=0$. So there is
\r
902 no uniform repartition for the stego-contents $Y_K$.
\r
911 \subsection{Chaos-Security of the $CI_1$ scheme}\label{sec:chaos-security}
\r
913 To check whether an information hiding scheme $S$ is chaos-secure or not, $S$
\r
914 must be written as an iterate process $x^{n+1}=f(x^n)$ on a metric space
\r
915 $(\mathcal{X},d)$. This formulation is always possible~\cite{ih10}. So,
\r
918 \begin{definition}[Chaos-Security]
\r
919 \label{Def:chaos-security-definition}
\r
920 An information hiding scheme $S$ is said to be chaos-secure on
\r
921 $(\mathcal{X},d)$ if its iterative process has a chaotic
\r
922 behavior according to Devaney.
\r
925 In the approach presented by Guyeux \emph{et al.}, a data hiding scheme is secure if it is unpredictable.
\r
926 Its iterative process must satisfy the Devaney's chaos property and its level of chaos-security increases with the number of chaotic properties satisfied by it.
\r
928 This new concept of security for data hiding schemes has been proposed in~\cite{ih10} as a complementary approach to the existing framework.
\r
929 It contributes to the reinforcement of confidence into existing secure data hiding schemes.
\r
930 Additionally, the study of security in KMA, KOA, and CMA setups is realizable in this context.
\r
931 Finally, this framework can replace stego-security in situations that are not encompassed by it.
\r
932 In particular, this framework is more relevant to give evaluation of data hiding schemes claimed as chaotic.
\r
937 We can establish that,
\r
939 \begin{proposition}
\r
941 CIIS and CIDS are chaos-secure.
\r
945 It is due to the fact that chaotic iterations have a chaotic behavior, as defined by Devaney.
\r
950 In the two following sections, we will study the qualitative and quantitative
\r
951 properties of chaos-security for chaotic iterations. These properties can measure the
\r
952 disorder generated by our scheme, giving by doing so some important informations about the
\r
953 unpredictability level of such a process.
\r
955 \subsection{Quantitative property of
\r
956 chaotic iterations}\label{sec:chaos-security-quantitative}
\r
958 \begin{definition}[Expansivity]
\r
959 A function $f$ is said to be \emph{expansive} if $
\r
960 \exists \varepsilon >0,\forall x\neq y,\exists n\in \mathds{N}%
\r
961 ,d(f^{n}(x),f^{n}(y))\geqslant \varepsilon .$
\r
964 \begin{proposition}
\r
965 $G_{f_{0}}$ is an expansive chaotic dynamical system on $\mathcal{X}$ with a constant of expansivity is equal to 1.
\r
968 If $(S,E)\neq (\check{S};\check{E})$, then either $E\neq \check{E}$, so at least
\r
969 one cell is not in the same state in $E$ and $\check{E}$. Consequently the distance between $(S,E)$ and $(%
\r
970 \check{S};\check{E})$ is greater or equal to 1. Or $E=\check{E}$. So the
\r
971 strategies $S$ and $\check{S}$ are not equal. Let $n_{0}$ be the first index in which the terms $S$ and $\check{S}$
\r
974 k<n_{0},\tilde{G}_{f_{0}}^{k}(S,E)=\tilde{G}_{f_{0}}^{k}(\check{S},\check{E})$,
\r
975 and $\tilde{G}_{f_{0}}^{n_{0}}(S,E)\neq \tilde{G}_{f_{0}}^{n_{0}}(\check{S},\check{E})$. As $E=\check{E},$ the cell which has changed in $E$ at the $n_{0}$-th
\r
976 iterate is not the same as the cell which has changed in $\check{E}$, so
\r
977 the distance between $\tilde{G}_{f_{0}}^{n_{0}}(S,E)$ and $\tilde{G}_{f_{0}}^{n_{0}}(\check{S%
\r
978 },\check{E})$ is greater or equal to 2.
\r
981 \subsection{Qualitative property of
\r
982 chaotic iterations}\label{sec:chaos-security-qualitative}
\r
984 \begin{definition}[Topological mixing]
\r
985 A discrete dynamical system is said to be topologically mixing
\r
986 if and only if, for any couple of disjoint open set $U, V \neq \varnothing$,
\r
987 $n_0 \in \mathds{N}$ can be found so that $\forall n \geqslant n_0, f^n(U) \cap
\r
988 V \neq \varnothing$.
\r
990 \begin{proposition}
\r
991 $\tilde{G}_{f_0}$ is topologically mixing on $(\mathcal{X}', d')$.
\r
994 This result is an immediate consequence of the lemma below.
\r
997 For any open ball $B$ of $\mathcal{X}'$, an index $n$ can be found such that $\tilde{G}_{f_0}^n(B) = \mathcal{X}'$.
\r
1001 Let $B=B((E,S),\varepsilon)$ be an open ball, which the radius can be considered as strictly less than 1.
\r
1002 All the elements of $B$ have the same state $E$ and are such that an integer $k \left(=-\log_{10}(\varepsilon)\right)$ satisfies:
\r
1004 \item all the strategies of $B$ have the same $k$ first terms,
\r
1005 \item after the index $k$, all values are possible.
\r
1008 Then, after $k$ iterations, the new state of the system is $\tilde{G}_{f_0}^k(E,S)_1$ and all the strategies are possible (all the points $(\tilde{G}_{f_0}^k(E,S)_1,\textrm{\^{S}})$, with any $\textrm{\^{S}} \in \mathbb{S}$, are reachable from $B$).
\r
1010 We will prove that all points of $\mathcal{X}'$ are reachable from $B$. Let
\r
1011 $(E',S') \in \mathcal{X}'$ and $s_i$ be the list of the different cells between
\r
1012 $\tilde{G}_{f_0}^k(E,S)_1$ and $E'$. We denote by $|s|$ the size of the sequence
\r
1013 $s_i$. So the point $(\check{E},\check{S})$ of $B$ defined by: $\check{E} = E$,
\r
1014 $\check{S}^i = S^i, \forall i \leqslant k$, $\check{S}^{k+i} = s_i, \forall i
\r
1015 \leqslant |s|$, and $\forall i \in \mathds{N}, S^{k + |s| + i} = S'^i$
\r
1016 is such that $\tilde{G}_{f_0}^{k+|s|}(\check{E},\check{S}) = (E',S')$. This concludes the proofs of the lemma and of the proposition.
\r
1021 \subsection{Comparison between spread-spectrum and chaotic iterations}\label{sec:comparison-application-context}
\r
1023 The consequences of topological mixing for data hiding are multiple. Firstly,
\r
1024 security can be largely improved by considering
\r
1025 the number of iterations as a secret key. An attacker
\r
1026 will reach all of the possible media when iterating without this key.
\r
1027 Additionally, he cannot benefit from a KOA setup, by studying media in the
\r
1028 neighborhood of the original cover. Moreover, as in a topological mixing
\r
1029 situation, it is possible that any hidden message (the initial condition), is
\r
1030 sent to the same fixed watermarked content (with different numbers of
\r
1031 iterations), the interest to be in a KMA setup is drastically reduced. Lastly, as
\r
1032 all of the watermarked contents are possible for a given hidden message, depending
\r
1033 on the number of iterations, CMA attacks will fail.
\r
1036 %Already corrected
\r
1037 The property of expansivity reinforces drastically the sensitivity in the aims of
\r
1038 reducing the benefits that Eve can obtain from an attack in KMA or KOA setup. For
\r
1039 example, it is impossible to have an estimation of the watermark by moving the
\r
1040 message (or the cover) as a cursor in situation of expansivity: this cursor will
\r
1041 be too much sensitive and the changes will be too important to be useful. On the
\r
1042 contrary, a very large constant of expansivity $\varepsilon$ is unsuitable: the
\r
1043 cover media will be strongly altered whereas the watermark would be undetectable.
\r
1046 % %Indeed, let us consider the same cover $E$ twice with two different watermarks
\r
1047 % $S,S'$. Thus $d(X,Y) < 1$, where $X=(E,S), Y=(E,S')$ and $d$ is for the distance
\r
1048 % previously defined. However, due to expansivity, $\exists n \in \mathds{N},
\r
1049 % d\left(G^n (X) ; G^n (Y) \right) \geqslant \varepsilon.$ Thus, $d_\infty
\r
1050 % \left(G^n (X)_1 ; G^n (Y)_1 \right) \geqslant \varepsilon - 1$, so either
\r
1051 % $d_\infty \left(X_1 ; G^n (X)_1 \right) \geqslant \dfrac{\varepsilon - 1}{2}$, or
\r
1052 % $d_\infty \left(Y_1 ; G^n (Y)_1 \right) \geqslant \dfrac{\varepsilon - 1}{2}$. If
\r
1053 % $\varepsilon$ is large, then at least one of the two watermarked media will be
\r
1054 % very different than its original cover.
\r
1056 Finally, spread-spectrum is relevant when
\r
1057 a discrete and secure data hiding technique is required in WOA setup. However,
\r
1058 this technique should not be used in KOA and KMA setup, due to its lack of
\r
1059 expansivity.% In the next section, we will present a new class of data hiding
\r
1060 schemes, which are expansive.
\r
1063 \section{Study of robustness: $CI_1$}\label{section:robustness-ci-1}
\r
1065 \subsection{Presentation of the architecture}\label{section:architecture-presentation}
\r
1067 In what follows, computations have been
\r
1068 performed on the supercomputer facilities of the M\'{e}socentre de calcul de Franche-Comt\'{e}.
\r
1070 In order to take benefits of parallelism, we have used Jace \cite{bhm09:ip}, a grid-enabled programming and execution
\r
1071 environment allowing a simple and efficient implementation
\r
1072 of parallel and distributed applications. Roughly speaking, Jace builds a virtual parallel machine by
\r
1073 connecting a set of heterogeneous and distant computers.
\r
1074 It schedules tasks, executes them, and returns results to the user. It
\r
1075 also proposes a simple programming interface for the implementation of applications
\r
1076 using a message passing model.
\r
1078 In our case, tasks are independent Python programs with different parameters. Jace takes care to execute them in parallel ensuring optimal load balancing and fault tolerance.
\r
1080 For these experiments we have used HPC resources
\r
1081 from M\'{e}socentre of Franche-Comt\'{e}. This platform
\r
1082 is currently composed of 720 cores with 11 TeraFLOPS of power.
\r
1083 The different tests have been realized on several images taken from the Wikimedia Commons repository~\cite{wiki:wikimedia-commons}.
\r
1084 The configurations of all tests are embedded into each graph caption.
\r
1086 %je ne sais pas comment expliquer vos configs !
\r
1087 %In the following experiments, we have chosen different configuration files,
\r
1088 %about 1000 images from wikimedia.....
\r
1092 \subsection{Concerning Tests}\label{sec:tests-realized-ci-1}
\r
1094 In this section, we intend to study the robustness of the $CI_1$ watermarking process.
\r
1095 To achieve this goal, two batteries of tests have been executed.
\r
1097 In the first battery, we have used the same embedding key, thus a constant strategy has been used.
\r
1098 In the second battery, random strategies have been used, in order to show the influence of the embedding key on robustness.
\r
1099 The objective of these tests is to evaluate the correlation linking the parameters of some given geometrical attacks on the one hand, and the bits difference rate between the original watermark and its extracted version after attacks on the other hand.
\r
1100 A fixed strategy is then used in these tests.
\r
1102 The following results have been obtained by using a large number of attacks on 600 images.
\r
1103 For each category of attacks, two graphs have been plotted: the first one is about averages, when the second one is for the standard deviation.
\r
1104 These graphs help to determine the threshold leading to the acceptation/rejection of a possibly watermarked media.
\r
1107 \subsection{Tests results}\label{sec:tests-results-ci-1}
\r
1109 The exhaustive list of the geometrical attacks tested and the
\r
1110 corresponding graphs results is following:
\r
1113 \item \textbf{Robustness facing a resizing attack.}\\
\r
1114 See Figure~\ref{fig:resizing-attack-constant-strategy}~\vpageref{fig:resizing-attack-constant-strategy}.
\r
1115 \item \textbf{Robustness facing a JPEG compression
\r
1117 Figure~\ref{fig:jpeg-attack-constant-strategy}~\vpageref{fig:jpeg-attack-constant-strategy}.
\r
1118 \item \textbf{Robustness facing a Gaussian blur
\r
1120 Figure~\ref{fig:gaussian-blur-attack-constant-strategy}~\vpageref{fig:gaussian-blur-attack-constant-strategy}.
\r
1121 \item \textbf{Robustness facing a rotation
\r
1123 Figure~\ref{fig:rotation-attack-constant-strategy}~\vpageref{fig:rotation-attack-constant-strategy}.
\r
1124 \item \textbf{Robustness facing a blur
\r
1126 Figure~\ref{fig:blur-attack-constant-strategy}~\vpageref{fig:blur-attack-constant-strategy}.
\r
1127 \item \textbf{Robustness facing a contrast
\r
1129 Figure~\ref{fig:contrast-attack-constant-strategy}~\vpageref{fig:contrast-attack-constant-strategy}.
\r
1130 \item \textbf{Robustness facing a cropping
\r
1132 Figure~\ref{fig:cropping-attack-constant-strategy}~\vpageref{fig:cropping-attack-constant-strategy}.
\r
1138 % %\includegraphics[width=10.5cm]{./img/prisoner-problem.png}
\r
1139 % \includegraphics[width=15cm]{./img/prisoner-problem}
\r
1142 % \caption{Simmons' prisoner problem~\cite{Simmons83}}
\r
1146 \begin{figure*}[htb]
\r
1147 \begin{minipage}[b]{.45\linewidth}
\r
1149 \centerline{\includegraphics[width=9cm]{graphs/graph_1_attack=redimensionnement-average}}
\r
1150 \centerline{(a) Average}
\r
1153 \begin{minipage}[b]{0.45\linewidth}
\r
1155 \centerline{\includegraphics[width=9cm]{graphs/graph_1_attack=redimensionnement-sd}}
\r
1156 \centerline{(b) Standard deviation}
\r
1158 \caption{Robustness of $CI_1$ facing a resizing attack.(600 images and constant strategy)}
\r
1159 \label{fig:resizing-attack-constant-strategy}
\r
1162 \begin{figure*}[htb]
\r
1163 \begin{minipage}[b]{.45\linewidth}
\r
1165 \centerline{\includegraphics[width=9cm]{graphs/graph_2_attack=jpeg-average}}
\r
1166 \centerline{(a) Average}
\r
1169 \begin{minipage}[b]{0.45\linewidth}
\r
1171 \centerline{\includegraphics[width=9cm]{graphs/graph_2_attack=jpeg-sd}}
\r
1172 \centerline{(b) Standard deviation}
\r
1174 \caption{Robustness of $CI_1$ facing a JPEG compression attack.(600 images and
\r
1175 constant strategy)}
\r
1176 \label{fig:jpeg-attack-constant-strategy}
\r
1180 \begin{figure*}[htb]
\r
1181 \begin{minipage}[b]{.45\linewidth}
\r
1183 \centerline{\includegraphics[width=9cm]{graphs/graph_3_attack=gaussien-average}}
\r
1184 \centerline{(a) Average}
\r
1187 \begin{minipage}[b]{0.45\linewidth}
\r
1189 \centerline{\includegraphics[width=9cm]{graphs/graph_3_attack=gaussien-sd}}
\r
1190 \centerline{(b) Standard deviation}
\r
1192 \caption{Robustness of $CI_1$ facing a Gaussian blur attack.(600 images and
\r
1193 constant strategy)}
\r
1194 \label{fig:gaussian-blur-attack-constant-strategy}
\r
1197 \begin{figure*}[htb]
\r
1198 \begin{minipage}[b]{.45\linewidth}
\r
1200 \centerline{\includegraphics[width=9cm]{graphs/graph_4_attack=rotation-average}}
\r
1201 \centerline{(a) Average}
\r
1204 \begin{minipage}[b]{0.45\linewidth}
\r
1206 \centerline{\includegraphics[width=9cm]{graphs/graph_4_attack=rotation-sd}}
\r
1207 \centerline{(b) Standard deviation}
\r
1209 \caption{Robustness of $CI_1$ facing a rotation attack.(600 images and constant
\r
1211 \label{fig:rotation-attack-constant-strategy}
\r
1215 \begin{figure*}[htb]
\r
1216 \begin{minipage}[b]{.45\linewidth}
\r
1218 \centerline{\includegraphics[width=9cm]{graphs/graph_5_attack=flou-average}}
\r
1219 \centerline{(a) Average}
\r
1222 \begin{minipage}[b]{0.45\linewidth}
\r
1224 \centerline{\includegraphics[width=9cm]{graphs/graph_5_attack=flou-sd}}
\r
1225 \centerline{(b) Standard deviation}
\r
1227 \caption{Robustness of $CI_1$ facing a blur attack.(600 images and constant
\r
1229 \label{fig:blur-attack-constant-strategy}
\r
1233 \begin{figure*}[htb]
\r
1234 \begin{minipage}[b]{.45\linewidth}
\r
1236 \centerline{\includegraphics[width=9cm]{graphs/graph_6_attack=contraste-average}}
\r
1237 \centerline{(a) Average}
\r
1240 \begin{minipage}[b]{0.45\linewidth}
\r
1242 \centerline{\includegraphics[width=9cm]{graphs/graph_6_attack=contraste-sd}}
\r
1243 \centerline{(b) Standard deviation}
\r
1245 \caption{Robustness of $CI_1$ facing a contrast attack.(600 images and constant
\r
1247 \label{fig:contrast-attack-constant-strategy}
\r
1251 \begin{figure*}[htb]
\r
1252 \begin{minipage}[b]{.45\linewidth}
\r
1254 \centerline{\includegraphics[width=9cm]{graphs/graph_7_attack=decoupage-average}}
\r
1255 \centerline{(a) Average}
\r
1258 \begin{minipage}[b]{0.45\linewidth}
\r
1260 \centerline{\includegraphics[width=9cm]{graphs/graph_7_attack=decoupage-sd}}
\r
1261 \centerline{(b) Standard deviation}
\r
1263 \caption{Robustness of $CI_1$ facing a cropping attack.(600 images and constant
\r
1265 \label{fig:cropping-attack-constant-strategy}
\r
1268 \subsection{Robustness evaluation}\label{sec:tests-results-ci-1}
\r
1270 From the results presented in the previous section, the robustness of the
\r
1271 process $CI_1$ can be evaluated.
\r
1273 \textbf{TODO: The interpretation which can be given of the robustness tests is
\r
1278 To conclude, at this point, only two information hiding schemes are both stego-secure and chaos-secure \cite{gfb10:ip}.
\r
1279 The first one is based on a spread spectrum technique called Natural Watermarking.
\r
1280 It is stego-secure when its parameter $\eta$ is equal to $1$ \cite{Cayre2008}.
\r
1281 Unfortunately, this scheme is neither robust, nor able to face an attacker in KOA and KMA setups, due to its lack of a topological property called expansivity \cite{gfb10:ip}.
\r
1282 The second scheme both chaos-secure and stego-secure is based on chaotic iterations \cite{guyeux10ter}.
\r
1283 However, its first versions called $CI_1$ allows to embed securely only one bit per embedding parameters.
\r
1284 The objective of the next sections is to improve the $CI_1$ scheme presented in \cite{guyeux10ter}, in such a way that more than one bit can be embedded.
\r
1287 \section{Improved process for steganography: $CI_2$}
\r
1288 \label{section:process-ci2}
\r
1290 \noindent In this section is given a new algorithm that generalize the
\r
1291 $CI_1$ scheme presented above.
\r
1293 Let us firstly introduce the following notations:
\r
1295 \subsection{Notations}
\r
1297 %\item Let $\mathbb{S}_k=\llbracket 0, \mathsf{k-1} \rrbracket^{\mathds{N}}$ be
\r
1298 %the set of all strategies with values in $\llbracket 0, \mathsf{k-1}
\r
1300 \item $x^0 \in \mathbb{B}^\mathsf{N}$ is the $\mathsf{N}$ least
\r
1301 significant coefficients of a given cover media $C$.% $X$ be the initial state $X_0$,
\r
1302 %\item The vectorial negation $f_0$ (defined in~\ref{Def:vectorial-negation})
\r
1303 %as iteration function.
\r
1304 \item $m^0 \in \mathbb{B}^\mathsf{P}$ is the watermark to embed into $x^0$.
\r
1305 \item $S_1 \in \mathbb{S}_N$ is a strategy called \textbf{place strategy}.
\r
1306 \item $S_2 \in \mathbb{S}_P$ is a strategy called \textbf{choice strategy}.
\r
1307 \item Lastly, $S_3 \in \mathbb{S}_P$ is a strategy called \textbf{mixing strategy}.
\r
1310 %\subsection{Algorithm SCISMM in details}\label{sec:algo-SCISMM}
\r
1312 \subsection{Presentation of the scheme}
\r
1314 Our information hiding scheme called Steganography by Chaotic Iterations and
\r
1315 Substitution with Mixing Message (SCISMM) is defined by
\r
1316 %\begin{definition}[SCISMM]\label{def:algo}
\r
1317 $\forall (n,i,j) \in
\r
1318 \mathds{N}^{\ast} \times \llbracket 0;\mathsf{N-1}\rrbracket \times \llbracket
\r
1319 0;\mathsf{P-1}\rrbracket$:
\r
1326 x_i^{n-1} & \text{ if }S_1^n\neq i \\
\r
1327 m_{S_2^n} & \text{ if }S_1^n=i.
\r
1334 m_j^{n-1} & \text{ if }S_3^n\neq j \\
\r
1336 \overline{m_j^{n-1}} & \text{ if }S_3^n=j.
\r
1343 where $\overline{m_j^{n-1}}$ is the boolean negation of $m_j^{n-1}$.
\r
1344 %\subsection{Stego-content by SCISMM}\label{sec:stego-content}
\r
1346 The stego-content is the boolean vector $y = x^P \in
\r
1347 \mathbb{B}^\mathsf{N}$.
\r
1350 \section{Study of security of $CI_2$}
\r
1352 \subsection{Study of stego-security}\label{sec:stego-security-ci-2}
\r
1355 \noindent Let us prove that,
\r
1357 \begin{proposition}
\r
1358 SCISMM is stego-secure.
\r
1362 %We suppose that $K,M \sim
\r
1363 %\mathbf{U}\left([0;1]\right)$, and $X \sim
\r
1364 %We consider a strategy in the CIIS scheme, and we
\r
1365 Let us suppose that $x^0 \sim
\r
1366 \mathbf{U}\left(\mathbb{B}^N\right)$ and $m^0 \sim
\r
1367 \mathbf{U}\left(\mathbb{B}^P\right)$ in a SCISMM setup.
\r
1368 We will prove by a mathematical induction that $\forall n \in \mathds{N}, x^n
\r
1369 \sim \mathbf{U}\left(\mathbb{B}^N\right)$. The base case is obvious according
\r
1370 to the uniform repartition hypothesis.
\r
1372 Let us now suppose that the statement $x^n \sim
\r
1373 \mathbf{U}\left(\mathbb{B}^N\right)$ holds for some $n$.
\r
1374 For a given $k \in \mathbb{B}^N$,
\r
1375 we denote by $\tilde{k_i} \in \mathbb{B}^N$ the vector defined by: $\forall i
\r
1376 \in \llbracket 0;\mathsf{N-1}\rrbracket,$
\r
1378 $k=\left(k_0,k_1,\hdots,k_i,\hdots,k_{\mathsf{N}-2},k_{\mathsf{N}-1}\right)$,\newline
\r
1379 then $\tilde{k}_i=\left( k_0,k_1,\hdots,\overline{k_i},\hdots,k_{\mathsf{N}-2},k_{\mathsf{N}-1} \right).$
\r
1382 %\begin{equation*}
\r
1384 $E_{i,j}$ be the following events: $$\forall (i,j) \in \llbracket
\r
1385 0;\mathsf{N-1}\rrbracket \times \llbracket 0;\mathsf{P-1}\rrbracket, E_{i,j}=$$
\r
1386 $$S_1^{n+1}=i \wedge S_2^{n+1}=j \wedge m_j^{n+1}=k_i \wedge \left(x^n=k \vee x^n=\tilde{k}_i\right),$$
\r
1388 $p=P\left(x^{n+1}=k\right).$
\r
1391 p=P\left(\bigvee_{i \in \llbracket
\r
1392 0;\mathsf{N-1}\rrbracket, j \in \llbracket 0;\mathsf{P-1}\rrbracket}
\r
1395 We now introduce the following notation: $P_1(i)=P\left(S_1^{n+1}=i\right),$
\r
1396 $P_2(j)=P\left(S_2^{n+1}=j\right),$
\r
1397 $P_3(i,j)=P\left(m_j^{n+1}=k_i\right),$
\r
1398 and $P_4(i)=P\left(x^n=k \vee x^n=\tilde{k}_i\right).$
\r
1401 These four events are independent in SCISMM setup, thus:
\r
1403 p=\sum_{i \in \llbracket
\r
1404 0;\mathsf{N-1}\rrbracket, j \in \llbracket 0;\mathsf{P-1}\rrbracket}
\r
1405 P_1(i)P_2(i)P_3(i,j)P_4(i).
\r
1408 Proposition~\ref{prop:CIIS-stego-security}, $P\left(m_j^{n+1}=k_i\right)=\frac{1}{2}$.
\r
1409 As the two events are incompatible:
\r
1410 $$P\left(x^n=k \vee x^n=\tilde{k}_i\right)=P\left(x^n=k\right) + P\left(x^n=\tilde{k}_i\right).$$
\r
1413 Then, by using the inductive hypothesis:
\r
1414 $P\left(x^n=k\right)=\frac{1}{2^N},$
\r
1416 $P\left(x^n=\tilde{k}_i\right)=\frac{1}{2^N}.$
\r
1418 Let $S$ be defined by $$S=\sum_{i
\r
1419 \in \llbracket 0;\mathsf{N-1}\rrbracket, j \in \llbracket 0;\mathsf{P-1}\rrbracket}
\r
1421 Then $p = 2 \times \frac{1}{2} \times \frac{1}{2^N} \times S = \frac{1}{2^N} \times S$.
\r
1423 $S$ can now be evaluated:
\r
1425 \begin{array}{lll}
\r
1427 \in \llbracket 0;\mathsf{N-1}\rrbracket, j \in \llbracket 0;\mathsf{P-1}\rrbracket}
\r
1429 & = & \sum_{i \in \llbracket 0;\mathsf{N-1}\rrbracket} P_1(i) \times \sum_{j \in \llbracket 0;\mathsf{P-1}\rrbracket}
\r
1434 The set of events $\left \{ S_1^{n+1}=i \right \}$ for $i \in \llbracket 0;N-1
\r
1435 \rrbracket$ and the set of events $\left \{ S_2^{n+1}=j \right \}$ for $j \in
\r
1436 \llbracket 0;P-1 \rrbracket$ are both a partition of the universe of possible,
\r
1439 %Evaluate now $ P\left(S^n=k\right)$.
\r
1441 %We have: $K^0 = M \otimes K \sim
\r
1442 %\mathbf{U}\left([0;1]\right)$, so $K^\prime=F\left( K^0,p \right) \sim
\r
1443 %\mathbf{U}\left([0;1]\right)$, because for PLCMs, ``Uniform input generate
\r
1444 %uniform output''~\cite{Lasota}.
\r
1445 %Well with an immediate proof by recurrence we have:
\r
1446 %$K^n \sim \mathbf{U}\left([0;1]\right)$. As $S^n = \left \lfloor N \times X^n
\r
1447 %\right \rfloor + 1$ we can deduce that: $S^n \sim
\r
1448 %\mathbf{U}\left([1;N]\right)$. Therefore: $ P\left(S^n=k\right)=\frac{1}{N}$.
\r
1450 %\begin{equation*}
\r
1451 %\begin{array}{llr}
\r
1452 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
\r
1453 % P\left(S^n=k\right) & \\
\r
1454 % & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} & \\
\r
1455 % & =\frac{1}{2^N} & \\
\r
1458 %\begin{equation*}
\r
1459 %$\begin{array}{llr}
\r
1460 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
\r
1461 % P\left(S^n=k\right) & \\
\r
1462 %P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} &
\r
1463 % =\frac{1}{2^N} \\
\r
1465 $P\left(x^{n+1}=k\right)=\frac{1}{2^N}$, which leads to $x^{n+1} \sim
\r
1466 \mathbf{U}\left(\mathbb{B}^N\right)$.
\r
1467 This result is true $\forall n \in \mathds{N}$, we thus have proven that the
\r
1468 stego-content $y$ is uniform in the set of possible stego-content, so
\r
1469 $y \sim \mathbf{U}\left(\mathbb{B}^N\right) \text{
\r
1470 when } x \sim \mathbf{U}\left(\mathbb{B}^N\right).$
\r
1474 \subsection{Study of chaos security of $CI_2$}\label{sec:chaos-security-ci2}
\r
1475 \subsubsection{Topological model}
\r
1476 \label{sec:SCISMM-topological-model}
\r
1478 %\section{THE NEW TOPOLOGICAL SPACE}
\r
1479 \noindent In this section, we prove that SCISMM can be modeled as a
\r
1480 discret dynamical system in a topological space.
\r
1481 We will show in the next section that SCISMM is a case of topological chaos in the sense of Devaney.
\r
1484 \paragraph{Iteration Function and Phase Space}\label{Defining}
\r
1487 %\begin{definition}[Function $F$]
\r
1491 F: & \llbracket0;\mathsf{N-1}\rrbracket \times
\r
1492 \mathds{B}^{\mathsf{N}}\times \llbracket0;\mathsf{P-1}\rrbracket \times
\r
1493 \mathds{B}^{\mathsf{P}}
\r
1494 \longrightarrow \mathds{B}^{\mathsf{N}} \\
\r
1495 & (k,x,\lambda,m) \longmapsto \left( \delta
\r
1496 (k,j).x_j+\overline{\delta (k,j)}.m_{\lambda}\right) _{j\in
\r
1497 \llbracket0;\mathsf{N-1}\rrbracket}\\
\r
1502 \noindent where + and . are the boolean addition and product operations.
\r
1504 Consider the phase space $\mathcal{X}_2$ defined as follow:
\r
1506 %\begin{definition}[Phase space $\mathcal{X}_2$]
\r
1509 \mathcal{X}_2 = \mathbb{S}_N \times \mathds{B}^\mathsf{N} \times \mathbb{S}_P
\r
1510 \times \mathds{B}^\mathsf{P} \times \mathbb{S}_P,
\r
1512 where $\mathbb{S}_N$ and $\mathbb{S}_P$ are the sets introduced in Section \ref{section:Algorithm}.
\r
1515 We define the map $\mathcal{G}_{f_0}:\mathcal{X}_2 \longrightarrow \mathcal{X}_2$ by:
\r
1518 \mathcal{G}_{f_0}\left(S_1,x,S_2,m,S_3\right) =
\r
1521 \left(\sigma_N(S_1),
\r
1522 F(i_N(S_1),x,i_P(S_2),m),\sigma_P(S_2),G_{f_0}(m,S_3),\sigma_P(S_3)\right)
\r
1525 \noindent Then SCISMM can be described by the
\r
1526 iterations of the following discret dynamical system:
\r
1528 %\begin{definition}[Discret Dynamical System for SCISMM]
\r
1532 X^0 \in \mathcal{X}_2 \\
\r
1533 X^{k+1}=\mathcal{G}_{f_0}(X^k).%
\r
1537 %\end{definition}%
\r
1540 \paragraph{Cardinality of $\mathcal{X}_2$}
\r
1542 By comparing $\mathcal{X}_2$ and $\mathcal{X}_1$, we have the following result.
\r
1544 \begin{proposition}
\r
1545 The phase space $\mathcal{X}_2$ has, at least, the cardinality of the continuum.
\r
1549 Let $\varphi$ be the map defined as follow:
\r
1552 \begin{array}{lcll}
\r
1553 \varphi: & \mathcal{X}_1 & \longrightarrow & \mathcal{X}_2 \\
\r
1554 & (S,x) & \longmapsto &(S,x,0,0,0)\\
\r
1558 \noindent $\varphi$ is injective.
\r
1559 So the cardinality of $\mathcal{X}_2$ is greater than or equal to the
\r
1560 cardinality of $\mathcal{X}_1$. And consequently
\r
1561 $\mathcal{X}_2$ has at least the cardinality of the continuum.
\r
1566 This result is independent on the number of cells of the system.
\r
1570 \paragraph{A New Distance on $\mathcal{X}_2$}
\r
1572 We define a new distance on $\mathcal{X}_2$ as follow:
\r
1573 %\begin{definition}[Distance $d_2$ on $\mathcal{X}_2$]
\r
1574 $\forall X,\check{X} \in \mathcal{X}_2,$ if $X =(S_1,x,S_2,m,S_3)$ and $\check{X} =
\r
1575 (\check{S_1},\check{x},\check{S_2},\check{m}, \check{S_3}),$ then:
\r
1577 \begin{array}{lll}
\r
1578 d_2(X,\check{X}) & = &
\r
1579 d_{\mathds{B}^{\mathsf{N}}}(x,\check{x})+d_{\mathds{B}^{\mathsf{P}}}(m,\check{m})\\
\r
1581 d_{\mathbb{S}_N}(S_1,\check{S_1})+d_{\mathbb{S}_P}(S_2,\check{S_2})+d_{\mathbb{S}_P}(S_3,\check{S_3}),\\
\r
1584 where $d_{\mathds{B}^{\mathsf{N}}}$, $d_{\mathds{B}^{\mathsf{P}}}$,
\r
1585 $d_{\mathbb{S}_N}$, and $d_{\mathbb{S}_P}$ are the same distances than in
\r
1586 Definition~\ref{def:distance-on-X1}.
\r
1594 \subsubsection{Continuity of $CI_2$}
\r
1596 To prove that SCISMM is another example of topological chaos in the
\r
1597 sense of Devaney, $\mathcal{G}_{f_0}$ must be continuous on the metric
\r
1598 space $(\mathcal{X}_2,d_2)$.
\r
1600 \begin{proposition}
\r
1601 $\mathcal{G}_{f_0}$ is a continuous function on $(\mathcal{X}_2,d_2)$.
\r
1605 We use the sequential continuity.
\r
1607 Let $((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)_{n\in \mathds{N}}$ be a sequence of the
\r
1608 phase space $\mathcal{X}_2$, which converges to $(S_1,x,S_2,m,S_3)$. We will prove
\r
1609 that $\left( \mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)\right) _{n\in
\r
1610 \mathds{N}}$ converges to $\mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)$. Let us recall
\r
1611 that for all $n$, $(S_1)^n$, $(S_2)^n$ and $(S_3)^n$ are strategies, thus we
\r
1612 consider a sequence of strategies (\emph{i.e.}, a sequence of sequences).
\r
1615 As $d_2(((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n),(S_1,x,S_2,m,S_3))$ converges to 0,
\r
1617 $d_{\mathds{B}^{\mathsf{N}}}(x^n,x)$, $d_{\mathds{B}^{\mathsf{P}}}(m^n,m)$,
\r
1618 $d_{\mathbb{S}_N}((S_1)^n,S_1)$, $d_{\mathbb{S}_P}((S_2)^n,S_2)$, and
\r
1619 $d_{\mathbb{S}_P}((S_3)^n,S_3)$ converges to 0. But
\r
1620 $d_{\mathds{B}^{\mathsf{N}}}(x^n,x)$ and $d_{\mathds{B}^{\mathsf{P}}}(m^n,m)$
\r
1621 are integers, so $\exists n_{0}\in \mathds{N}, \forall
\r
1623 d_{\mathds{B}^{\mathsf{N}}}(x^n,x)=0$ and $\exists n_{1}\in \mathds{N},
\r
1624 \forall n \geqslant n_1, d_{\mathds{B}^{\mathsf{P}}}(m^n,m)=0$.
\r
1626 Let $n_3=Max(n_0,n_1)$.
\r
1627 In other words, there exists a threshold $n_{3}\in \mathds{N}$ after which no
\r
1628 cell will change its state:
\r
1629 $\exists n_{3}\in \mathds{N},n\geqslant n_{3}\Longrightarrow (x^n = x) \wedge
\r
1632 In addition, $d_{\mathbb{S}_N}((S_1)^n,S_1)\longrightarrow 0$,
\r
1633 $d_{\mathbb{S}_P}((S_2)^n,S_2)\longrightarrow 0$, and
\r
1634 $d_{\mathbb{S}_P}((S_3)^n,S_3)\longrightarrow 0$, so $\exists n_4,n_5,n_6\in
\r
1637 \item $\forall n \geqslant n_4, d_{\mathbb{S}_N}((S_1)^n,S_1)<10^{-1}$,
\r
1638 \item $\forall n \geqslant n_5, d_{\mathbb{S}_P}((S_2)^n,S_2)<10^{-1}$,
\r
1639 \item $\forall n \geqslant n_6, d_{\mathbb{S}_P}((S_3)^n,S_3)<10^{-1}$.
\r
1642 Let $n_7=Max(n_4,n_5,n_6)$. For
\r
1643 $n\geqslant n_7$, all the strategies $(S_1)^n$, $(S_2)^n$, and $(S_3)^n$ have the same
\r
1644 first term, which are respectively $(S_1)_0$,$(S_2)_0$ and $(S_3)_0$ :$\forall n\geqslant n_7,$
\r
1645 $$((S_1)_0^n={(S_1)}_0)\wedge
\r
1646 ((S_2)_0^n={(S_2)}_0)\wedge ((S_3)_0^n={(S_3)}_0).
\r
1649 Let $n_8=Max(n_3,n_7)$.
\r
1650 After the $n_8-$th term, states of $x^n$ and $x$ on the one hand, and $m^n$ and $m$ on the other hand, are
\r
1651 identical. Additionally, strategies $(S_1)^n$ and $S_1$, $(S_2)^n$ and $S_2$, and $(S_3)^n$
\r
1652 and $S_3$ start with the same first term.
\r
1654 Consequently, states of
\r
1655 $\mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)$ and $\mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)$ are equal,
\r
1656 so, after the $(n_8)^{th}$ term, the distance $d_2$ between these two
\r
1657 points is strictly smaller than $3.10^{-1}$, so strictly smaller than 1.
\r
1659 We now prove that the distance between $\left(
\r
1660 \mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)\right) $ and $\left(
\r
1661 \mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)\right) $ is convergent to 0.
\r
1662 Let $\varepsilon >0$.
\r
1665 \item If $\varepsilon \geqslant 1$, we have seen that distance
\r
1666 between $\mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)$ and
\r
1667 $\mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)$ is
\r
1668 strictly less than 1 after the $(n_8)^{th}$ term (same state).
\r
1671 \item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant
\r
1672 \frac{\varepsilon}{3} \geqslant 10^{-(k+1)}$. As
\r
1673 $d_{\mathbb{S}_N}((S_1)^n,S_1)$, $d_{\mathbb{S}_P}((S_2)^n,S_2)$ and
\r
1674 $d_{\mathbb{S}_P}((S_3)^n,S_3)$ converges to 0, we have:
\r
1676 \item $\exists n_9\in \mathds{N},\forall n\geqslant
\r
1677 n_9,d_{\mathbb{S}_N}((S_1)^n,S_1)<10^{-(k+2)}$,
\r
1678 \item $\exists n_{10}\in \mathds{N},\forall n\geqslant
\r
1679 n_{10},d_{\mathbb{S}_P}((S_2)^n,S_2)<10^{-(k+2)}$,
\r
1680 \item $\exists n_{11}\in \mathds{N},\forall n\geqslant
\r
1681 n_{11},d_{\mathbb{S}_P}((S_3)^n,S_3)<10^{-(k+2)}$.
\r
1684 Let $n_{12}=Max(n_9,n_{10},n_{11})$
\r
1685 thus after $n_{12}$, the $k+2$ first terms of $(S_1)^n$ and $S_1$, $(S_2)^n$ and
\r
1686 $S_2$, and $(S_3)^n$ and $S_3$, are equal.
\r
1689 \noindent As a consequence, the $k+1$ first entries of the strategies of
\r
1690 $\mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n)$ and $
\r
1691 \mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)$ are the same
\r
1692 (due to the shift of strategies) and following the definition of
\r
1693 $d_{\mathbb{S}_N}$ and $d_{\mathbb{S}_P}$:
\r
1694 $$d_2\left(\mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n);\mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)\right)$$
\r
1696 $$d_{\mathbb{S}_N}((S_1)^n,S_1) + d_{\mathbb{S}_P}((S_2)^n,S_2) +
\r
1697 d_{\mathbb{S}_P}((S_3)^n,S_3)$$
\r
1698 which is smaller than $3.10^{-(k+1)} \leqslant 3.\frac{\varepsilon}{3} =\varepsilon$.
\r
1700 Let $N_{0}=max(n_{8},n_{12})$. We can claim that
\r
1702 \forall \varepsilon >0,\exists N_{0}\in \mathds{N},\forall n\geqslant N_{0},
\r
1705 d_2\left(\mathcal{G}_{f_0}((S_1)^n,x^n,(S_2)^n,m^n,(S_3)^n);\mathcal{G}_{f_0}(S_1,x,S_2,m,S_3)\right)
\r
1706 \leqslant \varepsilon .
\r
1708 $\mathcal{G}_{f_0}$ is consequently continuous on $(\mathcal{X}_2,d_2)$.
\r
1713 % >>>>>>>>>>>>>>>>>>>>>> Discrete chaotic iterations as topological chaos <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
\r
1714 %\subsection{Study of chaos-security}\label{section:chaos-security-ci-2}
\r
1716 \noindent To prove that we are in the framework of Devaney's topological chaos,
\r
1717 we have to check the regularity, transitivity, and sensitivity conditions.
\r
1718 %It will be proven that $\mathcal{G}_{f_0}$ function as introduce in
\r
1719 %definition~\ref{} satisfies these three hypotheses.
\r
1723 \subsubsection{Regularity}
\r
1725 \begin{proposition}%[Regularity of $\mathcal{G}_{f_0}$]
\r
1726 \label{prop:regularite}
\r
1727 Periodic points of $\mathcal{G}_{f_0}$ are dense in $\mathcal{X}_2$.
\r
1731 Let $(\check{S_1},\check{x},\check{S_2},\check{m}, \check{S_3})\in
\r
1732 \mathcal{X}_2$ and $\varepsilon >0$. We are looking for a periodic point
\r
1733 $(\widetilde{S_1},\widetilde{x},\widetilde{S_2},\widetilde{m}, \widetilde{S_3})$
\r
1734 satisfying $d_2((\check{S_1},\check{x},\check{S_2},\check{m},
\r
1735 \check{S_3});(\widetilde{S_1},\widetilde{x},\widetilde{S_2},\widetilde{m}, \widetilde{S_3}))<\varepsilon$.
\r
1737 As $\varepsilon$ can be strictly lesser than 1, we must choose
\r
1738 $\widetilde{x} = \check{x}$ and
\r
1739 $\widetilde{m} = \check{m}$.
\r
1740 Let us define $k_0(\varepsilon) =\lfloor
\r
1741 - log_{10}(\frac{\varepsilon}{3} )\rfloor +1$ and consider the set:
\r
1742 $\mathcal{S}_{\check{S_1},\check{S_2},\check{S_3}, k_0(\varepsilon)} =$
\r
1744 \in \mathbb{S}_N \times \mathbb{S}_P \times \mathbb{S}_P/ ((S_1)^k =
\r
1745 \check{S_1}^k) \wedge ((S_2)^k =\check{S_2}^k))\right.$
\r
1746 $\left.\wedge ((S_3)^k=\check{S_3}^k)), \forall k \leqslant k_0(\varepsilon)
\r
1751 $\forall (S_1,S_2,S_3) \in
\r
1752 \mathcal{S}_{\check{S_1},\check{S_2},\check{S_3},k_0(\varepsilon)},$
\r
1753 $d_2((S_1,\check{x},S_2,\check{m},S_3);(\check{S_1},\check{x},\check{S_2},\check{m},
\r
1754 \check{S_3})) < 3.\frac{\varepsilon}{3}=\varepsilon.$
\r
1755 It remains to choose $(\widetilde{S_1},\widetilde{S_1},\widetilde{S_1}) \in
\r
1756 \mathcal{S}_{\check{S_1},\check{S_2},\check{S_3}, k_0(\varepsilon)}$ such that
\r
1757 $(\widetilde{S_1},\widetilde{x},\widetilde{S_2},\widetilde{m}, \widetilde{S_3})
\r
1758 = (\widetilde{S_1},\check{x},\widetilde{S_2},\check{m}, \widetilde{S_3})$ is
\r
1759 a periodic point for $\mathcal{G}_{f_0}$.
\r
1761 Let $\mathcal{J} =$
\r
1762 $\left\{ i \in \llbracket0;\mathsf{N-1}\rrbracket / x_i \neq
\r
1763 \check{x_i}, \text{ where }\right.$
\r
1764 $\left.(S_1,x,S_2,m,S_3) = \mathcal{G}_{f_0}^{k_0}
\r
1765 (\check{S_1},\check{x},\check{S_2},\check{m},\check{S_3}) \right\},$
\r
1766 $\lambda = card(\mathcal{J})$, and
\r
1767 $j_0 <j_1 < ... < j_{\lambda-1}$ the elements of $ \mathcal{J}$.
\r
1770 \item Let us firstly build three strategies: $S_1^\ast$, $S_2^\ast$, and
\r
1771 $S_3^\ast$, as follows.
\r
1774 $(S_1^\ast)^k=\check{S_1}^k$, $(S_2^\ast)^k=\check{S_2}^k$, and
\r
1775 $(S_3^\ast)^k=\check{S_3}^k$, if $k \leqslant k_0(\varepsilon).$
\r
1776 \item Let us now explain how to replace $\check{x}_{j_q}$, $\forall q \in
\r
1777 \llbracket0;\mathsf{\lambda-1}\rrbracket$:\newline
\r
1778 First of all, we must replace $\check{x}_{j_0}$:
\r
1780 \item If $\exists \lambda_0 \in \llbracket0;\mathsf{P-1}\rrbracket /
\r
1781 \check{x}_{j_0}=m_{\lambda_0}$, then we can choose
\r
1782 $(S_1^\ast)^{k_0+1}=j_0$, $(S_2^\ast)^{k_0+1}=\lambda_0$,
\r
1783 $(S_3^\ast)^{k_0+1}=\lambda_0$, and so $I_{j_0}$ will be equal to $1$.
\r
1784 \item If such a $\lambda_0$ does not exist, we choose:\newline $(S_1^\ast)^{k_0+1}=j_0$, $(S_2^\ast)^{k_0+1}=0$,
\r
1785 $(S_3^\ast)^{k_0+1}=0$,\newline $(S_1^\ast)^{k_0+2}=j_0$,
\r
1786 $(S_2^\ast)^{k_0+2}=0$, $(S_3^\ast)^{k_0+2}=0$, \newline and
\r
1787 $I_{j_0}=2$.\newline
\r
1789 All of the $\check{x}_{j_q}$ are replaced similarly.
\r
1790 The other terms of $S_1^\ast$, $S_2^\ast$, and
\r
1791 $S_3^\ast$ are constructed identically, and the values of $I_{j_q}$ are defined in
\r
1792 the same way.\newline
\r
1793 Let $\gamma = \sum_{q=0}^{\lambda-1}I_{j_q}$.
\r
1796 \item Finally, let $(S_1^\ast)^{k}=(S_1^\ast)^{j}$, $(S_2^\ast)^{k}=(S_2^\ast)^{j}$,
\r
1797 and $(S_3^\ast)^{k}=(S_3^\ast)^{j}$, where $j\leqslant k_{0}(\varepsilon )+\gamma$
\r
1798 is satisfying $j\equiv k~[\text{mod } (k_{0}(\varepsilon )+\gamma)]$, if
\r
1799 $k>k_{0}(\varepsilon )+\gamma$.
\r
1802 $\mathcal{G}_{f_0}^{k_{0}(\varepsilon
\r
1803 )+\gamma}(S_1^\ast,\check{x},S_2^\ast,\check{m},S_3^\ast)=(S_1^\ast,\check{x},S_2^\ast,m,S_3^\ast).$
\r
1804 Let $\mathcal{K} =\left\{ i \in \llbracket0;\mathsf{P-1}\rrbracket / m_i \neq
\r
1805 \check{m_i}, \text{ where }\right.$\newline
\r
1806 $\left.\mathcal{G}_{f_0}^{k_{0}(\varepsilon
\r
1807 )+\gamma}(S_1^\ast,\check{x},S_2^\ast,\check{m},S_3^\ast)=(S_1^\ast,\check{x},S_2^\ast,m,S_3^\ast)
\r
1808 \right\},$\newline
\r
1809 $\mu = card(\mathcal{K})$, and
\r
1810 $r_0 <r_1 < ... < r_{\mu-1}$ the elements of $ \mathcal{K}$.
\r
1814 \item Let us now build the strategies $\widetilde{S_1}$,
\r
1815 $\widetilde{S_2}$, $\widetilde{S_3}$.
\r
1817 \item Firstly, let $\widetilde{S_1}^k=(S_1^\ast)^k$, $\widetilde{S_2}^k=(S_2^\ast)^k$, and
\r
1818 $\widetilde{S_3}^k=(S_3^\ast)^k$, if $k \leqslant k_0(\varepsilon) + \gamma.$
\r
1819 \item How to replace $\check{m}_{r_q}, \forall q \in
\r
1820 \llbracket0;\mathsf{\mu-1}\rrbracket$:\newline
\r
1822 First of all, let us explain how to replace $\check{m}_{r_0}$:
\r
1824 \item If $\exists \mu_0 \in \llbracket0;\mathsf{N-1}\rrbracket /
\r
1825 \check{x}_{\mu_0}=m_{r_0}$, then
\r
1826 we can choose $\widetilde{S_1}^{k_0+\gamma +1}=\mu_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1827 +1}=r_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1828 +1}=r_0$.\newline In that situation, we define $J_{r_0}=1$.
\r
1829 \item If such a $\mu_0$ does not exist, then we can choose:\newline
\r
1830 $\widetilde{S_1}^{k_0+\gamma +1}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1831 +1}=r_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1832 +1}=r_0$,\newline
\r
1833 $\widetilde{S_1}^{k_0+\gamma +2}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1834 +2}=r_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1836 $\widetilde{S_1}^{k_0+\gamma +3}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1837 +3}=r_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1841 Then the other $\check{m}_{r_q}$ are replaced as previously,
\r
1842 the other terms of $\widetilde{S_1}$,
\r
1843 $\widetilde{S_2}$, and $\widetilde{S_3}$ are constructed in the same way, and the
\r
1844 values of $J_{r_q}$ are defined similarly.\newline
\r
1845 Let $\alpha = \sum_{q=0}^{\mu-1}J_{r_q}$.
\r
1847 \item Finally, let $\widetilde{S_1}^{k}=\widetilde{S_1}^{j}$,
\r
1848 $\widetilde{S_2}^{k}=\widetilde{S_2}^{j}$, and
\r
1849 $\widetilde{S_3}^{k}=\widetilde{S_3}^{j}$ where $j\leqslant k_{0}(\varepsilon
\r
1850 )+\gamma +\alpha$ is satisfying $j\equiv k~[\text{mod } (k_{0}(\varepsilon
\r
1851 )+\gamma + \alpha)]$, if $k>k_{0}(\varepsilon )+\gamma + \alpha$.
\r
1856 So, $\mathcal{G}_{f_0}^{k_{0}(\varepsilon
\r
1857 )+\gamma+\alpha}(\widetilde{S_1},\check{x},\widetilde{S_2},\check{m},\widetilde{S_3})=(\widetilde{S_1},\check{x},\widetilde{S_2},\check{m},\widetilde{S_3})$
\r
1862 Then, $(\widetilde{S_1},\widetilde{S_2},\widetilde{S_3}) \in
\r
1863 \mathcal{S}_{\check{S_1},\check{S_2},\check{S_3},k_0(\varepsilon)}$ defined as
\r
1864 previous is such that $(\widetilde{S_3},\check{x},\widetilde{S_3},\check{m},\widetilde{S_3})$
\r
1865 is a periodic point, of period $k_{0}(\varepsilon
\r
1866 )+\gamma+\alpha$, which is $\varepsilon -$close to $(\check{S_1},\check{x},\check{S_2},\check{m}, \check{S_3})$.
\r
1868 As a conclusion, $(\mathcal{X}_2,\mathcal{G}_{f_0})$ is regular.
\r
1871 \subsubsection{Transitivity}\label{sec:transitivite}
\r
1873 \begin{proposition}%[Transitivity of $ \mathcal{G}_{f_0}$]
\r
1874 \label{prop:transitivite}
\r
1875 $(\mathcal{X}_2,\mathcal{G}_{f_0})$ is topologically transitive.
\r
1879 Let us define $\mathcal{X}:\mathcal{X}_2\rightarrow \mathbb{B}^{\mathsf{N}},$
\r
1880 such that $\mathcal{X}(S_1,x,S_2,m,S_3)=x$ and
\r
1881 $\mathcal{M}:\mathcal{X}_2\rightarrow \mathbb{B}^{\mathsf{P}},$ such that
\r
1882 $\mathcal{M}(S_1,x,S_2,m,S_3)=m$. Let \linebreak
\r
1883 $\mathcal{B}_{A}=\mathcal{B}(X_{A},r_{A}) $ and
\r
1884 $\mathcal{B}_{B}=\mathcal{B}(X_{B},r_{B})$ be two open balls of $\mathcal{X}_2$,
\r
1885 with\linebreak $X_{A}=((S_1)_{A},x_{A},(S_2)_{A},m_{A},(S_3)_{A})$ and
\r
1886 $X_{B}=((S_1)_{B},x_{B},(S_2)_{B},m_{B},(S_3)_{B})$. We are looking for
\r
1887 $\widetilde{X}=(\widetilde{S_1},\widetilde{x},\widetilde{S_2},\widetilde{m},\widetilde{S_3})$
\r
1888 in $\mathcal{B}_{A} $ such that $\exists n_{0}\in
\r
1889 \mathbb{N},\mathcal{G}_{f_0}^{n_{0}}(\widetilde{X})\in \mathcal{B}_{B}$.\newline
\r
1890 $\widetilde{X}$ must be in $\mathcal{B}_{A}$ and $r_{A}$ can be strictly
\r
1891 lesser than 1, so $\widetilde{x}=x_{A}$ and $\widetilde{m}=m_{A}$. Let
\r
1892 $k_{0}=\lfloor - \log _{10}(\frac{r_{A}}{3})+1\rfloor $.
\r
1893 Let us notice $\mathcal{S}_{X_{A}, k_0} =\left\{ (S_1,S_2,S_3)
\r
1894 \in \mathbb{S}_\mathsf{N}\times (\mathbb{S}_\mathsf{P})^2/ \forall k\leqslant k_{0},\right.$
\r
1895 $\left.(S_1^{k}=(S_1)_{A}^{k})\wedge
\r
1896 (S_2^{k}=(S_2)_{A}^{k})\wedge (S_3^{k}=(S_3)_{A}^{k}))\right\}$.
\r
1898 Then $\forall (S_1,S_2,S_3) \in \mathcal{S}_{X_{A}, k_0},
\r
1899 (S_1,\widetilde{x},S_2,\widetilde{m},S_3)\in \mathcal{B}_{A}.$
\r
1902 Let $\mathcal{J} =\left\{i\in
\r
1903 \llbracket0,\mathsf{N-1}\rrbracket/\check{x}_{i}\neq
\r
1904 \mathcal{X}(X_{B})_{i}, \text{ where }\right.$\newline
\r
1905 $\left.(\check{S_1},\check{x},\check{S_2},\check{m},\check{S_3})=\mathcal{G}_{f_0}^{k_{0}}(X_{A})\right\},$
\r
1906 $\lambda = card(\mathcal{J})$,\newline and
\r
1907 $j_0 <j_1 < ... < j_{\lambda-1}$ the elements of $ \mathcal{J}$.
\r
1910 \item Let us firstly build three strategies: $S_1^\ast$, $S_2^\ast$, and
\r
1911 $S_3^\ast$ as follows.
\r
1914 $(S_1^\ast)^k=(S_1)_A^k$, $(S_2^\ast)^k=(S_2)_A^k$, and
\r
1915 $(S_3^\ast)^k=(S_3)_A^k$, if $k \leqslant k_0.$
\r
1916 \item Let us now explain how to replace $\mathcal{X}(X_{B})_{j_q}$, $\forall q \in
\r
1917 \llbracket0;\mathsf{\lambda-1}\rrbracket$:\newline
\r
1918 First of all, we must replace $\mathcal{X}(X_{B})_{j_0}$:
\r
1920 \item If $\exists \lambda_0 \in \llbracket0;\mathsf{P-1}\rrbracket /
\r
1921 \mathcal{X}(X_{B})_{j_0}=\check{m}_{\lambda_0}$, then we can choose
\r
1922 $(S_1^\ast)^{k_0+1}=j_0$, $(S_2^\ast)^{k_0+1}=\lambda_0$,
\r
1923 $(S_3^\ast)^{k_0+1}=\lambda_0$, and so $I_{j_0}$ will be equal to $1$.
\r
1924 \item If such a $\lambda_0$ does not exist, we choose:\newline
\r
1925 $(S_1^\ast)^{k_0+1}=j_0$, $(S_2^\ast)^{k_0+1}=0$,
\r
1926 $(S_3^\ast)^{k_0+1}=0$,\newline $(S_1^\ast)^{k_0+2}=j_0$,
\r
1927 $(S_2^\ast)^{k_0+2}=0$, $(S_3^\ast)^{k_0+2}=0$ \newline and so let us notice
\r
1928 $I_{j_0}=2$.\newline
\r
1930 All of the $\mathcal{X}(X_{B})_{j_q}$ are replaced similarly.
\r
1931 The other terms of $S_1^\ast$, $S_2^\ast$, and $S_3^\ast$ are constructed identically, and the values of $I_{j_q}$ are defined on the same way.\newline
\r
1932 Let $\gamma = \sum_{q=0}^{\lambda-1}I_{j_q}$.
\r
1935 \item $(S_1^\ast)^{k}=(S_1^\ast)^{j}$, $(S_2^\ast)^{k}=(S_2^\ast)^{j}$
\r
1936 and $(S_3^\ast)^{k}=(S_3^\ast)^{j}$ where $j\leqslant k_{0}+\gamma$
\r
1937 is satisfying $j\equiv k~[\text{mod } (k_{0}+\gamma)]$, if
\r
1940 So,$\mathcal{G}_{f_0}^{k_{0}+\gamma}((S_1^\ast,x_A,S_2^\ast,m_A,S_3^\ast))=(S_1^\ast,x_B,S_2^\ast,m,S_3^\ast)$
\r
1942 Let $\mathcal{K} =\left\{ i \in \llbracket0;\mathsf{P-1}\rrbracket / m_i \neq
\r
1943 \mathcal{M}(X_{B})_{i}, \text{ where }\right.$\newline
\r
1944 $\left.(S_1^\ast,x_B,S_2^\ast,m,S_3^\ast)=\mathcal{G}_{f_0}^{k_{0}+\gamma}((S_1^\ast,x_A,S_2^\ast,m_A,S_3^\ast))\right\},$\newline
\r
1945 $\mu = card(\mathcal{K})$ and $r_0 <r_1 < ... < r_{\mu-1}$ the elements of $
\r
1949 \item Let us secondly build three other strategies: $\widetilde{S_1}$,
\r
1950 $\widetilde{S_2}$, $\widetilde{S_3}$ as follows.
\r
1952 \item $\widetilde{S_1}^k=(S_1^\ast)^k$, $\widetilde{S_2}^k=(S_2^\ast)^k$, and
\r
1953 $\widetilde{S_3}^k=(S_3^\ast)^k$, if $k \leqslant k_0 + \gamma.$
\r
1954 \item Let us now explain how to replace $\mathcal{M}(X_{B})_{r_q}, \forall q
\r
1955 \in \llbracket0;\mathsf{\mu-1}\rrbracket$:
\r
1957 First of all, we must replace $\mathcal{M}(X_{B})_{r_0}$:
\r
1959 \item If $\exists \mu_0 \in \llbracket0;\mathsf{N-1}\rrbracket /
\r
1960 \mathcal{M}(X_{B})_{r_0}=(x_B)_{\mu_0}$, then we can choose
\r
1961 $\widetilde{S_1}^{k_0+\gamma +1}=\mu_0$, $\widetilde{S_2}^{k_0+\gamma
\r
1962 +1}=r_0$, $\widetilde{S_3}^{k_0+\gamma
\r
1963 +1}=r_0$, and $J_{r_0}$ will be equal to $1$.
\r
1964 \item If such a $\mu_0$ does not exist, we choose:
\r
1965 $\widetilde{S_1}^{k_0+\gamma +1}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1966 +1}=r_0$, $\widetilde{S_3}^{k_0+\gamma
\r
1967 +1}=r_0$,\newline
\r
1968 $\widetilde{S_1}^{k_0+\gamma +2}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1969 +2}=r_0$, $\widetilde{S_3}^{k_0+\gamma
\r
1971 $\widetilde{S_1}^{k_0+\gamma +3}=0$, $\widetilde{S_2}^{k_0+\gamma
\r
1972 +3}=r_0$, $\widetilde{S_3}^{k_0+\gamma
\r
1974 and so let us notice $J_{r_0}=3$.\newline
\r
1976 All the $\mathcal{M}(X_{B})_{r_q}$ are replaced similarly.
\r
1977 The other terms of $\widetilde{S_1}$,
\r
1978 $\widetilde{S_2}$, and $\widetilde{S_3}$ are constructed identically, and the
\r
1979 values of $J_{r_q}$ are defined on the same way.\newline
\r
1980 Let $\alpha = \sum_{q=0}^{\mu-1}J_{r_q}$.
\r
1982 \item $\forall k \in \mathbb{N}^\ast, \widetilde{S_1}^{k_0+ \gamma + \alpha
\r
1983 + k}=(S_1)_B^{k}$, $\widetilde{S_2}^{k_0+ \gamma + \alpha + k}=(S_2)_B^{k}$, and
\r
1984 $\widetilde{S_3}^{k_0+ \gamma + \alpha + k}=(S_3)_B^{k}$.
\r
1989 $\mathcal{G}_{f_0}^{k_{0}+\gamma+\alpha}(\widetilde{S_1},x_A,\widetilde{S_2},m_A,\widetilde{S_3})=X_B$,
\r
1990 with $(\widetilde{S_1},\widetilde{S_2},\widetilde{S_3}) \in \mathcal{S}_{X_{A},
\r
1992 Then $\widetilde{X} = (\widetilde{S_1},x_A,\widetilde{S_2},m_A,\widetilde{S_3})
\r
1993 \in \mathcal{X}_2$ is such that $\widetilde{X} \in \mathcal{B}_A$ and
\r
1994 $\mathcal{G}_{f_0}^{k_0+\gamma+\alpha}( \widetilde{X}) \in \mathcal{B}_B$.
\r
1995 Finally we have proven the result.
\r
1998 \subsubsection{Sensibility to the Initial Condition}\label{sec:sensibilite}
\r
2000 \begin{proposition}%[Sensitivity of $,\mathcal{G}_{f_0}$]
\r
2001 \label{prop:sensibilite}
\r
2002 $(\mathcal{X}_2,\mathcal{G}_{f_0})$ has sensitive dependence on initial conditions.
\r
2006 $\mathcal{G}_{f_0}$ is regular and transitive. Due to Theorem~\ref{theo:banks}, $\mathcal{G}_{f_0}$ is sensitive.
\r
2009 %In a following section, we will show that this result can be stated independently of regularity,
\r
2010 %which must be redefined in the context of the finite set of
\r
2011 %machine numbers (see section \ref{Concerning}).
\r
2013 %In addition, the constant of sensitivity will be computed.
\r
2016 %This sensitive dependence could be stated as a consequence of regularity and
\r
2017 %transitivity (by using the theorem of Banks~\cite{Banks92}). However, we
\r
2018 %prefer to prove this result independently of regularity, because the
\r
2019 %notion of regularity must be redefined in the context of the finite set of
\r
2020 %machine numbers (see section \ref{Concerning}).
\r
2022 %In addition, the constant of sensitivity has been computed.
\r
2024 \subsubsection{Devaney's chaos}
\r
2028 In conclusion, $(\mathcal{X}_2,\mathcal{G}_{f_0})$ is topologically transitive, regular,
\r
2029 and has sensitive dependence on initial conditions. Then according to
\r
2031 defintition~\ref{def:chaos-devaney}~\vpageref{def:chaos-devaney}, we have the result.
\r
2033 \begin{theorem}%[$\mathcal{G}_{f_0}$ is a chaotic map]
\r
2034 \label{theo:chaotic}
\r
2035 $\mathcal{G}_{f_0}$ is a chaotic map on $(\mathcal{X}_2,d_2)$ in the sense of Devaney.
\r
2038 So we can claim that:
\r
2040 \begin{theorem}%[Chaos-security of SCISMM]
\r
2041 \label{theo:SCISMM-chaosecurity}
\r
2042 SCISMM is chaos-secure.
\r
2046 \subsection{Quantitative property of
\r
2047 $CI_2$}\label{sec:quantitative-properties-ci2}
\r
2049 In this section, it is studied one of the quantitative properties of the
\r
2050 chaos-security of the steganographic process $CI_2$: the constant of sensitivity
\r
2055 \subsection{Qualitative property of
\r
2056 $CI_2$}\label{sec:qualitative-properties-ci2}
\r
2058 In this section, it is studied one of the qualitative properties of the
\r
2059 chaos-security of the steganographic process $CI_2$: the strong transitivity.
\r
2063 \subsection{Consequences in attacks
\r
2064 frameworks}\label{sec:qualitative-properties-ci2}
\r
2066 \textbf{TODO} In this section, it is given the implication of the qualitative
\r
2067 and quantitative properties of $CI_2$ in KOA, KMA,CMA and WOA setups.
\r
2071 \section{Conclusion and future work}\label{sec:conclusion}
\r
2073 In this research work, the two information hiding schemes based on chaotic iterations proposed in \cite{gfb10:ip} and \cite{fgb11:ip}
\r
2074 have been recalled.
\r
2075 Additionally, all the previous contributions in the field of chaos-based security for information hiding have been summed up.
\r
2076 Furthermore, the robustness study of the first scheme initiated in \cite{guyeux10ter} has been widely improved, by using a large number of images, parameters, and attacks.
\r
2077 Finally, the security study of the new version of our information hiding scheme has been deepened, by giving qualitative and quantitative measures of its level of chaos-security.
\r
2078 In particular, the constant of sensibility and the qualitative properties of
\r
2079 strong transitivity and indecomposability have been established.\newline
\r
2081 The comparison between the currently only stego and chaos secure schemes is
\r
2082 synthesized in the
\r
2083 table~\ref{table:security-processes-comparison}~\vpageref{table:security-processes-comparison}.\newline
\r
2085 In future work, we intend to compare the robustness and security of these schemes with other existing information hiding algorithms.
\r
2086 Among other things, a complete comparison between spread-spectrum and chaotic iterations will be realized, and the security of other existing schemes will be studied in the framework of chaos-security.
\r
2087 Concerning the theoretical aspects of security, we intend to understand links and implications between the two existing security frameworks for information hiding: the stego-security and the chaos-security.
\r
2088 Finally, their relation with intended requirements in information hiding will be deepened.
\r
2091 \newcolumntype{V}{>{\centering\arraybackslash} m{1cm} }
\r
2092 %\resizebox{8cm}{!} {
\r
2095 %\begin{tabularx}{8cm}{|c|V|V|V|V|}
\r
2096 \begin{tabular}{|c|c|c|c|c|c|c|}\cline{2-3}
\r
2098 & \multirow{2}{*}{\textbf{KOA}} & \multirow{2}{*}{\textbf{KMA}} &
\r
2099 \multirow{2}{*}{\textbf{WOA}} & \multirow{2}{*}{\textbf{CMA}} &
\r
2100 \textbf{Bits}\\ & & & & & \textbf{embeded}\\
\r
2105 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2107 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2109 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2111 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2117 \textbf{NW \tiny($\eta=1$)}
\r
2119 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-normal-jaune}}
\r
2121 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-normal-jaune}}
\r
2123 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2125 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/interrogation}}
\r
2133 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2135 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2137 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2139 \parbox[c]{0.4cm}{\includegraphics[width=0.5cm]{img/smiley-sourire-vert}}
\r
2146 \caption{NW, $CI_1$, and $CI_2$ security. Embedding capacity.}
\r
2147 \label{table:security-processes-comparison}
\r
2156 % To cite in reference all the Bibtex entries.
\r
2159 %\bibliographystyle{compj}
\r
2160 %\bibliography{ModellingBidders}
\r
2162 \bibliographystyle{compj}
\r
2163 \bibliography{jabref}
\r
