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