X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/07a05f881830e54c344db7060dfbfd74220d0eec..5207d2fe1ec5d598398e217569e592f0fb6a07ff:/prng.tex

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