preliminaries.tex

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