Ajout diapos présentation PRNG

[16dcc.git] / intro.tex

diff --git a/intro.tex b/intro.tex
index c0b6e7d55d4f0dab90e4c4c57f95077979fea0d2..83b0a5a8ef164e60eed52611fe7b56b88cd6c8fe 100644 (file)
--- a/intro.tex
+++ b/intro.tex
@@ -1,102 +1,120 @@
-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.
+The exploitation of chaotic systems to generate pseudorandom sequences
+is  a    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.
+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 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. 
+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\}^{\mathsf{N}}
+\rightarrow  \{0,1\}^{\mathsf{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{DBLP:conf/secrypt/CouchotHGWB14}    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  ones   that  satisfy  the  second  property
+too.

 
 

+However,      it     cannot      be     directly      deduced     that
+$\chi_{\textit{14Secrypt}}$ is chaotic since we  do not output all the
+successive values of iterating $G_f$.   This algorithm only displays a
+subsequence $x^{b.n}$  of a whole  chaotic sequence $x^{n}$ and  it is
+indeed not correct  that the chaos property is preserved for any
+subsequence of  a chaotic sequence.  This  article presents conditions
+to preserve this property.

 
 

-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.
+Finding a Boolean function which provides a  strongly connected
+iteration graph having a doubly stochastic Markov matrix is however
+not an easy task.
+We have firstly proposed in~\cite{bcgr11:ip} a  generate-and-test based
+approach that solves this issue. However, this one was not efficient enough.
+Thus, a second scheme has been further presented
+in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
+a  $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
+has been removed is strongly connected and has
+a doubly stochastic Markov matrix.

 
 

-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.
+However, the removed Hamiltonian cycle  
+has a great influence in the quality of the output.
+For instance, if this one is not balanced (\textit{i.e.},
+the number of changes in different bits are completely different),
+some bits would be hard to switch.
+This article shows an effective algorithm that efficiently 
+implements the previous scheme and provides thus functions issued
+from removing, in the $\mathsf{N}$-cube, a \emph{balanced} Hamiltonian cycle. 

 
 

+The length $b$ of the walk to reach a
+distribution close to the uniform one would be dramatically long.
+This article theoretically and practically
+studies the length $b$ until the corresponding Markov
+chain is close to the uniform distribution.
+Finally, the ability of the approach to face classical tests
+suite is 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 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. 
-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.
+This article, which 
+is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14}, 
+is organized  as  follows. The  next
+section   is   devoted   to  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.      This    is     the     first    major     contribution.
+Section~\ref{sec:SCCfunc}  recalls a general scheme
+to obtain functions with awaited behavior. Main theorems are recalled
+to make the document self-content. 
+The  next  section (Sect.~\ref{sec:hamilton}) presents an algorithm that
+implements this scheme and proves that it always produces a solution.  
+This  is   the   second   major  contribution.
+Then, Section~\ref{sec:hypercube} defines the theoretical framework to study
+the  mixing-time,  \textit{i.e.},  time  until  reaching  an uniform
+distribution. It proves that this one is at worth quadratic in the number
+of elements. Experiments show that the bound is in practice largely much
+lower. This  is   the   third   major  contribution.  
+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.
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: