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, 90, 113, 88, 115, 126, 125, 84, 123, 98,
 114 &&\\
 115 &112, 96, 109, 106, 77, 110, 99, 74, 104, 72, 71, 100, 117, 116,
 116 &&\\
 117 &103, 102, 65, 97, 31, 86, 95, 28, 27, 91, 121, 92, 119, 118, 69,
 118 &&\\
 119 &68, 87, 114, 89, 81, 15, 76, 79, 108, 107, 10, 105, 8, 7, 6, 101,
 120 &&\\
 121 $\textcircled{d}$&70, 75, 82, 64, 0, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37,
 122 &&\\
 123 &36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33,
 124 &&\\
 125 &38, 43, 50, 32, 48, 29, 94, 61, 24, 26, 18, 17, 25, 19, 30, 85,
 126 &&\\
 127 &22, 83, 2, 16, 80, 13, 78, 9, 14, 3, 11, 73, 12, 23, 4, 21, 20,
 128 &&\\
 129 &67, 66, 5, 1] &&\\
 130 %%%%%n=8
 131 \hline
 132 &
 133 [223, 238, 249, 254, 243, 251, 233, 252, 183, 244, 229, 245, 227,
 134 &&\\
 135 &246, 240, 176, 175, 174, 253, 204, 203, 170, 169, 248, 247, 226,
 136 &&\\
 137 &228, 164, 163, 162, 161, 192, 215, 220, 205, 216, 155, 222, 221,
 138 &&\\
 139 &208, 213, 150, 212, 214, 219, 211, 145, 209, 239, 202, 207, 140,
 140 &&\\
 141 &195, 234, 193, 136, 231, 230, 199, 197, 131, 198, 225, 200, 63,
 142 &&\\
 143 &188, 173, 184, 186, 250, 57, 168, 191, 178, 180, 52, 187, 242,
 144 &&\\
 145 &241, 48, 143, 46, 237, 236, 235, 138, 185, 232, 135, 38, 181, 165,
 146 &&\\
 147 &35, 166, 33, 224, 31, 30, 153, 158, 147, 218, 217, 156, 159, 148,
 148 &&\\
 149 $\textcircled{e}$&151, 149, 19, 210, 144, 152, 141, 206, 13, 12, 171, 10, 201, 128,
 150 &8&109\\
 151 &133, 130, 132, 196, 3, 194, 137, 0, 255, 124, 109, 120, 122, 106,
 152 &&\\
 153 &125, 104, 103, 114, 116, 118, 123, 98, 97, 113, 79, 126, 111, 110,
 154 &&\\
 155 &99, 74, 121, 72, 71, 70, 117, 101, 115, 102, 65, 112, 127, 90, 89,
 156 &&\\
 157 &94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93,
 158 &&\\
 159 &108, 107, 78, 105, 64, 69, 66, 68, 100, 75, 67, 73, 96, 55, 190,
 160 &&\\
 161 &189, 62, 51, 59, 41, 60, 119, 182, 37, 53, 179, 54, 177, 32, 45,
 162 &&\\
 163 &44, 61, 172, 11, 58, 9, 56, 167, 34, 36, 4, 43, 50, 49, 160, 23,
 164 &&\\
 165 &28, 157, 24, 26, 154, 29, 16, 21, 18, 20, 22, 27, 146, 25, 17, 47,
 166 &&\\
 167 &142, 15, 14, 139, 42, 1, 40, 39, 134, 7, 5, 2, 6, 129, 8]
 168 &&\\
 169 \hline
 170 \end{tabular}
 171 \end{scriptsize}
 172 \end{center}
 173 \caption{Functions with DSCC Matrix and smallest MT\label{table:nc}}
 174 \end{table*}
 175
 176
 177
 178 Let us first discuss about results against the NIST test suite.
 179 In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested.
 180 If the value $\mathbb{P}_T$ of any test is smaller than 0.0001, the sequences are considered to be not good enough
 181 and the generator is unsuitable. Table~\ref{The passing rate} shows $\mathbb{P}_T$ of sequences based on discrete
 182 chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is
 183 marked with an asterisk and the average value is computed to characterize the statistics.
 184 We can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators
 185 achieve to pass the NIST battery of tests.
 186
 187
 188
 189 \begin{table*}
 190 \renewcommand{\arraystretch}{1.3}
 191 \begin{center}
 192 \begin{scriptsize}
 193 \setlength{\tabcolsep}{2pt}
 194
 195
 196 \begin{tabular}{|l|l|l|l|l|l|}
 197 \hline
 198 Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$   \\ \hline\hline
 199 Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
 200 Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline
 201 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
 202 Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline
 203 Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline
 204 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
 205 Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline
 206 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
 207 Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline
 208 Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline
 209 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
 210 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
 211 Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline
 212 Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline
 213 Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline
 214 Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline
 215 \end{tabular}
 216 \end{scriptsize}
 217 \end{center}
 218 \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)}
 219 \label{The passing rate}
 220 \end{table*}
 221
 222
 223 %%% Local Variables:
 224 %%% mode: latex
 225 %%% TeX-master: "main"
 226 %%% ispell-dictionary: "american"
 227 %%% mode: flyspell
 228 %%% End: