]> AND Private Git Repository - 16dcc.git/blob - intro.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
quelques corrections après remarques de Sylvain
[16dcc.git] / intro.tex
1 The exploitation of chaotic systems to generate pseudorandom sequences
2 is  a    hot  topic~\cite{915396,915385,5376454}.  Such   systems  are
3 fundamentally chosen  due to  their unpredictable character  and their
4 sensitiveness to initial conditions.   In most cases, these generators
5 simply  consist in  iterating  a chaotic  function  like the  logistic
6 map~\cite{915396,915385} or  the Arnold's  one~\cite{5376454}\ldots It
7 thus  remains to  find optimal  parameters in  such functions  so that
8 attractors are avoided, hoping by  doing so that the generated numbers
9 follow a uniform  distribution.  In order to check the  quality of the
10 produced outputs, it is usual  to test the PRNGs (Pseudo-Random Number
11 Generators)   with   statistical    batteries   like   the   so-called
12 DieHARD~\cite{Marsaglia1996},          NIST~\cite{Nist10},          or
13 TestU01~\cite{LEcuyerS07} ones.
14
15 In its  general understanding,  chaos notion is  often reduced  to the
16 strong  sensitiveness  to  the  initial  conditions  (the  well  known
17 ``butterfly effect''): a continuous function $k$ defined on a metrical
18 space is said  \emph{strongly sensitive to the  initial conditions} if
19 for each point $x$ and each  positive value $\epsilon$, it is possible
20 to find another point $y$ as close  as possible to $x$, and an integer
21 $t$ such that the distance between the $t$-th iterates of $x$ and $y$,
22 denoted by $k^t(x)$ and $k^t(y)$, are larger than $\epsilon$. However,
23 in  his definition  of  chaos, Devaney~\cite{Devaney}  imposes to  the
24 chaotic function  two other properties called  \emph{transitivity} and
25 \emph{regularity}. Functions evoked above  have been studied according
26 to these  properties, and they  have been  proven as chaotic  on $\R$.
27 But  nothing  guarantees  that  such  properties  are  preserved  when
28 iterating the functions on floating point numbers, which is the domain
29 of interpretation of real numbers $\R$ on machines.
30
31 To avoid this  lack of chaos, we have previously  presented some PRNGs
32 that iterate  continuous functions $G_f$  on a discrete domain  $\{ 1,
33 \ldots,  n  \}^{\Nats}  \times  \{0,1\}^n$, where  $f$  is  a  Boolean
34 function  (\textit{i.e.},  $f  :  \{0,1\}^{\mathsf{N}}
35 \rightarrow  \{0,1\}^{\mathsf{N}}$).
36 These         generators          are         $\textit{CIPRNG}_f^1(u)$
37 \cite{guyeuxTaiwan10,bcgr11:ip},            $\textit{CIPRNG}_f^2(u,v)$
38 \cite{wbg10ip}             and             $\chi_{\textit{14Secrypt}}$
39 \cite{DBLP:conf/secrypt/CouchotHGWB14}    where   \textit{CI}    means
40 \emph{Chaotic Iterations}.  We have firstly proven in~\cite{bcgr11:ip}
41 that,    to    establish    the   chaotic    nature    of    algorithm
42 $\textit{CIPRNG}_f^1$,  it  is  necessary   and  sufficient  that  the
43 asynchronous iterations  are strongly  connected. We then  have proven
44 that it is necessary and  sufficient that the Markov matrix associated
45 to  this graph  is  doubly  stochastic, in  order  to  have a  uniform
46 distribution of  the outputs.  We have finally  established sufficient
47 conditions to guarantee the first  property of connectivity. Among the
48 generated   functions,   we   thus   have   considered   for   further
49 investigations  only  the  ones   that  satisfy  the  second  property
50 too.
51
52 However,      it     cannot      be     directly      deduced     that
53 $\chi_{\textit{14Secrypt}}$ is chaotic since we  do not output all the
54 successive values of iterating $G_f$.   This algorithm only displays a
55 subsequence $x^{b.n}$  of a whole  chaotic sequence $x^{n}$ and  it is
56 indeed not correct  that the chaos property is preserved for any
57 subsequence of  a chaotic sequence.  This  article presents conditions
58 to preserve this property.
59
60
61 Finding a Boolean function which provides a  strongly connected
62 iteration graph having a doubly stochastic Markov matrix is however
63 not an easy task.
64 We have firstly proposed in~\cite{bcgr11:ip} a  generate-and-test based
65 approach that solves this issue. However, this one was not efficient enough.
66 Thus, a second scheme has been further presented
67 in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
68 a  $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
69 has been removed is strongly connected and has
70 a doubly stochastic Markov matrix.
71
72 However, the removed Hamiltonian cycle  
73 has a great influence in the quality of the output.
74 For instance, if this one one is not balanced (\textit{i.e.},
75 the number of changes in different bits are completely different),
76 some bits would be hard to switch.
77 This article shows an effective algorithm that efficiently 
78 implements the previous scheme and provides thus functions issued
79 from removing in the $\mathsf{N}$-cube a \emph{balanced} Hamiltonian cycle. 
80
81 The length $b$ of the walk to reach a
82 distribution close to the uniform one would be dramatically long.
83 This article theoretically and practically
84 studies the length $b$ until the corresponding Markov
85 chain is close to the uniform distribution.
86 Finally, the ability of the approach to face classical tests
87 suite is evaluated.
88
89
90
91 This article, which 
92 is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14} 
93 is organized  as  follows. The  next
94 section   is   devoted   to  preliminaries,   basic   notations,   and
95 terminologies   regarding   Boolean    map   iterations.    Then,   in
96 Section~\ref{sec:proofOfChaos},  Devaney's  definition   of  chaos  is
97 recalled  while the  proofs  of chaos  of our  most  general PRNGs  is
98 provided.      This    is     the     first    major     contribution.
99 Section~\ref{sec:SCCfunc}  recalls a general scheme
100 to obtain functions with awaited behavior. Main theorems are recalled
101 to make the document self-content. 
102 The  next  section (Sect.~\ref{sec:hamilton}) presents an algorithm that
103 implements this scheme and proves it always produces a solution.  
104 This  is   the   second   major  contribution
105 The  later section
106 (Sect.~\ref{sec:hypercube}) defines the theoretical framework to study
107 the  mixing-time,  \textit{i.e.},  time  until  reaching  a  uniform
108 distribution. It proves that this one is at worth quadratic in the number
109 of elements. Experiments show that the bound is practically largely much
110 lower. This  is   the   third   major  contribution.    The
111 Section~\ref{sec:prng} gives practical results  on evaluating the PRNG
112 against  the NIST  suite.  This  research  work ends  by a  conclusion
113 section, where the contribution is summarized and intended future work
114 is outlined.
115
116 %%% Local Variables:
117 %%% mode: latex
118 %%% TeX-master: "main"
119 %%% ispell-dictionary: "american"
120 %%% mode: flyspell
121 %%% End: