Ajout figure 3-cube

[16dcc.git] / intro.tex

diff --git a/intro.tex b/intro.tex
index 10463ea2fcf14be284f605bb2cd583b7588d5bc0..e66a6b47b02acc34d0d324024252f3925562d7be 100644 (file)
--- a/intro.tex
+++ b/intro.tex
@@ -1,28 +1,29 @@
 The exploitation of chaotic systems to generate pseudorandom sequences
 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
+is  a very topical issue~\cite{915396,915385,5376454}.  Such   systems  are
+fundamentally chosen  because of  their unpredictable character  and their

 sensitiveness to initial conditions.   In most cases, these generators
 simply  consist in  iterating  a chaotic  function  like the  logistic
 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
+map~\cite{915396,915385} or  the Arnold's  one~\cite{5376454}\ldots 
+Optimal  parameters of  such functions remain to be found so that
+attractors are avoided,\textit{e.g.}.
+By following this procedure, generated numbers will hopefully 

 follow a uniform  distribution.  In order to check the  quality of the
 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
+produced outputs, PRNGs (Pseudo-Random Number
+Generators)    are usually  tested with   statistical    batteries   like   the   so-called

 DieHARD~\cite{Marsaglia1996},          NIST~\cite{Nist10},          or
 TestU01~\cite{LEcuyerS07} ones.
 
 DieHARD~\cite{Marsaglia1996},          NIST~\cite{Nist10},          or
 TestU01~\cite{LEcuyerS07} ones.
 

-In its  general understanding,  chaos notion is  often reduced  to the
+In its  general understanding,  the notion of chaos  is  often reduced  to the

 strong  sensitiveness  to  the  initial  conditions  (the  well  known
 ``butterfly effect''): a continuous function $k$ defined on a metrical
 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
+space is said to be \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$,
 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,
+denoted by $k^t(x)$ and $k^t(y)$, is larger than $\epsilon$. However,

 in  his definition  of  chaos, Devaney~\cite{Devaney}  imposes to  the
 chaotic function  two other properties called  \emph{transitivity} and
 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
+\emph{regularity}. The functions mentioned 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
 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


@@ -35,11 +36,11 @@ 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)$
 \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
+\cite{wbg10ip},             and             $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14}    where   \textit{CI} stands for

 \emph{Chaotic Iterations}.  We have firstly proven in~\cite{bcgr11:ip}
 \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
+that,    to    establish    the   chaotic    nature    of    
+$\textit{CIPRNG}_f^1$ algorithm,  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
 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


@@ -47,13 +48,13 @@ 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
 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.
+as well.

 
 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
 
 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
+indeed incorrect to say that the chaos property is preserved for any

 subsequence of  a chaotic sequence.  This  article presents conditions
 to preserve this property.
 
 subsequence of  a chaotic sequence.  This  article presents conditions
 to preserve this property.
 


@@ -62,7 +63,7 @@ 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
 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.
+approach that solved 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)
 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)


@@ -71,12 +72,12 @@ a doubly stochastic Markov matrix.
 
 However, the removed Hamiltonian cycle  
 has a great influence in the quality of the output.
 
 However, the removed Hamiltonian cycle  
 has a great influence in the quality of the output.

-For instance, if this one one is not balanced (\textit{i.e.},
+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 
 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. 
+implements the previous scheme and thus provides  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.
 
 The length $b$ of the walk to reach a
 distribution close to the uniform one would be dramatically long.


@@ -88,27 +89,28 @@ suite is evaluated.
 
 
 
 
 
 

-
-The  remainder of  this  article  is organized  as  follows. The  next
+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
 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
+recalled  while the  proof  of chaos  of our  most  general PRNGs  is

 provided.      This    is     the     first    major     contribution.
 Section~\ref{sec:SCCfunc}  recalls a general scheme
 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. 
+to obtain functions with an expected behavior. Main theorems are recalled
+to make the article self-sufficient. 

 The  next  section (Sect.~\ref{sec:hamilton}) presents an algorithm that
 The  next  section (Sect.~\ref{sec:hamilton}) presents an algorithm that

-implements this scheme and proves it always produces a solution.  
-This  is   the   second   major  contribution
-The  later section
-(Sect.~\ref{sec:hypercube}) defines the theoretical framework to study
-the  mixing-time,  \textit{i.e.},  time  until  reaching  a  uniform
-distribution. It proves that this one is at worth quadratic in the number
-of elements. Experiments show that the bound is practically largely much
-lower. This  is   the   third   major  contribution.    The
+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.},  
+the sufficient amont of time until  reaching  an uniform
+distribution. It proves that this one is in the worst case quadratic in the number
+of elements. Experiments show that the bound is in practice 
+significantly lower. This  is   the   third   major  contribution.  

 Section~\ref{sec:prng} gives practical results  on evaluating the PRNG
 Section~\ref{sec:prng} gives practical results  on evaluating the PRNG

-against  the NIST  suite.  This  research  work ends  by a  conclusion
+against  the NIST  suite.  This  research  work ends  with a  conclusion

 section, where the contribution is summarized and intended future work
 is outlined.
 
 section, where the contribution is summarized and intended future work
 is outlined.