Two-sources randomness extractors in finite
fields and in elliptic curves

Boudjou T. Hortense<fnref n="1" /> — Abdoul A. Ciss<fnref n="2" />— Djiby Sow<fnref n="3" />— Kolyang<fnref n="4" />

**ABSTRACT.** We propose two-sources randomness extractors over finite fields and on elliptic curves that can extract from two sources of information without consideration of other assumptions that the starting algorithmic assumptions with a competitive level of security. These functions have several applications. We propose here a description of a version of a Diffie-Hellman key exchange protocol and key extraction.

RÉSUMÉ. Nous proposons des extracteurs d'aléas 2-sources sur les corps finis et sur les courbes elliptiques capables d'extraire à partir de plusieurs sources d'informations sans considération d'autres hypothèses que les hypothèses algorithmiques de départ avec un niveau de sécurité compétitif. Ces fonctions possèdent plusieurs applications. Nous proposons ici une version du protocole d'échange de clé Diffie-Hellman incluant la phase d'extraction.

**KEYWORDS** : Cryptography, key exchange, random deterministic extractors, finite fields, elliptic curves.

MOTS-CLÉS : Cryptographie, échange de clé, extracteur d'aléa 2-sources, corps finis, courbes elliptiques.

<footnote n="1">¹High Institute of the Sahel, University of Maroua
46 Maroua, Cameroon</footnote>

<footnote n="2">²LTISI, Polytechnic School of Thies
10 A Thies, Senegal</footnote>

<footnote n="3">³LACGAA, University of Cheikh Anta Diop,
5005 Dakar, Senegal</footnote>

<footnote n="4">⁴Higher Normal School, University of Maroua
46 Maroua, Cameroon</footnote>
# 1. Introduction

The shared element after a Diffie-Hellman exchange is $g^{ab} \in G$, where G is a cyclic subgroup of a finite field. $g^{ab}$ is indistinguishable from any other element of G under the decisional Diffie-Hellman (DDH) assumption [4]. This hypothesis argues that, given two distribution $(g^a, g^b, g^{ab})$ and $(g^a, g^b, g^c)$ there is no efficient algorithm that can distinguish them. However, the encryption key should be indistinguishable from a random bit string having a uniform distribution. So we could not directly use $g^{ab}$ as an encryption key. It is therefore of adequate arrangements to ensure the indistinguishability of the key such as hash functions, pseudo-random functions or random extractors.

Deterministic random extractor have been introduced in complexity theory by Trevisan and Vadhan [21]. Most of the work on deterministic extractors using exponential sums for their security proof work with simple exponential sums [5, 11, 12, 13, 15]. Here, we introduce deterministic random extractors that extract a perfectly random bit string of an element derived from the combination of two separate sources.

More precisely, We propose a deterministic random extractor under the DDH assumption, which maps two multiplicative subgroups of a finite field $F_{p^n}$ to the set $\{0, 1\}^k$, permitting to extract the k-least significant bits of a random element in the product of the two subgroups. We use the double exponential sums to bound the collision probability and give a security proof of our extractor. The same work is performed over two subgroups $G_1$ and $G_2$ of points of an elliptic curve defined over a finite field $F_{p^n}$.

This work is organized as follows: In section 2, We introduce some definitions and results on both the measurement parameters of randomness and exponential sums. Section 3 gives summary of previous work. In section 4 we present and analyze the security of our randomness extractors. In section 5, we give an application of our results, that is a version of Diffie-Hellman key exchange protocol. Section 6 is our conclusion.

# 2. Preliminaries

This section recalls some definitions and results on the measurement of randomness and the sums of characters. We rely on them to establish the safety of our results. [19].

## 2.1. Measures of randomness

**Definition 2.1** *Collision probability.*

Let $\mathcal{X}$ be a finite set and $X$ an $\mathcal{X}$-valued random variable. The collision probability of $X$, denoted by $\text{Col}(X)$, is the probability $\text{Col}(X) = \text{Pr}[X = X'] = \sum_{x \in \mathcal{X}} \text{Pr}[X = x]^2$.

**Definition 2.2** *Statistical distance.*

Let $\mathcal{X}$ be a finite set. If $X$ and $Y$ are $\mathcal{X}$-valued random variables, then the statistical distance $SD(X, Y)$ between $X$ and $Y$ is defined as

$$SD(X, Y) = \frac{1}{2} \sum_{x \in \mathcal{X}} |\text{Pr}[X = x] - \text{Pr}[Y = x]|$$

Let $U_{\mathcal{X}}$ be a random variable uniformly distributed on $\mathcal{X}$ and $\delta \le 1$ a positive real number. Then a random variable $X$ on $\mathcal{X}$ is said to be $\delta$-uniform if $SD(X, U_{\mathcal{X}}) \le \delta$.
**Lemma 2.1** Relation between SD and Col(X).

Let X be a random variable over a finite set $\mathcal{X}$ of size $|\mathcal{X}|$ and $\Delta = SD(X, U_{\mathcal{X}})$ be the statistical distance between X and $U_{\mathcal{X}}$, where $U_{\mathcal{X}}$ is a uniformly distributed random variable over $\mathcal{X}$. Then,

$$Col(X) \geq \frac{1 + 4\Delta^2}{|\mathcal{X}|}$$

To establish this result, we use the following one:

**Lemma 2.2** Let $\mathcal{X}$ be a finite set and $(\alpha_x)_{x \in \mathcal{X}}$ a sequence of real numbers. Then

$$\frac{(\sum_{x \in \mathcal{X}} |\alpha_x|)^2}{|\mathcal{X}|} \leq \sum_{x \in \mathcal{X}} \alpha_x^2 \quad [1]$$

This inequality is a direct consequence of the Cauchy-Schwarz inequality below:

$$\sum_{x \in \mathcal{X}} |\alpha_x| = \sum_{x \in \mathcal{X}} |\alpha_x| \cdot 1 \leq \sqrt{\sum_{x \in \mathcal{X}} \alpha_x^2} \cdot \sqrt{\sum_{x \in \mathcal{X}} 1^2} \leq \sqrt{|\mathcal{X}|} \cdot \sqrt{\sum_{x \in \mathcal{X}} \alpha_x^2} \quad [2]$$

Hence the result. If X is a random variable with values in $\mathcal{X}$, laying $\alpha_x = Pr[X = x]$, since the sum of the probabilities is equal to 1 and as $Col(X) = \sum_{x \in \mathcal{X}} Pr[X = x]^2$ we get:

$$\frac{1}{|\mathcal{X}|} \leq Col(X). \quad [3]$$

Now we can establish the proof of Lemma 2.1. If $\Delta = 0$, then the result is immediate.

Assuming $\Delta \neq 0$. Let us define $q_x = |Pr[X = x] - \frac{1}{|\mathcal{X}|}|/2\Delta$, then $\sum_x q_x = 1$. According to Equation 1, we get:

$$\frac{1}{|\mathcal{X}|} \leq \sum_{x \in \mathcal{X}} q_x^2 = \frac{1}{4\Delta^2} \sum_{x \in \mathcal{X}} \left( Pr[X = x] - \frac{1}{|\mathcal{X}|} \right)^2 = \\ \frac{1}{4\Delta^2} \left( \sum_{x \in \mathcal{X}} Pr[X = x]^2 - \frac{1}{|\mathcal{X}|} \right) \leq \frac{1}{4\Delta^2} \left( col(X) - \frac{1}{|\mathcal{X}|} \right)$$

Hence the expected result.

**Definition 2.3** Deterministic $(\mathcal{Y}, \delta)$-extractor.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two finite sets. Let $Ext$ be a function $Ext: \mathcal{X} \to \mathcal{Y}$. We say that $Ext$ is a deterministic $(\mathcal{Y}, \delta)$-extractor for $\mathcal{X}$ if $Ext(U_{\mathcal{X}})$ is $\delta$-uniform on $\mathcal{Y}$. That is $SD(Ext(U_{\mathcal{X}}), U_{\mathcal{Y}}) \leq \delta$.

**Definition 2.4** Two-sources extractor.

Let $\mathcal{X}, \mathcal{Y}$ and $\mathcal{Z}$ be finite sets. The function $F: \mathcal{X} \times \mathcal{Y} \to \mathcal{Z}$ is a two-sources extractor if the distribution $F(X, Y)$ is $\delta$-close to the uniform distribution $U_{\mathcal{Z}} \in \mathcal{Z}$ for every uniformly distributed random variables $X \in \mathcal{X}$ and $Y \in \mathcal{Y}$.
## 2.2. Exponential sums

In this section, we introduce some definitions and results on exponential sums over finite fields and over elliptic curves (see [1, 18, 22]).

### 2.2.1. Exponential sums over finite fields

**Definition 2.5 Character.**

Let $G$ be an abelian group. A character of $G$ is a homomorphism from $G \to C^*$. A character is trivial if it is identically 1. We denote the trivial character by $\chi_0$ or $\psi_0$.

**Definition 2.6** Let $F_q$ be a given finite field. An additive character $\psi: F_q^+ \to C$ is a character $\psi$ with $F_q$ considered as an additive group. A multiplicative character $\chi: F_q^* \to C$ is a character with $F_q^* = F_q - \{0\}$ considered as a multiplicative group. We extend $\chi$ to $F_q$ by defining $\chi(0) = 1$ if $\chi$ is trivial, and $\chi(0) = 0$ otherwise. Note that the extended $\chi$ still preserves multiplication.

The main interests of exponential sums is that they allows to construct some characteristic functions and in some cases we know good bounds for them. The use of these characteristic functions can permit to evaluate the size of these sets. We focus on certain character sums, those involving the character $e_p$ define as it follows.

**Theorem 2.1** Multiplicative characters of $F_p$.

The multiplicative characters of $F_p$, where $p$ is a prime, are given by: $\forall x \in F_p$, $e_p(x) = e^{\frac{2i\pi x}{p}} \in C^*$.

**Theorem 2.2** Additive characters of $F_q$.

Suppose $q = p^r$ where $p$ is prime. The additive characters of $F_q$ are given by $\psi(x) = e_p(\text{Tr}(x))$ where $\text{Tr}(x) = x + x^p + \dots + x^{p^{n-1}}$ is the trace of $x$.

**Definition 2.7** Single character sums.

Let $p$ be a prime number, $G$ a multiplicative subgroup of $F_p^*$. For all $a \in F_{p^*}$, let introduce the following notation: $S(a, G) = \sum_{x \in G} e_p(ax)$.

**Lemma 2.3** Let $p$ be a prime number, $G$ a multiplicative subgroup of $F_p^*$.

1) if $a = 0$, $\sum_{x=0}^{p-1} e_p(ax) = p$

2) For all $a \in F_p^*$, $\sum_{x=0}^{p-1} e_p(ax) = 0$

3) For all $x_0 \in G$ and all $a \in F_p^*$, $S(ax_0, G) = S(a, G)$

See [24] pp 69

**Theorem 2.3** Polya-Vinogradov bound.

Let $p$ be a prime number, $G$ a multiplicative subgroup of $F_p^*$. For all $a \in F_{p^*}$:

$$ \left| \sum_{x \in G} e_p(ax) \right| \le \sqrt{p} $$
See [24] pp 70

**Theorem 2.4** Winterhof bound.

Let V be an additive subgroup of $F_{p^n}$ and let $\psi$ be an additive character of $F_{p^n}$. Then,

$$ \sum_{a \in F_{p^n}} \left| \sum_{x \in V} \psi(ax) \right| \le p^n $$

See [23]

**Definition 2.8** Bilinear character sums.

Let $p$ be a prime number, $G$ and $H$ be two multiplicative subgroups of $F_p^*$ . For all $a \in F_{p^*}$, let introduce the following notation: $S(a, (G, H)) = \sum_{x \in G} \sum_{y \in H} e_p(axy)$

**Lemma 2.4** Let $p$ be prime and, $G$ and $H$ two subsets of $F_p^*$. Then

$$ \max_{(n,p)=1} \left| \sum_{x \in G} \sum_{y \in H} (e_p(nxy)) \right| \le (p|G||H|)^{\frac{1}{2}} $$

See [6] (bound (1.4)), [22] pp 142.

**Lemma 2.5** For any subsets $G$, $H$ of $F_{p^n}$ and for any complex coefficients $\alpha_x, \beta_y$ with $|\alpha_x| \le 1$, $|\beta_y| \le 1$, the following bound holds, $|\sum_{x \in G} \sum_{y \in H} \alpha_x \beta_y \psi(xy)| \le (p^n|G||H|)^{\frac{1}{2}}$.

See [22] pp 142.

### 2.2.2. Exponential sums over points of elliptic curves

**Definition 2.9** Elliptic curves.

Let $\mathcal{E}$ be an elliptic curve over $F_p$ with $p \ge 3$ defined by an affine Weierstrass equation of the form $y^2 = x^3 + ax + b$ with coefficients $a, b \in F_p$. It is known that the set $\mathcal{E}(F_p)$ of $F_p$-rational points of $\mathcal{E}$, with the point at infinity $\mathcal{O}$ as the neutral element, forms an abelian group. The group law operation is denoted by $\oplus$. Every point $P \ne \mathcal{O} \in \mathcal{E}(F_p)$ is denote by $P = (x(P), y(P))$. Given an integer $n$ and a point $P \in \mathcal{E}(F_p)$, we write $nP$ for the sum of $n$ copies of $P$:

$$nP = P \oplus P \oplus \oplus P.$$

**Definition 2.10** Bilinear sums over additive character.

Given two subsets $P, Q$ of $\mathcal{E}(F_p)$, and arbitrary complex functions $\sigma, v$ supported on $P$ and $Q$ we consider the bilinear sums of additive characters.

$$V_{\sigma,v}(\psi, P, Q) = \sum_{P \in P} \sum_{Q \in Q} \sigma(P)v(Q)\psi(x(P \oplus Q)).$$
**Lemma 2.6** Let $\mathcal{E}$ be an elliptic curve defined over $F_q$ where $q = p^n$, with $n \ge 1$ and
let $\sum_{P \in \mathcal{P}} |\sigma(P)|^2 \le R$ and $\sum_{Q \in \mathcal{Q}} |v(Q)|^2 \le T$. Then, uniformly over all nontrivial additive
character $\psi$ of $F_q$, $|V_{\sigma,v}(\psi, \mathcal{P}, \mathcal{Q})| \ll \sqrt{qRT}$

Let $\mathcal{X}$ be the set of group characters on $\mathcal{E}(F_q)$. We collect the points $P$ and $Q$ with
a given sum $S = P \oplus Q$ and identify this condition via the character sum over $\mathcal{X}$. This
gives

$$
V_{\sigma,v}(\psi, \mathcal{P}, \mathcal{Q}) = \sum_{S \in \mathcal{E}(F_q)} \psi(x(S)) \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sigma(P)v(Q) \frac{1}{\#\mathcal{E}(F_q)} \sum_{X \in \mathcal{X}} X(P \oplus Q \ominus S).
$$

Therefore

$$
V_{\sigma,v}(\psi, \mathcal{P}, \mathcal{Q}) = \frac{1}{\#\mathcal{E}(F_q)} \sum_{X \in \mathcal{X}} \sum_{S \in \mathcal{E}(F_q)} \psi(x(S)) \overline{X(S)} \sum_{P \in \mathcal{P}} \sigma(P) X(P) \sum_{Q \in \mathcal{Q}} v(Q) X(Q).
$$

The sum over $S$ is $O(q^{1/2})$, so

$$
V_{\sigma,v}(\psi, \mathcal{P}, \mathcal{Q}) | \ll \frac{q^{1/2}}{\#\mathcal{E}(F_q)} \sum_{X \in \mathcal{X}} \left| \sum_{P \in \mathcal{P}} \sigma(P) X(P) \right| \left| \sum_{Q \in \mathcal{Q}} v(Q) X(Q) \right|.
$$

Then, with the Cauchy inequality we get

$$
\left( \sum_{X \in \mathcal{X}} \left| \sum_{P \in \mathcal{P}} \sigma(P) X(P) \right| \left| \sum_{Q \in \mathcal{Q}} v(Q) X(Q) \right| \right)^2 \le \sum_{X \in \mathcal{X}} \left| \sum_{P \in \mathcal{P}} \sigma(P) X(P) \right|^2 \sum_{X \in \mathcal{X}} \left| \sum_{Q \in \mathcal{Q}} v(Q) X(Q) \right|^2 \\
\le \#\mathcal{E}(F_q)^2 \text{RT, since}
$$

$$
\sum_{X \in \mathcal{X}} \left| \sum_{P \in \mathcal{P}} \sigma(P) X(P) \right|^2 = \sum_{P_1, P_2 \in \mathcal{P}} \sigma(P_1) \overline{\sigma(P_2)} \sum_{X \in \mathcal{X}} X(P_1 \ominus P_2) = \#\mathcal{E}(F_q) \sum_{P \in \mathcal{P}} |\sigma(P)|^2 \le \#\mathcal{E}(F_q)RT.
$$

Similarly

$$
\sum_{X \in \mathcal{X}} \left| \sum_{Q \in \mathcal{Q}} v(Q) X(Q) \right|^2 \le \#\mathcal{E}(F_q)T,
$$

and the desired result follows.

**3. Summary of previous work**

After a Diffie-Hellman key exchange protocol, the honest parties share an element
which is indistinguishable from a uniformly distributed element assuming the DDH as-
sumption. However they need a uniformly distributed bits string to perform cryptographic
operations as encryption. Thus one needs to extract entropy from the shared element.

Several solutions exist and can be implemented. There are essentially two methods of
esolution: the descent method and the character method.
**3.1. Descent method and probabilistic solutions**

The descent method is based on the random oracle model. The first way, and also the
most commonly used, to derive a bits string from a random element is to hash using hash
functions. The advantage of this solution is that its implementation is simple. However,
most often the solutions of this method are probabilistic. Indeed, in addition to the original
source, it is considered an additional input which is uniformly distributed, meaning that it
is viewed as a perfect random that, in practice, is difficult to achieve. The additional input
is called "seed" and such constructions are named "seeded extractor".

For such extractors with seed of length $O(\log n)$ bits, together with enumeration over all possible seed values, it is possible to simulate probabilistic algorithm with polynomial overhead, using only a high min-entropy source. On that point of view, the polynomial overhead can be too expensive. More, cryptographic applications prohibit such enumeration.

In 1998, Boneh et al. [5] showed that calculating the *k*-most significant bits of a secret is as difficult as calculating the common secret. The authors relied on the *Hidden Number Problem* (HNP). The goal of the HNP is to find a hidden number $s \in Z_p^*$, when given $p$ a prime, $g$ a generator of $Z_p^*$ and access to an oracle that on query $a$ returns the $k$ most significant bits of $s.g^a(p)$.

Hästad et al. [16] proposed random extractor based on the probabilistic *Leftover Hash Lemma*, capable of removing all of the entropy random source having sufficient min-entropy. This technique and its variants, however, require the use of hash functions and perfect random.

The drawback of these extractors is that they belong to the random oracle model so
the indistinguishability cannot be proven under the DDH assumption unless you add a
random oracle which in practice is considered to be limitations.

**3.2. Character method**

The character method is based on the standard model. Another approach, not re-
quiring the consideration of an additional perfect random is to use the deterministic ran-
domness extractors. They are also called "seedless extractors" and do not require any
computation. The only constraint is to consider quite large subgroups.

There have been many works constructing such seedless extractors using different
techniques.

In 2008, Fouque et al. [15] proposed a simple extractor capable of extracting the *k*-least significant bits or the *k*-most significant bits of a strong random element issued to the Diffie-Hellman exchange on a sufficient big subgroup of $Z_p$. They relied on exponential sums to bound the statistical distance between two variables.

In 2009, Chevalier et al. [11] also used exponential sums but bound the collision prob-
ability of bits extracted to prove the security of their extractor. Authors used the *Vino-
gradov inequality* to limit the incomplete character sums. They improved the results of
Fouque by providing an extractor capable of extracting up to two times more bits. They
also featured extractor on the group of points of an elliptic curve defined over a finite field.
However, their work was limited to the finite prime fields.

In 2011, Ciss et al. [12] extended the work of Chevalier over finite non-prime fields $F_{p^n}$ and elliptic curves over $F_{p^n}$ and more particularly on binary finite fields. They used the *Winterhof inequality* to limit the incomplete character sums.

All those previous works are based on the use of single character sums for their proof.
Sometimes a source cannot be able to allow deterministic extraction. So, when seedless
extractor from one source is impossible or when the unique source does not have enough min-entropy, it is natural to consider doing so from several independent sources.

Indeed, in the last few years, there where results on constructing extractors for a few independent sources. For example, in 2005, Bourgain [8] showed how to get an extractor for 2 sources relying on bounds coming from arithmetic combinatorics. In 2012, Kasher et al. [17] proposed a two-sources extractors in the quantum world, especially against entanglement.

# 4. Our Contribution

## 4.1. Randomness extractors in finite fields

We propose and prove the security of a simple deterministic randomness extractor for two subgroups $G_1$ and $G_2$ of $F_q^*$ where $q = p^n$, with $p$ prime and $n \ge 1$. The main theorem of this section states that the $k$-least significant bits of $x_1 \cdot x_2$, where $(x_1, x_2)$ is a random element in $(G_1, G_2)$, are close to a truly random element in $\{0, 1\}^k$. Our approach is from the model based on character sums.

### 4.1.1. Randomness extraction in $F_p$

Let $F_p$ be a finite prime field such that $|p| = m$. Let $G_1$ and $G_2$ be two multiplicative subgroups of $F_p^*$ of order $q_1$ and $q_2$ respectively, with $|q_1| = l_1$, $|q_2| = l_2$, the bit-length of $q_1$ and $q_2$ respectively. Let $U_{G_1}$ (resp. $U_{G_2}$) be a random variable uniformly distributed on $G_1$ (resp. $G_2$), and $k$ a positive integer less than $m$.

**Definition 4.1** Extractor $f_k$ on $F_p$.

The extractor $f_k$ is defined as the function

$$f_k: G_1 \times G_2 \to \{0, 1\}^k, (x_1, x_2) \mapsto lsb_k(x_1, x_2)$$

The following theorem shows that $f_k$ is a good randomness extractor.

**Theorem 4.1** Let $U_k$ be a random variable uniformly distributed on $\{0, 1\}^k$.

If $\Delta = SD(f_k(U_{G_1}, U_{G_2}), U_k)$ then,

$$2\Delta \le 2^{\frac{k+m+\log_2(m)-(l_1+l_2)}{2}}$$

We introduce the following notation $S(a, (G_1, G_2)) = \sum_{x_1 \in G_1} \sum_{x_2 \in G_2} e_p(ax_1x_2)$. Let us define $K = 2^k$, and $u_0 = \text{msb}_{m-k}(p-1)$. Let us construct the characteristic function, $1((x_1, x_2), (x'_1, x'_2), u) = \frac{1}{p} \sum_{a=0}^{p-1} e_p(a(x_1x_2 - x'_1x'_2 - Ku))$ using properties (1) and (2) of Lemma 2.3. Its equal to 1 if $x_1x_2 - x'_1x'_2 = Ku(p)$ and 0 otherwise. Therefore, we can evaluate $\text{Col}(f_k(U_{G_1}, U_{G_2}))$ where $U_{G_1}$ (resp. $U_{G_2}$) is uniformly distributed in $G_1$ (resp. in $G_2$):
$$
\mathrm{Col}(f_k(U_{G_1}, U_{G_2})) = \frac{1}{(q_1 q_2)^2} |\{(x_1, x_2), (x'_1, x'_2)\} \in (G_1, G_2)^2 \exists u \le u_0, x_1 x_2 - x'_1 x'_2 = Ku(p)\}| = \frac{1}{(q_1 q_2)^2 p} \sum_{(x_1, x_2) \in (G_1, G_2)} \sum_{(x'_1, x'_2) \in (G_1, G_2)} \sum_{u=0}^{u_0} \sum_{a=0}^{p-1} e_p(a(x_1 x_2 - x'_1 x'_2 - Ku)).
$$

Then, we manipulate the sums, separate some terms ($a = 0$) with the rest. That is, for $a = 0$,

$$
\mathrm{Col}(f_k(U_{G_1}, U_{G_2})) = \frac{1}{(q_1 q_2)^2 p} \sum_{a=0}^{p-1} \sum_{(x_1, x_2) \in (G_1, G_2)} \sum_{(x'_1, x'_2) \in (G_1, G_2)} \sum_{u=0}^{u_0} e_p(0) = \frac{u_0+1}{p} \quad [4]
$$

For $a \in F_p^*$,

$$
\begin{align*}
\mathrm{Col}(f_k(U_{G_1}, U_{G_2})) &= \frac{1}{(q_1 q_2)^2 p} \sum_{a=1}^{p-1} \sum_{(x_1, x_2) \in (G_1, G_2)} \sum_{(x'_1, x'_2) \in (G_1, G_2)} \sum_{u=0}^{u_0} e_p(a(x_1 x_2 - \\
&\quad x'_1 x'_2 - Ku)) \\
&= \frac{1}{(q_1 q_2)^2 p} \sum_{a=1}^{p-1} \sum_{(x_1, x_2) \in (G_1, G_2)} e_p(ax_1 x_2) \sum_{(x'_1, x'_2) \in (G_1, G_2)} e_p(-ax'_1 x'_2) \sum_{u=0}^{u_0} e_p(-aKu) \\
&= \frac{1}{(q_1 q_2)^2 p} \sum_{a=1}^{p-1} S(a, (G_1, G_2)) S(-a, (G_1, G_2)) \sum_{u=0}^{u_0} e_p(-aKu) \\
&= \frac{1}{(q_1 q_2)^2 p} \sum_{a=1}^{p-1} |S(a, (G_1, G_2))|^2 \sum_{u=0}^{u_0} e_p(-aKu).
\end{align*}
$$

We inject the result of equation (4) in the above result, the collision probability is there
equal to:

$$
\mathrm{Col}(f_k(U_{G_1}, U_{G_2})) = \frac{u_0 + 1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{a=1}^{p-1} |S(a, (G_1, G_2))|^2 \sum_{u=0}^{u_0} e_p(-aKu)
$$

According to the change of variable ($a' = Ka = 2^k a(p)$, with $\gcd(2, p) = 1$) and the fact that $[0, u_0]$ is an interval, giving a geometric sum on it, We have:
$$
\sum_{a=1}^{p-1} \sum_{u=0}^{u_0} e_p(-aKu) = \sum_{a=1}^{p-1} \sum_{u=0}^{u_0} \frac{1 - e_p(-a(u_0 + 1))}{1 - e_p(-a)} = \sum_{a=1}^{p-1} \frac{\sin(\frac{\pi a(u_0+1)}{p})}{\sin(\frac{\pi a}{p})} = 2 \sum_{a=1}^{\frac{p-1}{2}} \frac{\sin(\frac{\pi a(u_0+1)}{p})}{\sin(\frac{\pi a}{p})} \le 2 \sum_{a=1}^{\frac{p-1}{2}} \frac{1}{\sin(\frac{\pi a}{p})} \le 2 \sum_{a=1}^{\frac{p-1}{2}} \left|\frac{p}{a}\right| \le p \log_2(p)
$$

$$
\text{Therefore } \mathrm{Col}(f_k(U_{G_1}, U_{G_2})) \le \frac{u_0+1}{p} + \frac{1}{(q_1 q_2)^2 p} |S(a, (G_1, G_2))|^2 p \log_2(p) \le \frac{u_0+1}{p} + \frac{1}{(q_1 q_2)^2 p} (pq_1 q_2 p \log_2(p)) \le \frac{u_0+1}{p} + \frac{p \log_2(p)}{q_1 q_2}
$$
Using Lemma 2.1 which gives a relation between the statistical distance $\Delta$, of $f_k(U_{G_1}, U_{G_2})$ with the uniform distribution, and the collision probability: $Col(f_k(U_{G_1}, U_{G_2})) = \frac{1+4\Delta^2}{2^k}$, the previous upper bound combined with some manipulations gives:

$$2\Delta \le \sqrt{2^k \cdot Col(f_k(U_{G_1}, U_{G_2})) - 1} \le \sqrt{\frac{2^k}{p}} + \sqrt{\frac{2^k p(\log_2(p))}{q_1 q_2}} \le 2^{\frac{k+m+\log_2(m)-(l_1+l_2)}{2}}$$

### 4.1.2. Randomness extraction in $F_{p^n}$

Consider the finite field $F_{p^n}$, where $p$ is a $m$-bits prime and $n$ is a positive integer greater than 1. $F_{p^n}$ is a $n$-dimensional vector space over $F_p$. Let $\{\alpha_1, \alpha_2, \dots, \alpha_n\}$ be a basis of $F_{p^n}$ over $F_p$. That means, every element $x$ in $F_{p^n}$ can be represented in the form $x = x_1\alpha_1 + x_2\alpha_2 + \dots + x_n\alpha_n$, where $x_i \in F_p$. Let $G_1$ and $G_2$ be two multiplicative subgroups of $F_{p^n}^*$ of order $q_1$ and $q_2$ respectively, with $|q_1| = l_1$, $|q_2| = l_2$. Let $U_{G_1}$ (resp. $U_{G_2}$) be a random variable uniformly distributed on $G_1$ (resp. $G_2$), and $k$ be a positive integer less than $n$.

The theorem here establishes that the $k$-first coefficients in $F_p$ of a random element of $G_1 \times G_2$ are indistinguishable from a random group element of $F_p^k$.

**Definition 4.2** Extractor $F_k$ on $F_{p^n}$.

We define the function $F_k : G_1 \times G_2 \to F_p^k, (x, x') \mapsto (x_1x'_1, x_2x'_2, \dots, x_kx'_k)$.

The theorem below shows that $F_k$ is a good randomness extractor.

**Theorem 4.2** Let $U_k$ be a random variable uniformly distributed on $F_p^k$. In the terms of the above consideration, if $\Delta = SD(F_k(U_{G_1}, U_{G_2}), U_k)$ then,

$$\Delta \le 2^{\frac{km+nm-(l_1+l_2+2)}{2}}.$$

Let us introduce the notation

$$T(a, (G_1, G_2)) = \sum_{x \in G_1} \sum_{x' \in G_2} \psi(axx'). \text{ Let } (x, x'), (y, z) \in (G_1, G_2)^2.$$

Let us define the following sets:

$$R = \{x_{k+1}x'_{k+1}\alpha_{k+1} + x_{k+2}x'_{k+2}\alpha_{k+2} + x_nx'_n\alpha_n\}, \text{ a subgroup of } F_{p^n}$$

$$C = \{( (x, x'), (y, z)) \in (G_1, G_2)^2 / \exists r \in R, xx' - yz = r \}$$

$$|C| = \frac{1}{p^n} \sum_{x \in G_1, x' \in G_2} \sum_{y \in G_1, z \in G_2} \sum_{r \in R} \sum_{a \in F_{p^n}} \psi(a(xx' - yz - r)).$$

We can evaluate the collision probability:

$$\begin{aligned} \mathrm{Col}(F_k(U_{G_1}, U_{G_2})) &= \frac{|C|}{|G_1 \times G_2|^2} \\ &= \frac{1}{(q_1 q_2)^{2p^n}} \sum_{(x,x') \in (G_1, G_2)} \sum_{(y,z) \in (G_1, G_2)} \sum_{r \in R} \sum_{a \in F_{p^n}} \psi(a(xx' - yz - r)) \\ &= \frac{1}{(q_1 q_2)^{2p^n}} \sum_{a \in F_{p^n}} \sum_{(x,x') \in (G_1, G_2)} \psi(axx') \sum_{(y,z) \in (G_1, G_2)} \psi(-ayz) \sum_{r \in R} \psi(-ar). \end{aligned}$$

Then we manipulate the sums, separate some terms ($a = 0$) which gives $\frac{1}{p^k}$ with the rest. So for $a \in F_{p^n}^*$
$$
\mathrm{Col}(F_k(U_{G_1}, U_{G_2})) = \frac{1}{(q_1 q_2)^2 p^n} \sum_{a \in F_{p^n}^*} \sum_{(x,x') \in (G_1, G_2)} \psi(axx') \sum_{(y,z) \in (G_1, G_2)} \psi(-ayz) \sum_{r \in R} \psi(-ar)
$$

$$
\begin{align*}
\text{Then, for all } a \in F_{p^n}^*
& \qquad \operatorname{Col}(F_k(U_{G_1}, U_{G_2})) \\
&= \frac{1}{p^k} + \frac{1}{(q_1 q_2)^2 p^n} \sum_{a \in F_{p^n}^*} \sum_{(x,x') \in (G_1, G_2)} \psi(axx') \sum_{(y,z) \in (G_1, G_2)} \psi(-ayz) \sum_{r \in R} \psi(-ar) \\
&= \frac{1}{p^k} + \frac{1}{(q_1 q_2)^2 p^n} \sum_{a \in F_{p^n}^*} |T(a, (G_1, G_2))|^2 \sum_{r \in R} \psi(-ar) \\
&\le \frac{1}{p^k} + \frac{p^n (q_1 q_2) p^n}{(q_1 q_2)^2 p^n}, \quad \text{by Lemma 2.5 and Theorem 2.4} \\
&\le \frac{1}{p^k} + \frac{p^n}{(q_1 q_2)}.
\end{align*}
$$

Therefore, using Lemma 2.1 with some manipulations, we obtain the expected result:

$$
\Delta \le \sqrt{\frac{p^{n+k-2}}{q_1 q_2}} \le 2^{\frac{km+nm-(l_1+l_2+2)}{2}}.
$$

**Corollary 4.1** Let $G_1$ and $G_2$ be two multiplicative subgroups of $F_{2^n}^*$ of order $q_1$ (resp. $q_2$),
with $|q_1| = l_1$, $|q_2| = l_2$.
If $e > 1$ and $k > 1$ are two integers such as $k \le (l_1 + l_2) - 2e - n + 2$ then, $F_k$ is a
$((U_{G_1}, U_{G_2}), \frac{1}{2^e})$-deterministic extractor.

Proof of corollary 4.1

$$
\begin{gather*}
\text{If } k \le (l_1 + l_2) - 2e - n + 2, \\
\frac{k+n}{2} \le \frac{l_1+l_2+2}{2} - e
\end{gather*}
$$

$$
\sqrt{\frac{2^{\frac{k+n}{2}}}{\frac{p^{n+k}}{4q_1q_2}}} \le 2^{-e}
$$

**Corollary 4.2** Let $p > 2$ a prime such as $|p| = m$.

If $e > 1$ and $k > 1$ are two integers such as $k \le \frac{(l_1+l_2)-2e-mn+2}{m}$ then, $F_k$ is a
$((U_{G_1}, U_{G_2}), 2^{-e})$-deterministic extractor.

**4.2. Randomness extraction in elliptic curves**

Let $p$ be a prime greater than 5. Let $\mathcal{E}$ be an elliptic curve over the finite field $F_p$ and
let $\mathcal{P}, \mathcal{Q}$ be two subgroups of $\mathcal{E}(F_p)$. Let denote $|\mathcal{P}| = q_1$ and $|\mathcal{Q}| = q_2$. Let $U_{\mathcal{P}}$ and $U_{\mathcal{Q}}$
be two random variables uniformly distributed in $\mathcal{P}$ and $\mathcal{Q}$ respectively.

**4.2.1. Randomness extractor in E(F<sub>p</sub>)**

**Definition 4.3** We define the function $\text{extrac}_k : \mathcal{P} \times \mathcal{Q} \to \{0, 1\}^k$, $(\mathcal{P}, \mathcal{Q}) \mapsto \text{lsb}_k(x(\mathcal{P}) \cdot x(\mathcal{Q}))$.

The following theorem shows that $\text{extrac}_k$ is a good randomness extractor.
**Theorem 4.3** Let $U_k$ be the uniform distribution in $\{0, 1\}^k$. Then,

$$ \Delta(\text{extrac}_k(U_P, U_Q), U_k) \ll 2^{\frac{k+n+\log_2(n)-(l_1+l_2+2)}{2}} $$

Let us define $K = 2^k$, $u_0 = \text{msb}_{m-k}(p-1)$. Let us define the characteristic function $1((P, Q), (A, B), u) = \frac{1}{p} \sum_{\psi \in \Psi} \psi(x(P)x(Q) - x(A)x(B) - Ku)$ which is equal to 1 if $\psi = \psi_0$ and to 0, otherwise.

Let us compute the collision probability:

$$ \text{Col}(\text{extrac}_k(U_P, U_Q)) = \frac{1}{(q_1 q_2)^2 p} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{\psi \in \Psi} \sum_{u \le u_0} \psi(x(P)x(Q) - x(A)x(B) - Ku) $$

Then we manipulate the sums, separate some terms ($\psi = \psi_0$) with the rest.

So for ($\psi = \psi_0$),

$$ \begin{aligned} \text{Col}(\text{extrac}_k(U_P, U_Q)) &= \frac{1}{(q_1 q_2)^2 p} \sum_{\psi=\psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{u \le u_0} \psi_0(0) \\ &= \frac{1}{(q_1 q_2)^2 p} \sum_{\psi=\psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{u \le u_0} e_p(\text{Tr}(0)) \\ &= \frac{1}{(q_1 q_2)^2 p} \sum_{\psi=\psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{u \le u_0} 1 = \frac{u_0 + 1}{p} \end{aligned} $$

And for ($\psi \neq \psi_0$),

$$ \text{Col}(\text{extrac}_k(U_P, U_Q)) = \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{u \le u_0} \psi(x(P)x(Q) - x(A)x(B) - Ku) $$

Then for all $\psi$,

$$ \begin{aligned} \text{Col}(\text{extrac}_k(U_P, U_Q)) &= \frac{u_0 + 1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \sum_{u \le u_0} \psi(x(P)x(Q) - x(A)x(B) - Ku) \\ &= \frac{u_0 + 1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \psi(x(P)x(Q)) \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \psi(-x(A)x(B)) \sum_{u \le u_0} \psi(-Ku) \\ &= \frac{u_0 + 1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} \left| \sum_{P \in \mathcal{P}} \sum_{Q \in \mathcal{Q}} \psi(x(P)x(Q)) \right| \sum_{A \in \mathcal{P}} \sum_{B \in \mathcal{Q}} \psi(-x(A)x(B)) \left| \sum_{u \le u_0} \psi(-Ku) \right| \\ &= \frac{u_0 + 1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} \left| \mathcal{V}(\psi, \mathcal{P}, \mathcal{Q}) \right|^2 \sum_{u \le u_0} \psi(-Ku) \\ &\le \frac{1}{p} + \frac{1}{(q_1 q_2)^2 p} \sum_{\psi \neq \psi_0} q_1 q_2 p \sum_{u \le u_0} \psi(-Ku), \quad \text{by Lemma 2.6} \\ &\le \frac{1}{p} + \frac{1}{(q_1 q_2)^2 p} pq_1 q_2 p \log_2(p), \quad \text{since it is shown that } \sum_{\psi \neq \psi_0} \sum_{u \le u_0} \psi(-Ku) \le p \log_2(p) \\ &\le \frac{1}{p} + \frac{1}{(q_1 q_2)^2 p} p \log_2(p). \end{aligned} $$

Therefore, using Lemma 2.1 with some manipulations, we obtain the expected result:

$$ \Delta(\text{extrac}_k(U_P, U_Q), U_k) \ll \sqrt{\frac{2^{k-2} p \log_2(p)}{q_1 q_2}} = 2^{\frac{k+n+\log_2(n)-(l_1+l_2+2)}{2}} $$
4.2.2. Randomness extractor in $\mathcal{E}(F_{p^n})$

**Definition 4.4** Let us define the function Extrac<sub>k</sub> : $\mathcal{P} \times \mathcal{Q} \to F_p^k$, (P, Q) $\mapsto$ (t<sub>1</sub>, t<sub>2</sub>, ..., t<sub>k</sub>),
where $x(P) \cdot x(Q) = t_1\alpha_1 + t_2\alpha_2 + \dots + t_n\alpha_n$.

The theorem below shows that Extrac<sub>k</sub> is a good randomness extractor over $\mathcal{E}(F_{p^n})$.

**Theorem 4.4** Let $U_k$ be the uniform distribution in $F_p^k$. Then,

$$
\Delta(\text{Extrac}_k(U_{\mathcal{P}}, U_{\mathcal{Q}}), U_k) \ll 2^{\frac{km+nm-(l_1+l_2+2)}{2}}.
$$

Using Lemma 2.6 and Theorem 2.4, the sketch of the proof is the same as those of
Theorem 4.2

**4.3. Specification: Abstract Data Type**

Sort ArrayofBits;

Functions

initialize: → ArrayofBits;

createKey: Integer → ArrayofBits;

getKeyLength: ArrayofBits → Integer;

testParameterEntropy ArrayofBits, Integer → Boolean;

lsb-k: ArrayofBits, Integer → ArrayofBits;

Axioms

A1 initialize=[]

A2 createKey(r) = createKeyConvertToBits(r))

A3 getKeyLength(initialize) = 0

A4 getKeyLength createKey(r)
= # getKeyLength convertToBits(r))

A5 testParameterEntropy(initialize, k)=False

A6 testParameterEntropy createKey(r), k = True,
if getKeyLength createKey(r)) ≥ k

A7 lsb-k(initialize, k) = Error

A8 lsb-k createKey(r), k
= lsb-k createKey ConvertToBits(r), k

5. Applications

The ideas behind a randomness extractors is the following one: suppose one got a ran-
dom variable X with some entropy but which is not uniform. For many areas of computer
science, typically for many cryptographic applications, it is required an uniformly random
variable for example to use as a secret key. Therefore, one needs to somehow extract the
randomness from X to get a uniformly distributed output.

**Extractors for multiple sources.** Sometimes, extraction from one source is impossi-
ble.
There are some solutions in the probabilistic method namely "seeded extractors". These are extractors that receive one source (with min-entropy at least $k$, for some parameter $k$) and an independent short input $Y$, called "seed", that is uniformly distributed. Since the assumption over $Y$ is strong, that is having perfectly random bits is difficult in practice, an alternative is the use of two or more sources. In this setup, a more natural setting is to consider $Y$ with the same length and min-entropy threshold as $X$.

Moreover, cryptographic protocols require to work on sufficient large sub-groups. The high level of considering multiple sources is to show that if the given $l$-sources with min-entropy $\delta n$, $\delta > 0$ are over a finite field $F_q$ that has no large sub-fields (which holds in the case that $F_q$ is a prime field), then the cumulative distribution will have more min-entropy.

**Generating keys for cryptographic protocols** The interest of studying randomness extractors has several cryptographic applications. Specially, it can apply for the key extraction phase of a key exchange protocol, but also for identity encryption schemes.

The security of cryptographic protocols depends on the ability of honest parties to generate uniformly distributed and private random key. More generally, honest parties work in a non-secure environment set up by an adversary trying to steal the shared secret.

Thus multi-source extractors enable an honest party to sample a string that is (close to) uniform, given multiple sources, the main requirement from each source being to contain some min-entropy.

For example, if one wants to extract a 256-bits, for $n = 1024$, $e = 80$, one needs a group of size greater than $2^{756}$ with Chevalier's et al. extractor [11]. With our extractor $f_k$ define in subsection 4.1.1, considering two groups of sizes $2^{724}$ one can extracts 256-bits. In this case, $f_k$ is an ($(U_{G_1}, U_{G_2}), 2^{-80}$)—deterministic extractor.

**Example: key exchange protocol and key extraction from two-sources**

1) For the first session,

- Alice and Bob choose a public elliptic curve group of points $G = \langle P \rangle; \text{Extrac}_k : G \times G \mapsto \{0, 1\}^k$

- Alice and Bob perform the DH ratchet as follows:

i=1;

Alice chooses $a_i \in Z_q^*$, sends $a_i P$ to Bob;

Bob chooses $b_i \in Z_q^*$, sends $b_i P$ to Alice;

Alice computes $a_i b_i P$ and Bob computes $b_i a_i P$;

They share and keep secret $a_i b_i P$.

2) They can use a one-source randomness extractor for this session.

For the next session,

- Alice and Bob perform a new DH ratchet;

i=i+1;

Then both share a new $a_i b_i P$;

They can now use a two-source randomness extractor and perform the key extraction phase as follows:

Key extraction: $k = \text{Extrac}_k(a_i b_i P, a_{i-1} b_{i-1} P) = lsb_k(x(a_i b_i P) + x(a_{i-1} b_{i-1} P))$.
## 6. Conclusion

The problem is: how to ensure the indistinguishability of a key session which is a string of bits issue to a shared element after a Diffie-Hellman exchange protocol. Even if the commonly use solution is one of a hash function, the solutions in the standard model are more reliable. We have constructed some two-sources deterministic randomness extractors which perform extraction of random bits string close to the uniform distribution over more than one source of information. These extractors can be used in any finite field or any elliptic curve based protocols. We have also proposed some applications, for example a version of Diffie-Hellman key exchange protocol with key extraction step.

As future work, we intend to generalize the proposed extractors to *n*-sources, find analogous results for hyperelliptic curves and propose cryptographically secure pseudo-random number generators based on these extractors. Most identity-based protocols calculates the current key of a user from its identity view as a point of an (hyper)elliptic curve. This is, an implementation of a platform of session keys generation using our extractors, and of calculation of a point of a curve using new encoding functions is underway. The goal here is to provide a practical tool for key generation phases of these encryption primitive.

## 7. References

[1] O. AHMADI, I. E. SHPARLINSKI, “Exponential Sums over Points of Elliptic Curves”, arXiv preprint arXiv:1302.4210, 2013.

[2] alog A. BALOG, K. A. BROUGHAN, I. E. SHPARLINSKI, “Sum-Products Estimates with Several Sets and Applications”,

[3] M. BELLARE, P. ROGAWAY, “Random oracles are practical: A Paradigm for designing efficient protocols”, In V. Ashby, editor, *ACM CCS 93*, 62-73, 1993.

[4] D. BONEH, “The decision Diffie-Hellman problem”, In *Third Algorithmic Number Theory Symposium (ANTS)*, vol. 1423, of LNCS. Springer, 1998.

[5] D. BONEH, R. VENKATESAN, “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes”, In *N. Koblitz, editor, CRYPTO'96*, vol. 1109, of LNCS. Springer, 1996.

[6] J. BOURGAIN, M. Z. GARAEV, “On a variant of sum-product estimate and explicit exponential sum bounds in prime field”, *Math.Proc.Camb.Phil.Soc*, 146, 2008.

[7] J. BOURGAIN, S. V. KONYAGIN, “Estimates for the Number of Sums and Products and for Exponential Sums Over Subgroups in Fields of Prime Order”, 2003.

[8] J. BOURGAIN, “More on the sum-product phenomenon in prime fields and its applications”, *International Journal of Number Theory*, 2005.

[9] R. CARNETI, J. FRIEDLANDER, S. KOYAGIN, M. LARSEN, D. LIEMAN, I. SHPARLINSKI, “On the Statistical Properties of Diffie-Hellman Distributions”, *Israel Journal of Mathematics*, vol. 120, 2000.

[10] R. CARNETI, J. FRIEDLANDER, I. SHPARLINSKI, “On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples”, *Journal of the London Mathematical Society*, vol. 59, num. 2, 1999.

[11] C. CHEVALIER, P. FOUQUE, D. POINTCHEVAL, S. ZIMMER, “Optimal Randomness Extraction from a Diffie-Hellman Element, Advances in Cryptology”, *Eurocrypt'09*, vol. 5479, of LNCS, 572-589, Springer-Verlag, 2009.
[12] A. A. CISS, D. SOW, "On Randomness Extraction in Elliptic Curves", In *A. Nitaj and D. Pointcheval, editors.* *Africacrypt 2011*, vol. 6737, of LNCS, 290-297, Springer-Verlag, 2011.

[13] W. DIFFIE, M. HELLMAN, "New Directions in Cryptography", *IEEE Transactions On Information Theory*, vol. 22, num. 6, 644-654, 1976.

[14] R. R. FARASHAHI, I. E. SHPARLINSKI, J. F. VOLOCH, "On hashing into elliptic curves", *J.Math.Cryptology*, vol. 3, 353-360, 2010.

[15] P. A. FOUQUE, D. POINTCHEVAL, J. STERN, S. ZIMMER, "Hardness of distinguishing the MSB or the LSB of secret keys in Diffie-Hellman schemes", In *M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors*, *ICALP 2006*, vol. 4052, of LNCS, 240-251, ACM, 2008.

[16] J. HÄSTAD, R. IMPAGLIAZZO, L. LEVIN, M. LUBY, "A pseudorandom generator from any one-way function", *SIAM Journal on Computing*, vol. 28, num. 4, 240-251, 1999.

[17] R. KASHER, J. KEMPE, "Two-source Extractors Secure Against Quantum Adversaries", *Theory Of Computing*, vol. 8, num. 1, 461-486, 2012.

[18] S. V. KOYAGIN, I. SHPARLINSKI, "Character Sums With Exponential Functions and Their Applications", *Cambridge University Press, Cambridge*, 1999.

[19] V. SHOUP, "A Computational Introduction to Number Theory and Algebra", *Cambridge University Press, Cambridge*, 2005.

[20] L. TREVISAN, "Extractors and pseudorandom generators", *J. ACM*, vol. 48, num. 4, 860-879, 2001.

[21] L. TREVISAN, S. VADHAN, "Extracting Randomness from Samplable Distributions", *EEE Symposium on Foundations of Computer Science*, 2003.

[22] I. M. VINOGRADOV, "An Introduction to the Theory of Numbers", *Pergamon Press*, 1955.

[23] A. WINTERHOF, "Incomplete Additive Character Sums and Applications", In *D. Jungnickel and H. Niederreiter, editors.* *Finite Fields and Applications*, Springer-Velag, 2001.

[24] S. ZIMMER, "Mécanismes cryptographiques pour la génération de cléfs et l'authentification",