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 $n$ be a positive integer. A  {\emph{Boolean map} $f$ is
   7 a function from $\Bool^n$
   8 to itself
   9 such that
  10 $x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
  11 Functions are iterated as follows.
  12 At the $t^{th}$ iteration, only the $s_{t}-$th component is
  13 ``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. Formally,
  14 let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
  15 \[
  16 F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
  17 \]
  18 Then, let $x^0\in\Bool^n$ be an initial configuration
  19 and $s\in
  20 \llbracket1;n\rrbracket^\Nats$ be a strategy,
  21 the dynamics are described by the recurrence
  22 \begin{equation}\label{eq:asyn}
  23 x^{t+1}=F_f(s_t,x^t).
  24 \end{equation}
  25
  26
  27 Let be given a Boolean map $f$. Its associated
  28 {\emph{iteration graph}}  $\Gamma(f)$ is the
  29 directed graph such that  the set of vertices is
  30 $\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
  31 the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$.
  32
  33 \begin{xpl}
  34 Let us consider for instance $n=3$.
  35 Let
  36 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
  37 $f^*(x_1,x_2,x_3) =
  38 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
  39 \overline{x_1}\overline{x_3} + x_1x_2)$.
  40 The iteration graph $\Gamma(f^*)$ of this function is given in
  41 Figure~\ref{fig:iteration:f*}.
  42
  43 \vspace{-1em}
  44 \begin{figure}[ht]
  45 \begin{center}
  46 \includegraphics[scale=0.5]{images/iter_f0c}
  47 \end{center}
  48 \vspace{-0.5em}
  49 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
  50 \end{figure}
  51 \end{xpl}
  52
  53 % \vspace{-0.5em}
  54 % It is easy to associate a Markov Matrix $M$ to such a graph $G(f)$
  55 % as follows:
  56
  57 % $M_{ij} = \frac{1}{n}$ if there is an edge from $i$ to $j$ in $\Gamma(f)$ and $i \neq j$;  $M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}$; and $M_{ij} = 0$ otherwise.
  58
  59 % \begin{xpl}
  60 % The Markov matrix associated to the function $f^*$ is
  61
  62 % \[
  63 % M=\dfrac{1}{3} \left(
  64 % \begin{array}{llllllll}
  65 % 1&1&1&0&0&0&0&0 \\
  66 % 1&1&0&0&0&1&0&0 \\
  67 % 0&0&1&1&0&0&1&0 \\
  68 % 0&1&1&1&0&0&0&0 \\
  69 % 1&0&0&0&1&0&1&0 \\
  70 % 0&0&0&0&1&1&0&1 \\
  71 % 0&0&0&0&1&0&1&1 \\
  72 % 0&0&0&1&0&1&0&1
  73 % \end{array}
  74 % \right)
  75 % \]
  76 %\end{xpl}
  77
  78
  79 It is usual to check whether rows of such kind of matrices
  80 converge to a specific
  81 distribution.
  82 Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
  83 which is defined for two distributions $\pi$ and $\mu$ on the same set
  84 $\Omega$  by:
  85 $$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$
  86 % It is known that
  87 % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$
  88
  89 Let then $M(x,\cdot)$ be the
  90 distribution induced by the $x$-th row of $M$. If the Markov chain
  91 induced by
  92 $M$ has a stationary distribution $\pi$, then we define
  93 $$d(t)=\max_{x\in\Omega}\tv{M^t(x,\cdot)-\pi}.$$
  94 Intuitively $d(t)$ is the largest deviation between
  95 the distribution $\pi$ and $M^t(x,\cdot)$, which
  96 is the result of iterating $t$ times the function.
  97 Finally, let $\varepsilon$ be a positive number, the \emph{mixing time}
  98 with respect to $\varepsilon$ is given by
  99 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 100 It defines the smallest iteration number
 101 that is sufficient to obtain a deviation lesser than $\varepsilon$.
 102 % Notice that the upper and lower bounds of mixing times cannot
 103 % directly be computed with eigenvalues formulae as expressed
 104 % in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work
 105 % only consider reversible Markov matrices whereas we do no restrict our
 106 % matrices to such a form.
 107
 108
 109
 110 Let us finally present the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
 111 which is based on random walks in $\Gamma(f)$.
 112 More precisely, let be given a Boolean map $f:\Bool^n \rightarrow \Bool^n$,
 113 a PRNG \textit{Random},
 114 an integer $b$ that corresponds to an awaited mixing time, and
 115 an initial configuration $x^0$.
 116 Starting from $x^0$, the algorithm repeats $b$ times
 117 a random choice of which edge to follow and traverses this edge.
 118 The final configuration is thus outputted.
 119 This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
 120
 121
 122
 123 \vspace{-1em}
 124 \begin{algorithm}[ht]
 125 %\begin{scriptsize}
 126 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
 127 \KwOut{a configuration $x$ ($n$ bits)}
 128 $x\leftarrow x^0$\;
 129 \For{$i=0,\dots,b-1$}
 130 {
 131 $s\leftarrow{\textit{Random}(n)}$\;
 132 $x\leftarrow{F_f(s,x)}$\;
 133 }
 134 return $x$\;
 135 %\end{scriptsize}
 136 \caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
 137 \label{CI Algorithm}
 138 \end{algorithm}
 139 \vspace{-0.5em}
 140 This PRNG is a particularized version of Algorithm given in~\cite{BCGR11}.
 141 Compared to this latter, the length of the random
 142 walk of our algorithm is always constant (and is equal to $b$) whereas it
 143 was given by a second PRNG in this latter.
 144 However, all the theoretical results that are given in~\cite{BCGR11} remain
 145 true since the proofs do not rely on this fact.
 146
 147 Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
 148 It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that
 149 if its iteration graph is strongly connected, then
 150 the output of $\chi_{\textit{14Secrypt}}$ follows
 151 a law that tends to the uniform distribution
 152 if and only if its Markov matrix is a doubly stochastic matrix.
 153
 154 Let us now present  a method to
 155 generate  functions
 156 with Doubly Stochastic matrix and Strongly Connected iteration graph,
 157  denoted as DSSC matrix.
 158