X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/a51608c746760d82cb96c37061470f6cda53b08c..3abda4f59d76446238e6b891bc14e1ac7b44c34a:/supplementary.tex diff --git a/supplementary.tex b/supplementary.tex index 2ab8f9c..1ad62e6 100644 --- a/supplementary.tex +++ b/supplementary.tex @@ -16,7 +16,6 @@ \usepackage{ctable} \usepackage{tabularx} \usepackage{multirow} - % Pour mathds : les ensembles IR, IN, etc. \usepackage{dsfont} @@ -26,6 +25,10 @@ \usepackage{graphicx} % Pour faire des sous-figures dans les figures \usepackage{subfigure} +\usepackage{xr-hyper} +\usepackage{hyperref} +\externaldocument[M-]{prng_gpu} +%\usepackage{hyperref} \newtheorem{notation}{Notation} @@ -39,7 +42,7 @@ -\title{Supplementary of ``Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU''} +\title{Annex document of ``Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU''} \begin{document} \author{Jacques M. Bahi, Rapha\"{e}l Couturier, Christophe @@ -52,6 +55,255 @@ Guyeux, and Pierre-Cyrille Héam\thanks{Authors in alphabetic order}} \IEEEpeerreviewmaketitle +\section{Proofs of Chaos of the General Formulation of the Chaotic Iterations} +\label{deuxième def} +Let us consider the discrete dynamical systems in chaotic iterations having +the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in +\llbracket1;\mathsf{N}\rrbracket $, + +\begin{equation} + x_i^n=\left\{ +\begin{array}{ll} + x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\ + \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n. +\end{array}\right. +\label{general CIs} +\end{equation} + +In other words, at the $n^{th}$ iteration, only the cells whose id is +contained into the set $S^{n}$ are iterated. + +Let us now rewrite these general chaotic iterations as usual discrete dynamical +system of the form $X^{n+1}=f(X^n)$ on an ad hoc metric space. Such a formulation +is required in order to study the topological behavior of the system. + +Let us introduce the following function: +\begin{equation} +\begin{array}{cccc} + \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\ + & (i,X) & \longmapsto & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X, \end{array}\right. +\end{array} +\end{equation} +where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$. + +Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: +$F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} +\longrightarrow \mathds{B}^{\mathsf{N}}$ +\begin{equation*} +\begin{array}{rll} + (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% +\end{array}% +\end{equation*}% +where + and . are the Boolean addition and product operations, and $\overline{x}$ +is the negation of the Boolean $x$. +Consider the phase space: +\begin{equation} +\mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times +\mathds{B}^\mathsf{N}, +\end{equation} +\noindent and the map defined on $\mathcal{X}$: +\begin{equation} +G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant... +\end{equation} +\noindent where $\sigma$ is the \emph{shift} function defined by $\sigma +(S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in +\mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function} +$i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$. +Then the general chaotic iterations defined in Equation \ref{general CIs} can +be described by the following discrete dynamical system: +\begin{equation} +\left\{ +\begin{array}{l} +X^0 \in \mathcal{X} \\ +X^{k+1}=G_{f}(X^k).% +\end{array}% +\right. +\end{equation}% + +Once more, a shift function appears as a component of these general chaotic +iterations. + +To study the Devaney's chaos property, a distance between two points +$X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be defined. +Let us introduce: +\begin{equation} +d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}), +\label{nouveau d} +\end{equation} +\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}% + }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and +$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}% + \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$, +%%RAPH : ici, j'ai supprimé tous les sauts à la ligne +%% \begin{equation} +%% \left\{ +%% \begin{array}{lll} +%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% +%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\ +%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% +%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.% +%% \end{array}% +%% \right. +%% \end{equation} +where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as +$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$. + + +\begin{proposition} +The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$. +\end{proposition} + +\begin{proof} + $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance +too, thus $d$, as being the sum of two distances, will also be a distance. + \begin{itemize} +\item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then +$d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then +$\forall k \in \mathds{N}, |S^k\Delta {S}^k|=0$, and so $\forall k, S^k=\check{S}^k$. + \item $d_s$ is symmetric +($d_s(S,\check{S})=d_s(\check{S},S)$) due to the commutative property +of the symmetric difference. +\item Finally, $|S \Delta S''| = |(S \Delta \varnothing) \Delta S''|= |S \Delta (S'\Delta S') \Delta S''|= |(S \Delta S') \Delta (S' \Delta S'')|\leqslant |S \Delta S'| + |S' \Delta S''|$, +and so for all subsets $S,S',$ and $S''$ of $\llbracket 1, \mathsf{N} \rrbracket$, +we have $d_s(S,S'') \leqslant d_e(S,S')+d_s(S',S'')$, and the triangle +inequality is obtained. + \end{itemize} +\end{proof} + + +Before being able to study the topological behavior of the general +chaotic iterations, we must first establish that: + +\begin{proposition} + For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on +$\left( \mathcal{X},d\right)$. +\end{proposition} + + +\begin{proof} +We use the sequential continuity. +Let $(S^n,E^n)_{n\in \mathds{N}}$ be a sequence of the phase space $% +\mathcal{X}$, which converges to $(S,E)$. We will prove that $\left( +G_{f}(S^n,E^n)\right) _{n\in \mathds{N}}$ converges to $\left( +G_{f}(S,E)\right) $. Let us remark that for all $n$, $S^n$ is a strategy, +thus, we consider a sequence of strategies (\emph{i.e.}, a sequence of +sequences).\newline +As $d((S^n,E^n);(S,E))$ converges to 0, each distance $d_{e}(E^n,E)$ and $d_{s}(S^n,S)$ converges +to 0. But $d_{e}(E^n,E)$ is an integer, so $\exists n_{0}\in \mathds{N},$ $% +d_{e}(E^n,E)=0$ for any $n\geqslant n_{0}$.\newline +In other words, there exists a threshold $n_{0}\in \mathds{N}$ after which no +cell will change its state: +$\exists n_{0}\in \mathds{N},n\geqslant n_{0}\Rightarrow E^n = E.$ + +In addition, $d_{s}(S^n,S)\longrightarrow 0,$ so $\exists n_{1}\in % +\mathds{N},d_{s}(S^n,S)<10^{-1}$ for all indexes greater than or equal to $% +n_{1}$. This means that for $n\geqslant n_{1}$, all the $S^n$ have the same +first term, which is $S^0$: $\forall n\geqslant n_{1},S_0^n=S_0.$ + +Thus, after the $max(n_{0},n_{1})^{th}$ term, states of $E^n$ and $E$ are +identical and strategies $S^n$ and $S$ start with the same first term.\newline +Consequently, states of $G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are equal, +so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two points is strictly less than 1.\newline +\noindent We now prove that the distance between $\left( +G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to +0. Let $\varepsilon >0$. \medskip +\begin{itemize} +\item If $\varepsilon \geqslant 1$, we see that the distance +between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is +strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state). +\medskip +\item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant +\varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so +\begin{equation*} +\exists n_{2}\in \mathds{N},\forall n\geqslant +n_{2},d_{s}(S^n,S)<10^{-(k+2)}, +\end{equation*}% +thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. +\end{itemize} +\noindent As a consequence, the $k+1$ first entries of the strategies of $% +G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of +the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% +10^{-(k+1)}\leqslant \varepsilon $. + +In conclusion, +%%RAPH : ici j'ai rajouté une ligne +%%TOF : ici j'ai rajouté un commentaire +%%TOF : ici aussi +$ +\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} +,$ $\forall n\geqslant N_{0},$ +$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) +\leqslant \varepsilon . +$ +$G_{f}$ is consequently continuous. +\end{proof} + + +It is now possible to study the topological behavior of the general chaotic +iterations. We will prove that, + +\begin{theorem} +\label{t:chaos des general} + The general chaotic iterations defined on Equation~\ref{general CIs} satisfy +the Devaney's property of chaos. +\end{theorem} + +Let us firstly prove the following lemma. + +\begin{lemma}[Strong transitivity] +\label{strongTrans} + For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can +find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$. +\end{lemma} + +\begin{proof} + Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. +Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, +are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define +$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$. +We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates +that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of +the form $(S',E')$ where $E'=E$ and $S'$ starts with +$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties: +\begin{itemize} + \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$, + \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$. +\end{itemize} +Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, +where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties +claimed in the lemma. +\end{proof} + +We can now prove the Theorem~\ref{t:chaos des general}. + +\begin{proof}[Theorem~\ref{t:chaos des general}] +Firstly, strong transitivity implies transitivity. + +Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To +prove that $G_f$ is regular, it is sufficient to prove that +there exists a strategy $\tilde S$ such that the distance between +$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that +$(\tilde S,E)$ is a periodic point. + +Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the +configuration that we obtain from $(S,E)$ after $t_1$ iterations of +$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ +and $t_2\in\mathds{N}$ such +that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. + +Consider the strategy $\tilde S$ that alternates the first $t_1$ terms +of $S$ and the first $t_2$ terms of $S'$: +%%RAPH : j'ai coupé la ligne en 2 +$$\tilde +S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after +$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic +point. Since $\tilde S_t=S_t$ for $t 0$. +$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom +generator $G$ if + +\begin{flushleft} +$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$ +\end{flushleft} + +\begin{flushright} +$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$ +\end{flushright} + +\noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation +``$\in_R$'' indicates the process of selecting an element at random and uniformly over the +corresponding set. +\end{definition} + +Let us recall that the running time of a probabilistic algorithm is defined to be the +maximum of the expected number of steps needed to produce an output, maximized +over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}. +We are now able to define the notion of cryptographically secure PRNGs: + +\begin{definition} +A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator. +\end{definition} + + + + + + + +Suppose now that the PRNG of Eq.~\eqref{M-equation Oplus} of the main document will work during +$M=100$ time units, and that during this period, +an attacker can realize $10^{12}$ clock cycles. +We thus wonder whether, during the PRNG's +lifetime, the attacker can distinguish this +sequence from a truly random one, with a probability +greater than $\varepsilon = 0.2$. +We consider that $N$ has 900 bits. + +Predicting the next generated bit knowing all the +previously released ones by Eq.~\eqref{M-equation Oplus} of the main document is obviously equivalent to predicting the +next bit in the BBS generator, which +is cryptographically secure. More precisely, it +is $(T,\varepsilon)-$secure: no +$(T,\varepsilon)-$distinguishing attack can be +successfully realized on this PRNG, if~\cite{Fischlin} +\begin{equation} +T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) +\label{mesureConcrete} +\end{equation} +where $M$ is the length of the output ($M=100$ in +our example), and $L(N)$ is equal to +$$ +2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln~ 2)^\frac{1}{3} \times (ln(N~ln~ 2))^\frac{2}{3}\right) +$$ +is the number of clock cycles to factor a $N-$bit +integer. + + + + +A direct numerical application shows that this attacker +cannot achieve his $(10^{12},0.2)$ distinguishing +attack in that context. + + + + + \bibliographystyle{plain} \bibliography{mabase}