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