X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/07fc9a29ed26c33dfe987821fc94b3afa4cdd3a5..b14071948f5418eda195be08e12edc746770f7de:/intro.tex

diff --git a/intro.tex b/intro.tex
index 569c493..c0b6e7d 100644
--- a/intro.tex
+++ b/intro.tex
@@ -38,214 +38,65 @@ asynchronous iterations are strongly connected. We then have proven that it is n
 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
+generated functions, we thus have considered for further investigations only the ones 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.
+stochastic Markov matrix. 
+
+
+However, it cannot be directly deduced
+that $\chi_{\textit{14Secrypt}}$ is chaotic 
+since we do not output all the successive
+values of iterating $F_f$. 
+This algorithm only displays a
+subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and
+it is indeed  definitively false that the chaos property is 
+preserved for any subsequence of a chaotic sequence.
+This article presents conditions to preserve this property.
+
+An approach to generate a large class of chaotic functions has 
+been presented in~\cite{chgw14oip}.
+It is basically fourfold:
+first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop
+on each vertex and finally, translate this into a Boolean map.
+We are then left to check whether this approach proposes maps with the required conditions 
+for the chaos. 
+The answer is indeed positive. The pseudorandom number generation can thus be seen as a
+random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle.
+
+In the PRNG context, there remains to find which subsequence
+is theoretically and practically 
+sufficient to extract.
+A uniform distribution is indeed awaited and this 
+cannot be obtained in a walk in the hypercube
+with paths of short length $b$.
+However, the higher 
+is $b$  the slower is the 
+algorithm to generate pseudorandom
+numbers. 
+The  time  until the
+corresponding  Markov chain is close 
+to the uniform distribution is a metric
+that should be theoretically and practically studied.
+Finally, the ability of the approach to face classical 
+tests suite has to be evaluated.
+
+
+%A upper bound of this time  quadratic in the number of 
+%generated bits.
 
 
 The remainder of this article is organized as follows. The next section is devoted to 
-preliminaries, basic notations, and terminologies regarding asynchronous iterations.
+preliminaries, basic notations, and terminologies regarding Boolean map 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. 
+while the proofs of chaos of our most general PRNGs is provided. 
+This is the first major contribution.
+Section~\ref{sec:SCCfunc} shows how to generate functions with required properties 
+making the PRNG chaotic.
+The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework 
+to study the stopping-time, \textit{i.e.}, time until reaching
+a uniform distribution.
+This is the second major contribution.
+The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite.
 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: 
