typos

[rairo15.git] / intro.tex

The exploitation of chaotic systems to generate pseudorandom sequences is
an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally 
chosen due to their unpredictable character and their sensitiveness to initial conditions.
In most cases, these generators simply consist in iterating a chaotic function like 
the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
It thus remains to find optimal parameters in such functions so that attractors are
avoided, hoping by doing so that the generated numbers follow a uniform distribution.
In order to check the quality of the produced outputs, it is usual to test the 
PRNGs   (Pseudo-Random  Number   Generators) with statistical batteries like
the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.

In its general understanding, chaos notion is often reduced to the strong
sensitiveness to the initial conditions (the well known ``butterfly effect''):
a continuous function $k$ defined on a metrical space is said 
\emph{strongly sensitive to the initial conditions} if for each point 
$x$ and each positive value $\epsilon$, it is possible to find another 
point $y$ as close as possible to $x$, and an integer $t$ such that the distance
between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} 
imposes to the chaotic function two other properties called
\emph{transitivity} and \emph{regularity}. Functions evoked above have
been studied according to these properties, and they have been proven as chaotic on $\R$.
But nothing guarantees that such properties are preserved when iterating the functions
on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
machines.

To avoid this lack of chaos, we have previously presented some PRNGs that iterate
continuous functions $G_f$ on a discrete domain  $\{ 1, \ldots,  n \}^{\Nats}
 \times  \{0,1\}^n$, where $f$  is a Boolean function (\textit{i.e.},  $f  :
 \{0,1\}^n      \rightarrow      \{0,1\}^n$).       These generators are 
$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     and
$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     where    \textit{CI}    means
\emph{Chaotic Iterations}.
We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the 
asynchronous iterations are strongly connected. We then have proven that it is necessary
and sufficient that the Markov matrix associated to this graph is doubly stochastic,
in order to have a uniform distribution of the outputs. We have finally established 
sufficient conditions to guarantee the first property of connectivity. Among the 
generated functions, we thus have considered for further investigations only the one that
satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic 
method allowing to directly obtain a strongly connected iteration graph having a doubly
stochastic Markov matrix. The research work presented here generalizes this latter article
by updating the iteration domain and the metric. The obtained algorithm owns the same
theoretical properties but with a reduced mixing time.

% 
% Pour décrire un peu plus précisément le principe de
% la génération pseudo-aléatoire, considérons l'espace booléen 
% $\Bool=\{0,1\}$
% muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} 
% définies par les tableaux ci-dessous:

% \begin{center}
%   \begin{tabular}{|c|c|c|}
%     \hline 
%     +              & 0 & 1 \\
%     \hline 
%     0              & 0 & 1 \\
%     \hline 
%     1              & 1 & 1 \\
%     \hline
%   \end{tabular}\qquad
%   \begin{tabular}{|c|c|c|}
%     \hline 
%     .              & 0 & 1 \\
%     \hline 
%     0              & 0 & 0 \\
%     \hline 
%     1              & 0 & 1 \\
%     \hline
%   \end{tabular}\qquad
%   \begin{tabular}{|c|c|c|}
%     \hline 
%     x              & 0 & 1 \\
%     \hline 
%     $\overline{x}$ & 1 & 0 \\
%     \hline 
%   \end{tabular}
% \end{center}


% La fonction itérée est
% une fonction $f$ de $\Bool^n$ dans lui-même qui à
% un mot binaire $x = (x_1,\ldots,x_n)$ 
% associe le mot $(f_1(x),\ldots, f_n(x))$.
% Un exemple de fonction de $\Bool^n$ dans lui-même
% est la fonction négation 
% définie par  
% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 

% Le principe itératif, basé sur  le mode opératoire dit \emph{asynchrone}, est le
% suivant: à chaque itération  $t$, on choisit un indice $i$ entre  $1$ et $n$, et
% le mot $x^t = (x_1^t,\ldots,x_n^t)$  est remplacé par $x^{t+1} = (x_1^t,\ldots ,
% x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.

% Au  bout d'un  nombre $N$  d'itérations,  si la  fonction (notée  $G_f$ dans  ce
% document)  que l'on  peut  associer à  l'algorithme  décrit ci-dessus  a de  \og
% \emph{bonnes}\fg{} propriétés chaotiques, le  mot $x^N$ doit être \og \emph{très
%   différent}\fg{} de  $x^0$ de  façon à  sembler ne plus  dépendre de  $x_0$. En
% effet, pour  un générateur aléatoire, il  faut que la structure  de $x^N$ semble
% être due  au hasard;  pour une application  cryptographique, il faut  qu'il soit
% matériellement  impossible   (dans  les  conditions   techniques  actuelles)  de
% retrouver $x^0$ à partir de $x^N$.

% Tous  les  mots   de  $\Bool^n$  peuvent  constituer  les   $2^n$  sommets  d'un
% \gls{graphoriente} (cf. glossaire) dans lequel  un arc relie deux sommets $x$ et
% $x'$  s'il existe  une itération  de l'algorithme  de génération  qui  permet de
% passer directement de  $x$ à $x'$.   Ce graphe est  appelé le \emph{graphe  d'itérations} et
% nous montrons ici que si  l'on a un \gls{graphfortementconnexe} (cf. glossaire),
% alors la fonction $G_f$ est transitive, donc chaotique.

% Enfin, un bon générateur aléatoire se doit de 
% fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
% La dernière partie de cet article donne, 
% dans le cas où le graphe d'itérations est fortement connexe, 
% une condition nécessaire et suffisante pour que
% cette propriété soit satisfaite.


% Le chaos a été appliqué à des domaines variés en 
% informatique, comme les fonctions de hachage,
% la stéganographie, la génération de nombres pseudo 
% aléatoires\ldots
% Toutes ces  applications  exploitent les  propriétés définissant des 
% fonctions  chaotiques et énoncées par Devaney,  telles que la
% transitivité, la régularité et la sensibilité aux conditions initiales.


% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs 
% définis par une fonction chaotique  $f$  d'un  domaine $E$ dans lui-même.
% En démarrant d'un état quelconque $x$ du sytème, 
% nommé par la suite \emph{configuration}, 
% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots 
% où $f^k(x)$  est le   $k^{\textrm{ème}}$ itéré  de  $f$ en  $x$.  
% La plupart des applications informatiques dite \og chaotiques \fg{}
% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
% où $f$ est la fonction  \emph{tente} avec  $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) 
% ou la fonction  \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) 
% connues pour être chaotiques dans $\R$.

% \begin{figure}[hb]
% \begin{center}
%     \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{
%       \begin{minipage}{0.45\textwidth}
%         \begin{center}
%           \includegraphics[height=3cm]{images/tente.png}
%         \end{center}
%       \end{minipage}
%       \label{fig:iter:tent}
%     }
%     \subfloat[Fonction logistique $f(x) =  \mu x (1 -x)$]{
%       \begin{minipage}{0.45\textwidth}
%         \begin{center}
%           \includegraphics[height=3cm]{images/logistique.png}
%         \end{center}
%       \end{minipage}
%       \label{fig:iter:log}
%     }
% \end{center}
%  \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
% \end{figure}


% Cependant il n'a pas été établi que des fonctions prouvées
% comme étant chaotiques sur $\R$ le restent sur les  nombres à virgule flottante,
% qui est le domaine d'interprétation informatique des réels.  
% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
% lors de l'exécution des programmes implémentant ces fonctions. 
% Ce document présente pour cela l'alternative suivante: 
% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, 
% où $\Bool$ est le domaine des booléens  $\{0,1\}$, on
% construit une fonction $G_f : \llbracket 1 ;  n \rrbracket^{\Nats}  \times \Bool^n$, 
% où $\llbracket 1  ; n \rrbracket$ est l'ensemble des entiers
% $\{1, 2, \hdots,  n\}$ et on itère celle-ci.
% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant 
% l'implémentation.
% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation 
% définie par  
% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 




% De plus,  plutôt que de trouver des exemples de telles fonctions $f$, et de prouver 
% (\textit{a  posteriori}) la chaoticité de $G_f$, on peut penser à caractériser  
% les fonctions engendrant systématiquement des fonctions chaotiques.
% Ce document présente une telle caractérisation 
% qui s'exprime sur le graphe des itérations asynchrones
% de la fonction booléenne $f$, qui est, intuitivement, le graphe 
% de toutes les itérations possibles de la fonction. 
% Cette situation se réduit en un problème portant sur des graphes à $2^n$  
% sommets.  
% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
% au graphe des interactions de $f$, qui, intuitivement,
% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
% et qui ne contient que  $n$ sommets (et qui est à comparer aux $2^n$ 
% sommets.
% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.

% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
% de nombres pseudo aléatoires, l'aléa étant intuitivement 
% une notion proche de celle du chaos.
% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins 
% garantir que l'ensemble des valeurs retournées par l'algorithme suit
% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
% Cette idée est validée après évaluation 
% des générateurs de nombres pseudo aléatoires 
% sur une batterie de tests.


The remainder of this article is organized as follows. The next section is devoted to 
preliminaries, basic notations, and terminologies regarding asynchronous iterations.
Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the
PRNG chaotic. The next section focuses on examples of such graphs obtained by modifying the 
hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and
pseudorandom number generation. 
This research work ends by a conclusion section, where the contribution is summarized and
intended future work is outlined.

% Le reste de ce document est organisé comme suit. 
% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
% La chaoticité de la fonction engendrée $G_f$ est caractérisée en 
% section~\ref{sec:charac}. 
% Des conditions suffisantes pour obtenir cette chaoticité sont présentées  en
% section~\ref{sec:sccg}.
% L'application à la génération de nombres pseudo aléatoires est formalisée,
% les fonctions dont l'image est uniformément distribuée sur le domaine sont
% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.

% Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
% systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
% définitions théoriques liées au chaos. Ensuite, une application de ces résultats
% à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
% section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
% matrices         d'itérations         doublement        stochastiques         en
% section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
% du PRNG obtenu est éprouvée avec les tests standards du domaine.
% 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: