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 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: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 that the graph $\Gamma_{\{b\}}(f)$ is 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 lesser 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 aginst this statistical tests.
 202
 203
 204 \begin{table*}
 205 \renewcommand{\arraystretch}{1.3}
 206 \begin{center}
 207 \begin{tiny}
 208 \setlength{\tabcolsep}{2pt}
 209
 210
 211 % \begin{tabular}{|l|l|l|l|l|l|}
 212 % \hline
 213 % Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$   \\ \hline\hline
 214 % Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
 215 % Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
 216 % Frequency  within a Block& 0.262 (0.98)& 0.699 (0.98)& 0.867 (0.99)& 0.145 (1.0)& 0.455 (0.99)\\ \hline
 217 % Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline
 218 % Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline
 219 % Longest Run of 1s & 0.383 (1.0)& 0.474 (1.0)& 0.983 (0.99)& 0.699 (0.98)& 0.897 (0.96)\\ \hline
 220 % Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline
 221 % Disc. Fourier Transf. (Spect.)& 0.474 (1.0)& 0.739 (0.99)& 0.012 (1.0)& 0.678 (0.98)& 0.437 (0.99)\\ \hline
 222 % Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline
 223 % Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline
 224 % Maurer's Universal Statistical& 0.759 (0.96)& 0.699 (0.97)& 0.191 (0.98)& 0.699 (1.0)& 0.798 (0.97)\\ \hline
 225 % Approximate Entropy (m=10)& 0.759 (0.99)& 0.162 (0.99)& 0.867 (0.99)& 0.534 (1.0)& 0.616 (0.99)\\ \hline
 226 % Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline
 227 % Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline
 228 % Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline
 229 % Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline
 230 \begin{tabular}{|l|r|r|r|r|r||r|r|r|r|r|}
 231  \hline
 232 Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$
 233 &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline
 234 Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99)& 0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline
 235 Frequency  within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline
 236 Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline
 237 Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)& 0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline
 238 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)& 0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline
 239 Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline
 240 Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)& 0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline
 241 Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline
 242 Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)& 0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline
 243 Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)& 0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline
 244 Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)& 0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline
 245 Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline
 246 Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline
 247 Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)& 0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline
 248 Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline
 249 \end{tabular}
 250 \end{tiny}
 251 \end{center}
 252 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 253 \label{The passing rate}
 254 \end{table*}
 255
 256
 257 %%% Local Variables:
 258 %%% mode: latex
 259 %%% TeX-master: "main"
 260 %%% ispell-dictionary: "american"
 261 %%% mode: flyspell
 262 %%% End: