\begin{document}
\author{Jacques M. Bahi, Rapha\"{e}l Couturier, Christophe
-Guyeux, and Pierre-Cyrille Heam\thanks{Authors in alphabetic order}}
+Guyeux, and Pierre-Cyrille Héam\thanks{Authors in alphabetic order}}
\maketitle
Furthermore, we show that the proposed post-treatment preserves the
cryptographical security of the inputted PRNG, when this last has such a
property.
-Last, but not least, we propose a rewritting of the Blum-Goldwasser asymmetric
+Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
key encryption protocol by using the proposed method.
The remainder of this paper is organized as follows. In Section~\ref{section:related
\label{equation Oplus}
\end{equation}
where $\oplus$ is for the bitwise exclusive or between two integers.
-This rewritting can be understood as follows. The $n-$th term $S^n$ of the
+This rewriting can be understood as follows. The $n-$th term $S^n$ of the
sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents
the list of cells to update in the state $x^n$ of the system (represented
as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th
Algorithm~\ref{algo:gpu_kernel} presents a naive implementation of the proposed PRNG on
GPU. Due to the available memory in the GPU and the number of threads
-used simultenaously, the number of random numbers that a thread can generate
+used simultaneously, the number of random numbers that a thread can generate
inside a kernel is limited (\emph{i.e.}, the variable \texttt{n} in
algorithm~\ref{algo:gpu_kernel}). For instance, if $100,000$ threads are used and
if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)},
denoted by $uv$.
In a cryptographic context, a pseudorandom generator is a deterministic
algorithm $G$ transforming strings into strings and such that, for any
-seed $k$ of length $k$, $G(k)$ (the output of $G$ on the input $k$) has size
-$\ell_G(k)$ with $\ell_G(k)>k$.
+seed $s$ of length $m$, $G(s)$ (the output of $G$ on the input $s$) has size
+$\ell_G(m)$ with $\ell_G(m)>m$.
The notion of {\it secure} PRNGs can now be defined as follows.
\begin{definition}
A cryptographic PRNG $G$ is secure if for any probabilistic polynomial time
algorithm $D$, for any positive polynomial $p$, and for all sufficiently
-large $k$'s,
-$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)})=1]|< \frac{1}{p(k)},$$
+large $m$'s,
+$$| \mathrm{Pr}[D(G(U_m))=1]-Pr[D(U_{\ell_G(m)})=1]|< \frac{1}{p(m)},$$
where $U_r$ is the uniform distribution over $\{0,1\}^r$ and the
-probabilities are taken over $U_N$, $U_{\ell_G(N)}$ as well as over the
+probabilities are taken over $U_m$, $U_{\ell_G(m)}$ as well as over the
internal coin tosses of $D$.
\end{definition}
negligible probability. The interested reader is referred
to~\cite[chapter~3]{Goldreich} for more information. Note that it is
quite easily possible to change the function $\ell$ into any polynomial
-function $\ell^\prime$ satisfying $\ell^\prime(N)>N)$~\cite[Chapter 3.3]{Goldreich}.
+function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}.
The generation schema developed in (\ref{equation Oplus}) is based on a
pseudorandom generator. Let $H$ be a cryptographic PRNG. We may assume,
indistinguishable bits is lesser than or equals to
$log_2(log_2(M))$). In other words, to generate a 32-bits number, we need to use
8 times the BBS algorithm with possibly different combinations of $M$. This
-approach is not sufficient to be able to pass all the TestU01,
+approach is not sufficient to be able to pass all the tests of TestU01,
as small values of $M$ for the BBS lead to
small periods. So, in order to add randomness we have proceeded with
the followings modifications.
most} 3 bits, represented by \texttt{shift} in the algorithm, and we put
\emph{exactly} the \texttt{shift} last bits from a BBS into the \texttt{shift}
last bits of $t$. For this, an array named \texttt{array\_shift}, containing the
-correspondance between the shift and the number obtained with \texttt{shift} 1
+correspondence between the shift and the number obtained with \texttt{shift} 1
to make the \texttt{and} operation is used. For example, with a left shift of 0,
we make an and operation with 0, with a left shift of 3, we make an and
operation with 7 (represented by 111 in binary mode).
