generating.tex

   1 First of all, let $f: \Bool^{{\mathsf{N}}} \rightarrow \Bool^{{\mathsf{N}}}$.
   2 It has been shown~\cite[Theorem 4]{bcgr11:ip} that
   3 if its iteration graph $\Gamma(f)$ is strongly connected, then
   4 the output of $\chi_{\textit{14Secrypt}}$ follows
   5 a law that tends to the uniform distribution
   6 if and only if its Markov matrix is a doubly stochastic matrix.
   7
   8
   9 In~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14},
  10 we have presented an efficient
  11 approach which generates
  12 function with strongly connected iteration graph $\Gamma(f)$ and
  13 with doubly stochastic Markov probability matrix.
  14
  15 Basically, let consider the ${\mathsf{N}}$-cube. Let us next
  16 remove one Hamiltonian cycle in this one. When an edge $(x,y)$
  17 is removed, an edge $(x,x)$ is added.
  18
  19 \begin{xpl}
  20 For instance, the iteration graph $\Gamma(f^*)$
  21 (given in Figure~\ref{fig:iteration:f*})
  22 is the $3$-cube in which the Hamiltonian cycle
  23 $000,100,101,001,011,111,110,010,000$
  24 has been removed.
  25 \end{xpl}
  26
  27 We first have proven the following result, which
  28 states that the ${\mathsf{N}}$-cube without one
  29 Hamiltonian cycle
  30 has the awaited property with regard to the connectivity.
  31
  32 \begin{thrm}
  33 The iteration graph $\Gamma(f)$ issued from
  34 the ${\mathsf{N}}$-cube where an Hamiltonian
  35 cycle is removed is strongly connected.
  36 \end{thrm}
  37
  38 Moreover, if all the transitions have the same probability ($\frac{1}{n}$),
  39 we have proven the following results:
  40 \begin{thrm}
  41 The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in
  42 which an Hamiltonian
  43 cycle is removed, is doubly stochastic.
  44 \end{thrm}
  45
  46 Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian
  47 cycle is removed.
  48 Let $f$ be the corresponding function.
  49 The question which remains to solve is
  50 can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected.
  51
  52 The answer is indeed positive. We furtheremore have the following strongest
  53 result.
  54 \begin{thrm}
  55 There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
  56 \end{thrm}
  57 \begin{proof}
  58 There is an arc $(x,y)$ in the
  59 graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
  60 where $M$ is the Markov matrix of $\Gamma(f)$.
  61 It has been shown in~\cite[Lemma 3]{bcgr11:ip}  that $M$ is regular.
  62 There exists thus $b$ such there is an arc between any $x$ and $y$.
  63 \end{proof}
  64
  65 The next section presents how to build hamiltonian cycles in the
  66 $\mathsf{N}$-cube with the objective to embed them into the
  67 pseudorandom number generator.