prng.tex

   1 Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$,
   2 which is based on random walks in $\Gamma_{\{b\}}(f)$.
   3 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow
   4 \Bool^\mathsf{N}$,
   5 a PRNG \textit{Random},
   6 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and
   7 an initial configuration $x^0$.
   8 Starting from $x^0$, the algorithm repeats $b$ times
   9 a random choice of which edge to follow, and traverses this edge
  10 provided it is allowed to do so, \textit{i.e.},
  11 when $\textit{Random}(1)$ is not null.
  12 The final configuration is thus outputted.
  13 This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
  14
  15
  16
  17 \begin{algorithm}[ht]
  18 %\begin{scriptsize}
  19 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
  20 \KwOut{a configuration $x$ ($n$ bits)}
  21 $x\leftarrow x^0$\;
  22 \For{$i=0,\dots,b-1$}
  23 {
  24 \If{$\textit{Random}(1) \neq 0$}{
  25 $s\leftarrow{\textit{Random}(n)}$\;
  26 $x\leftarrow{F_f(s,x)}$\;
  27 }
  28 }
  29 return $x$\;
  30 %\end{scriptsize}
  31 \caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
  32 \label{CI Algorithm}
  33 \end{algorithm}
  34
  35
  36 This PRNG is slightly different from $\chi_{\textit{14Secrypt}}$
  37 recalled in Algorithm~\ref{CI Algorithm}.
  38 As this latter, the length of the random
  39 walk of our algorithm is always constant (and is equal to $b$).
  40 However, in the current version, we add the constraint that
  41 the probability to execute the function $F_f$ is equal to 0.5 since
  42 the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.
  43 This constraint is added to match the theoretical framework of
  44 Sect.~\ref{sec:hypercube}.
  45
  46
  47
  48 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}
  49 only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected.
  50 Since the $\chi_{\textit{15Rairo}}$ algorithm
  51 only adds probability constraints on existing edges,
  52 it preserves this property.
  53
  54
  55 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated
  56 the functions according to the method
  57 given in Sect.~\ref{sec:SCCfunc}.
  58 For each $\mathsf{N}$, we have then restricted this evaluation to the function
  59 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo}))
  60 has the smallest practical mixing time.
  61 Such functions are
  62 given in Table~\ref{table:nc}.
  63 In this table, let us consider for instance
  64 the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$
  65 defined by the following images :
  66 $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$.
  67 In other words,  the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$:
  68 it is obtained as  the  binary  value  of  the  fourth element  in
  69 the  second  list (namely~14).
  70
  71 In this table the column
  72 that is labeled with $b$ (respectively by $E[\tau]$)
  73 gives the practical mixing time
  74 where the deviation to the standard distribution is lesser than $10^{-6}$
  75 (resp. the theoretical upper bound of stopping time as described in
  76 Sect.~\ref{sec:hypercube}).
  77
  78
  79
  80 \begin{table*}[t]
  81 \begin{center}
  82 \begin{scriptsize}
  83 \begin{tabular}{|c|c|c|c|c|}
  84 \hline
  85 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
  86 &$E[\tau]$\\
  87 \hline
  88 %%%%% n= 4
  89 $\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&\\
  90 \hline
  91 %%%%% n= 5
  92 $\textcircled{b}$&
  93 [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & \\
  94 &
  95  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
  96 &&&\\
  97 %%%%% n= 6
  98 \hline
  99 &
 100 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 101 &&&\\
 102 &
 103  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 104 &&&\\
 105 $\textcircled{c}$&
 106  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13,
 107 &6&88&\\
 108 &
 109 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 110 &&&\\
 111 %%%%% n= 7
 112 \hline
 113 &
 114 [111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98,
 115 &&&\\
 116 &
 117  81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118,  117,
 118  &&&\\
 119 &
 120 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22,
 121 &&&\\
 122 $\textcircled{d}$&
 123 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
 124 &7 & 99&\\
 125
 126 &
 127  101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,
 128 &&&\\
 129 &
 130  37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34,
 131 &&&\\
 132 &
 133 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30,
 134 &&&\\
 135 &
 136 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21,
 137 &&&\\
 138 &
 139 68, 7, 6, 65, 1]
 140 &&&\\
 141
 142
 143 %%%%%n=8
 144 \hline
 145 &
 146 [223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227,
 147 &&&\\
 148 &
 149 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166,
 150 &&&\\
 151 &
 152 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221,
 153 &&&\\
 154 &
 155 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140,
 156 &&&\\
 157 &
 158 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159,
 159 &&&\\
 160 &
 161 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176,
 162 &&&\\
 163 &
 164 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35,
 165 &&&\\
 166 &
 167 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146,
 168 &&&\\
 169 &
 170 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129,
 171 &&&\\
 172 $\textcircled{e}$&
 173 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
 174 &8&110&\\
 175 &
 176  126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
 177 &&&\\
 178 &
 179  111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65,
 180 &&&\\
 181 &
 182 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86,
 183 &&&\\
 184 &
 185 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75,
 186 &&&\\
 187 &
 188 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181,
 189 &&&\\
 190 &
 191 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6,
 192 &&&\\
 193 &
 194  36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31,
 195 &&&\\
 196 &
 197 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12,
 198 &&&\\
 199 &
 200 39, 134, 133, 5, 131, 34, 9, 128]
 201 &&&\\
 202 \hline
 203 \end{tabular}
 204 \end{scriptsize}
 205 \end{center}
 206 \caption{Functions with DSCC Matrix and smallest MT\label{table:nc}}
 207 \end{table*}
 208
 209
 210
 211 Let us first discuss about results against the NIST test suite.
 212 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
 213 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough
 214 and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete
 215 chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is
 216 marked with an asterisk and the average value is computed to characterize the statistics.
 217 We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators
 218 achieve to pass the NIST battery of tests.
 219
 220
 221
 222 \begin{table}
 223 \renewcommand{\arraystretch}{1.3}
 224 \begin{center}
 225 \begin{scriptsize}
 226 \setlength{\tabcolsep}{2pt}
 227
 228
 229 \end{scriptsize}
 230 \end{center}
 231 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 232 \label{The passing rate}
 233 \end{table}
 234
 235