preliminaries.tex

   1 In what follows, we consider the Boolean algebra on the set
   2 $\Bool=\{0,1\}$ with the classical operators of conjunction '.',
   3 of disjunction '+', of negation '$\overline{~}$', and of
   4 disjunctive union $\oplus$.
   5
   6 Let us first introduce basic notations.
   7 Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$
   8 of integers belonging between $1$ and $\mathsf{N}$
   9 is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$.
  10 A  {\emph{Boolean map} $f$ is
  11 a function from $\Bool^{\mathsf{N}}$
  12 to itself
  13 such that
  14 $x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$.
  15 In what follows, for any finite set $X$, $|X|$ denotes its cardinality and
  16 $\lfloor y \rfloor$ is
  17 the largest integer lower than $y$.
  18
  19 Functions are iterated as follows.
  20 At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
  21 ``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''.
  22 Formally,
  23 let $F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by
  24 \[
  25 F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
  26 \]
  27 Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration
  28 and $s\in
  29 \llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy,
  30 the dynamics are described by the recurrence
  31 \begin{equation}\label{eq:asyn}
  32 x^{t+1}=F_f(x^t,s_t).
  33 \end{equation}
  34
  35
  36
  37
  38
  39 Let be given a Boolean map $f$. Its associated
  40 {\emph{iteration graph}}  $\Gamma(f)$ is the
  41 directed graph such that  the set of vertices is
  42 $\Bool^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$,
  43 the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$.
  44 Each arc $(x,F_f(x,i))$ is labelled with $i$.
  45
  46
  47 \begin{xpl}
  48 Let us consider for instance ${\mathsf{N}}=3$.
  49 Let
  50 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
  51 $f^*(x_1,x_2,x_3) =
  52 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
  53 \overline{x_1}\overline{x_3} + x_1x_2)$.
  54 The iteration graph $\Gamma(f^*)$ of this function is given in
  55 Figure~\ref{fig:iteration:f*}.
  56 \end{xpl}
  57
  58 \begin{figure}[ht]
  59 \begin{center}
  60 \includegraphics[scale=0.5]{images/iter_f0c}
  61 \end{center}
  62 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
  63 \end{figure}
  64
  65 Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
  66 \cite{DBLP:conf/secrypt/CouchotHGWB14}
  67 formalized in Algorithm~\ref{CI Algorithm}.
  68 It is based on random walks in $\Gamma(f)$.
  69 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$,
  70 an input PRNG \textit{Random},
  71 an integer $b$ that corresponds to a number of iterations, and
  72 an initial configuration $x^0$.
  73 Starting from $x^0$, the algorithm repeats $b$ times
  74 a random choice of which edge to follow and traverses this edge.
  75 The final configuration is thus outputted.
  76
  77
  78 \begin{algorithm}[ht]
  79 \begin{scriptsize}
  80 %\JFC{Mettre ceci dans une boite flottante}
  81 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ (${\mathsf{N}}$ bits)}
  82 \KwOut{a configuration $x$ (${\mathsf{N}}$ bits)}
  83 $x\leftarrow x^0$\;
  84 \For{$i=0,\dots,b-1$}
  85 {
  86 $s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
  87 $x\leftarrow{F_f(x,s)}$\;
  88 }
  89 return $x$\;
  90 \end{scriptsize}
  91 \caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
  92 \label{CI Algorithm}
  93 \end{algorithm}
  94
  95
  96
  97 With all this material, we can study the chaos properties of these
  98 function.
  99 This is the aims of the next section.
 100
 101