prng.tex

   1 Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$
   2 which is based on random walks in $\Gamma(f)$.
   3 More precisely, let be given a Boolean map $f:\Bool^n \rightarrow \Bool^n$,
   4 a PRNG \textit{Random},
   5 an integer $b$ that corresponds an iteration number (\textit{i.e.}, the length of the walk), and
   6 an initial configuration $x^0$.
   7 Starting from $x^0$, the algorithm repeats $b$ times
   8 a random choice of which edge to follow and traverses this edge
   9 provided it is allowed to traverse it, \textit{i.e.},
  10 when $\textit{Random}(1)$ is not null.
  11 The final configuration is thus outputted.
  12 This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
  13
  14
  15
  16 \begin{algorithm}[ht]
  17 %\begin{scriptsize}
  18 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
  19 \KwOut{a configuration $x$ ($n$ bits)}
  20 $x\leftarrow x^0$\;
  21 \For{$i=0,\dots,b-1$}
  22 {
  23 \If{$\textit{Random}(1) \neq 0$}{
  24 $s\leftarrow{\textit{Random}(n)}$\;
  25 $x\leftarrow{F_f(s,x)}$\;
  26 }
  27 }
  28 return $x$\;
  29 %\end{scriptsize}
  30 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
  31 \label{CI Algorithm}
  32 \end{algorithm}
  33
  34
  35 This PRNG is a particularized version of Algorithm given in~\cite{DBLP:conf/secrypt/CouchotHGWB14}.
  36 As this latter, the length of the random
  37 walk of our algorithm is always constant (and is equal to $b$).
  38 However, in the current version, we add the constraint that
  39 the probability to execute the function $F_f$ is equal to 0.5 since
  40 the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.
  41
  42 Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
  43 It has been shown~\cite[Th. 4, p. 135]{bcgr11:ip} that
  44 if its iteration graph is strongly connected, then
  45 the output of $\chi_{\textit{14Secrypt}}$ follows
  46 a law that tends to the uniform distribution
  47 if and only if its Markov matrix is a doubly stochastic matrix.
  48
  49 Let us now present  a method to
  50 generate  functions
  51 with Doubly Stochastic matrix and Strongly Connected iteration graph,
  52 denoted as DSSC matrix.