prng.tex

   1 Let us finally present the pseudorandom number generator $\chi_{\textit{16HamG}}$,
   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 crosses 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:2}.
  14
  15
  16
  17 \begin{algorithm}[ht]
  18 %\begin{scriptsize}
  19 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
  20 \KwOut{a configuration $x$ ($\mathsf{N}$ bits)}
  21 $x\leftarrow x^0$\;
  22 \For{$i=0,\dots,b-1$}
  23 {
  24 \If{$\textit{Random}(1) \neq 0$}{
  25 $s^0\leftarrow{\textit{Random}(\mathsf{N})}$\;
  26 $x\leftarrow{F_f(x,s^0)}$\;
  27 }
  28 }
  29 return $x$\;
  30 %\end{scriptsize}
  31 \caption{Pseudo Code of the $\chi_{\textit{16HamG}}$ PRNG}
  32 \label{CI Algorithm:2}
  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 the graph $\Gamma_{\{b\}}(f)$ to be  strongly connected.
  50 Since the $\chi_{\textit{16HamG}}$ 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} and~\ref{sec:hamilton}.
  58 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV)
  59 For each $\mathsf{N}$, we have then restricted this evaluation to the function
  60 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo}))
  61 has the smallest practical mixing time.
  62 Such functions are
  63 given in Table~\ref{table:nc}.
  64 In this table, let us consider, for instance,
  65 the function $\textcircled{a}$ from $\Bool^4$ to $\Bool^4$
  66 defined by the following images :
  67 $[13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]$.
  68 In other words,  the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$:
  69 it is obtained as  the  binary  value  of  the  fourth element  in
  70 the  second  list (namely~14).
  71
  72 In this table the column that is labeled with $b$ %(respectively by $E[\tau]$)
  73 gives the practical mixing time
  74 where the deviation to the standard distribution is inferior than $10^{-6}$.
  75 %(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}).
  76
  77
  78
  79 \begin{table*}[t]
  80 \begin{center}
  81 \begin{scriptsize}
  82 \begin{tabular}{|c|c|c|c|}
  83 \hline
  84 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$
  85 \\
  86 \hline
  87 %%%%% n= 4
  88 $\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\
  89 \hline
  90 %%%%% n= 5
  91 $\textcircled{b}$&
  92 [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\
  93 &
  94  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
  95 &&\\
  96 %%%%% n= 6
  97 \hline
  98 &
  99 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 100 &&\\
 101 &
 102  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 103 &&\\
 104 $\textcircled{c}$&
 105  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13,
 106 &6&88\\
 107 &
 108 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 109 &&\\
 110 %%%%% n= 7
 111 \hline
 112 &
 113 [111, 124, 93, 120, 122, 114, 89, 121, 87, 126, 125, 84, 123, 82,
 114 &&\\
 115 &112, 80, 79, 106, 105, 110, 75, 107, 73, 108, 119, 100, 117, 116,
 116 &&\\
 117 &103, 102, 101, 97, 31, 86, 95, 94, 83, 26, 88, 24, 71, 118, 69,
 118 &&\\
 119 &68, 115, 90, 113, 16, 15, 76, 109, 72, 74, 10, 9, 104, 7, 6, 65,
 120 &&\\
 121 $\textcircled{d}$ &70, 99, 98, 64, 96, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, &7 &99\\
 122 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33,
 123 &&\\
 124 &38, 43, 50, 32, 48, 29, 28, 61, 92, 91, 18, 17, 25, 19, 30, 85,
 125 &&\\
 126 &22, 27, 2, 81, 0, 13, 78, 77, 14, 3, 11, 8, 12, 23, 4, 21, 20,
 127 &&\\
 128 &67, 66, 5, 1]
 129 &&\\
 130
 131
 132 %%%%%n=8
 133 \hline
 134 &
 135 [223, 238, 249, 254, 243, 251, 233, 252, 183, 244, 229, 245, 227,
 136 &&\\
 137 &246, 240, 176, 175, 174, 253, 204, 203, 170, 169, 248, 247, 226,
 138 &&\\
 139 &228, 164, 163, 162, 161, 192, 215, 220, 205, 216, 155, 222, 221,
 140 &&\\
 141 &208, 213, 150, 212, 214, 219, 211, 145, 209, 239, 202, 207, 140,
 142 &&\\
 143 &195, 234, 193, 136, 231, 230, 199, 197, 131, 198, 225, 200, 63,
 144 &&\\
 145 &188, 173, 184, 186, 250, 57, 168, 191, 178, 180, 52, 187, 242,
 146 &&\\
 147 &241, 48, 143, 46, 237, 236, 235, 138, 185, 232, 135, 38, 181, 165,
 148 &&\\
 149 &35, 166, 33, 224, 31, 30, 153, 158, 147, 218, 217, 156, 159, 148,
 150 &&\\
 151 $\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 128,
 152 &8&109\\
 153 &133, 130, 132, 196, 3, 194, 137, 0, 255, 124, 109, 120, 122, 106,
 154 &&\\
 155 &125, 104, 103, 114, 116, 118, 123, 98, 97, 113, 79, 126, 111, 110,
 156 &&\\
 157 &99, 74, 121, 72, 71, 70, 117, 101, 115, 102, 65, 112, 127, 90, 89,
 158 &&\\
 159 &94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93,
 160 &&\\
 161 &108, 107, 78, 105, 64, 69, 66, 68, 100, 75, 67, 73, 96, 55, 190,
 162 &&\\
 163 &189, 62, 51, 59, 41, 60, 119, 182, 37, 53, 179, 54, 177, 32, 45,
 164 &&\\
 165 &44, 61, 172, 11, 58, 9, 56, 167, 34, 36, 4, 43, 50, 49, 160, 23,
 166 &&\\
 167 &28, 157, 24, 26, 154, 29, 16, 21, 18, 20, 22, 27, 146, 25, 17, 47,
 168 &&\\
 169 &142, 15, 14, 139, 42, 1, 40, 39, 134, 7, 5, 2, 6, 129, 8]
 170 &&\\
 171 \hline
 172 \end{tabular}
 173 \end{scriptsize}
 174 \end{center}
 175 \caption{Functions with DSCC Matrix and smallest MT}\label{table:nc}
 176 \end{table*}
 177
 178
 179
 180 Let us first discuss about results against the NIST test suite.
 181 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
 182 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough
 183 and the generator is unsuitable.
 184
 185 Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based
 186 on $\chi_{\textit{16HamG}}$ using different functions, namely
 187 $\textcircled{a}$,\ldots, $\textcircled{e}$.
 188 In this algorithm implementation,
 189 the embedded PRNG \textit{Random} is the default Python PRNG, \textit{i.e.},
 190 the Mersenne Twister algorithm~\cite{matsumoto1998mersenne}.
 191 Implementations for $\mathsf{N}=4, \dots, 8$ of this algorithm is evaluated
 192 through the NIST test suite and results are given in columns
 193 $\textit{MT}_4$, \ldots,  $\textit{MT}_8$.
 194 If there are at least two statistical values in a test, this test is
 195 marked with an asterisk and the average value is computed to characterize the statistics.
 196
 197 We first can see in Table \ref{The passing rate} that all the rates
 198 are greater than 97/100, \textit{i.e.}, all the generators
 199 achieve to pass the NIST battery of tests.
 200 It can be noticed that adding chaos properties for Mersenne Twister
 201 algorithm does not reduce its security against this statistical tests.
 202
 203
 204 \begin{table*}
 205 \renewcommand{\arraystretch}{1.1}
 206 \begin{center}
 207 \begin{tiny}
 208 \setlength{\tabcolsep}{2pt}
 209
 210 \begin{tabular}{|l|r|r|r|r|r|}
 211  \hline
 212 Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$
 213  \\ \hline
 214 Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99) \\ \hline
 215 Frequency  within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)\\ \hline
 216 Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)\\ \hline
 217 Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)\\ \hline
 218 Longest Run of Ones in a Block& 0.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)\\ \hline
 219 Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)\\ \hline
 220 Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)\\ \hline
 221 Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)\\ \hline
 222 Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)\\ \hline
 223 Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)\\ \hline
 224 Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)\\ \hline
 225 Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)\\ \hline
 226 Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)\\ \hline
 227 Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)\\ \hline
 228 Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)\\ \hline
 229 \end{tabular}
 230
 231 \begin{tabular}{|l|r|r|r|r|r|}
 232  \hline
 233 Test
 234 &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline
 235 Frequency (Monobit)&0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline
 236 Frequency  within a Block& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline
 237 Cumulative Sums (Cusum) *& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline
 238 Runs&  0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline
 239 Longest Run of Ones in a Block&  0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline
 240 Binary Matrix Rank& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline
 241 Discrete Fourier Transform (Spectral)&  0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline
 242 Non-overlapping Template Matching*& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline
 243 Overlapping Template Matching&  0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline
 244 Maurer's "Universal Statistical"&  0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline
 245 Approximate Entropy (m=10)&  0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline
 246 Random Excursions *& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline
 247 Random Excursions Variant *& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline
 248 Serial* (m=10)&0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline
 249 Linear Complexity& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline
 250 \end{tabular}
 251
 252 \end{tiny}
 253 \end{center}
 254 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 255 \label{The passing rate}
 256 \end{table*}
 257
 258
 259 %%% Local Variables:
 260 %%% mode: latex
 261 %%% TeX-master: "main"
 262 %%% ispell-dictionary: "american"
 263 %%% mode: flyspell
 264 %%% End: