generating : synthese secrypt + mons

[rairo15.git] / preliminaries.tex

diff --git a/preliminaries.tex b/preliminaries.tex
index 9441aab3a586ced9fb98b0b7d799c13e24d4ffed..1200bc519103d7ac6dbe9a9d3c4d32404fdff062 100644 (file)
--- a/preliminaries.tex
+++ b/preliminaries.tex
@@ -3,36 +3,49 @@ $\Bool=\{0,1\}$ with the classical operators of conjunction '.',
 of disjunction '+', of negation '$\overline{~}$', and of 
 disjunctive union $\oplus$. 
 
 of disjunction '+', of negation '$\overline{~}$', and of 
 disjunctive union $\oplus$. 
 

-Let $n$ be a positive integer. A  {\emph{Boolean map} $f$ is 
-a function from $\Bool^n$  
+Let us first introduce basic notations.
+Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$
+of integers belonging between $1$ and $\mathsf{N}$
+is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$.
+A  {\emph{Boolean map} $f$ is 
+a function from $\Bool^{\mathsf{N}}$  

 to itself 
 such that 
 to itself 
 such that 

-$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
+$x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$.
+In what follows, for any finite set $X$, $|X|$ denotes its cardinality and 
+$\lfloor y \rfloor$ is
+the largest integer lower than $y$.
+

 Functions are iterated as follows. 
 At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
 Functions are iterated as follows. 
 At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be

-``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. 
+``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''. 

 Formally,
 Formally,

-let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
+let $F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by

 \[
 \[

-F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
+F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).

 \]
 \]

-Then, let $x^0\in\Bool^n$ be an initial configuration
+Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration

 and $s\in
 and $s\in

-\llbracket1;n\rrbracket^\Nats$ be a strategy, 
+\llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy, 

 the dynamics are described by the recurrence
 \begin{equation}\label{eq:asyn}
 the dynamics are described by the recurrence
 \begin{equation}\label{eq:asyn}

-x^{t+1}=F_f(s_t,x^t).
+x^{t+1}=F_f(x^t,s_t).

 \end{equation}
 
 
 \end{equation}
 
 

+
+
+

 Let be given a Boolean map $f$. Its associated   
 {\emph{iteration graph}}  $\Gamma(f)$ is the
 directed graph such that  the set of vertices is
 Let be given a Boolean map $f$. Its associated   
 {\emph{iteration graph}}  $\Gamma(f)$ is the
 directed graph such that  the set of vertices is

-$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
-the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. 
+$\Bool^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$.
+Each arc $(x,F_f(x,i))$ is labelled with $i$. 
+

 
 \begin{xpl}
 
 \begin{xpl}

-Let us consider for instance $n=3$.
+Let us consider for instance ${\mathsf{N}}=3$.

 Let 
 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
 $f^*(x_1,x_2,x_3) = 
 Let 
 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
 $f^*(x_1,x_2,x_3) = 


@@ -40,86 +53,49 @@ $f^*(x_1,x_2,x_3) =
 \overline{x_1}\overline{x_3} + x_1x_2)$.
 The iteration graph $\Gamma(f^*)$ of this function is given in 
 Figure~\ref{fig:iteration:f*}.
 \overline{x_1}\overline{x_3} + x_1x_2)$.
 The iteration graph $\Gamma(f^*)$ of this function is given in 
 Figure~\ref{fig:iteration:f*}.

+\end{xpl}

 
 

-\vspace{-1em}

 \begin{figure}[ht]
 \begin{center}
 \includegraphics[scale=0.5]{images/iter_f0c}
 \end{center}
 \begin{figure}[ht]
 \begin{center}
 \includegraphics[scale=0.5]{images/iter_f0c}
 \end{center}

-\vspace{-0.5em}

 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
 \end{figure}
 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
 \end{figure}

-\end{xpl}
-

 
 

-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph 
-where the choice of the edge to follow is decided by the strategy.
-Notice that the iteration graph is always a subgraph of 
-$n$-cube augmented with all the self-loop, \textit{i.e.}, all the 
-edges $(v,v)$ for any $v \in \Bool^n$. 
-Next, if we add probabilities on the transition graph, iterations can be 
-interpreted as Markov chains.
+Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14}
+formalized in Algorithm~\ref{CI Algorithm}.
+It is based on random walks in $\Gamma(f)$. 
+More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$,
+an input PRNG \textit{Random},
+an integer $b$ that corresponds to a number of iterations, 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.
+The final configuration is thus outputted.

 
 

-\begin{xpl}
-Let us consider for instance  
-the graph $\Gamma(f)$ defined 
-in \textsc{Figure~\ref{fig:iteration:f*}.} and 
-the probability function $p$ defined on the set of edges as follows:
-$$
-p(e) \left\{
-\begin{array}{ll}
-= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{6} \textrm{ otherwise.}
-\end{array}
-\right.  
-$$
-The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
-\[
-P=\dfrac{1}{6} \left(
-\begin{array}{llllllll}
-4&1&1&0&0&0&0&0 \\
-1&4&0&0&0&1&0&0 \\
-0&0&4&1&0&0&1&0 \\
-0&1&1&4&0&0&0&0 \\
-1&0&0&0&4&0&1&0 \\
-0&0&0&0&1&4&0&1 \\
-0&0&0&0&1&0&4&1 \\
-0&0&0&1&0&1&0&4 
-\end{array}
-\right)
-\]
-\end{xpl}

 
 

+\begin{algorithm}[ht]
+\begin{scriptsize}
+%\JFC{Mettre ceci dans une boite flottante}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{a configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+\For{$i=0,\dots,b-1$}
+{
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+$x\leftarrow{F_f(x,s)}$\;
+}
+return $x$\;
+\end{scriptsize}
+\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
+\label{CI Algorithm}
+\end{algorithm}

 
 

-% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
-% % $\Bool^n$  by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which 
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number 
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot    
-% directly be computed with eigenvalues formulae as expressed 
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
-% only consider reversible Markov matrices whereas we do no restrict our 
-% matrices to such a form.

 
 
 
 

+With all this material, we can study the chaos properties of these 
+function.
+This is the aims of the next section.