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 a general scheme which generates
  11 function with strongly connected iteration graph $\Gamma(f)$ and
  12 with doubly stochastic Markov probability matrix.
  13
  14 Basically, let us consider the ${\mathsf{N}}$-cube. Let us next
  15 remove one Hamiltonian cycle in this one. When an edge $(x,y)$
  16 is removed, an edge $(x,x)$ is added.
  17
  18 \begin{xpl}
  19 For instance, the iteration graph $\Gamma(f^*)$
  20 (given in Figure~\ref{fig:iteration:f*})
  21 is the $3$-cube in which the Hamiltonian cycle
  22 $000,100,101,001,011,111,110,010,000$
  23 has been removed.
  24 \end{xpl}
  25
  26 We first have proven the following result, which
  27 states that the ${\mathsf{N}}$-cube without one
  28 Hamiltonian cycle
  29 has the awaited property with regard to the connectivity.
  30
  31 \begin{thrm}
  32 The iteration graph $\Gamma(f)$ issued from
  33 the ${\mathsf{N}}$-cube where an Hamiltonian
  34 cycle is removed is strongly connected.
  35 \end{thrm}
  36
  37 Moreover, if all the transitions have the same probability ($\frac{1}{n}$),
  38 we have proven the following results:
  39 \begin{thrm}
  40 The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in
  41 which an Hamiltonian
  42 cycle is removed, is doubly stochastic.
  43 \end{thrm}
  44
  45 Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian
  46 cycle is removed.
  47 Let $f$ be the corresponding function.
  48 The question which remains to solve is:
  49 \emph{can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected?}
  50
  51 The answer is indeed positive. We furthermore have the following strongest
  52 result.
  53 \begin{thrm}
  54 There exists $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
  55 \end{thrm}
  56 \begin{proof}
  57 There is an arc $(x,y)$ in the
  58 graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
  59 where $M$ is the Markov matrix of $\Gamma(f)$.
  60 It has been shown in~\cite[Lemma 3]{bcgr11:ip}  that $M$ is regular.
  61 Thus, there exists $b$ such that there is an arc between any $x$ and $y$.
  62 \end{proof}
  63
  64 This section ends with the idea of removing a Hamiltonian cycle in the
  65 $\mathsf{N}$-cube.
  66 In such a context, the Hamiltonian cycle is equivalent to a Gray code.
  67 Many approaches have been proposed a way to build such codes, for instance
  68 the Reflected Binary Code. In this one and
  69 for a $\mathsf{N}$-length cycle, one of the bits is exactly switched
  70 $2^{\mathsf{N}-1}$ times whereas the others bits are modified at most
  71 $\left\lfloor \dfrac{2^{\mathsf{N-1}}}{\mathsf{N}-1} \right\rfloor$ times.
  72 It is clear that the function that is built from such a code would
  73 not provide a uniform output.
  74
  75 The next section presents how to build balanced Hamiltonian cycles in the
  76 $\mathsf{N}$-cube with the objective to embed them into the
  77 pseudorandom number generator.
  78
  79 %%% Local Variables:
  80 %%% mode: latex
  81 %%% TeX-master: "main"
  82 %%% ispell-dictionary: "american"
  83 %%% mode: flyspell
  84 %%% End: