Boudjou T Hortense

Abdoul A Ciss

-Djiby Sow

- Kolyang

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

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

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.

Introduction

The shared element after a Diffie-Hellman exchange is g ab ∈ G, where G is a cyclic subgroup of a finite field. g ab is indistinguishable from any other element of G under the decisionnal Diffie-Hellman (DDH) assumption [START_REF] Boneh | The decision Diffie-Hellman problem[END_REF]. 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 [START_REF] Trevisan | Extracting Randomness from Samplable Distributions[END_REF]. Most of the work on deterministic extractors using exponential sums for their security proof work with simple exponential sums [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Helman and related schemes[END_REF][START_REF] Chevalier | Optimal Randomness Extraction from a Diffie-Hellman Element, Advances in Cryptology[END_REF][START_REF] Ciss | On Randomness Extraction in Elliptic Curves[END_REF]13,[START_REF] Fouque | Hardness of distinguishing the MSB or the LSB of secret keys in Diffie-Hellman schemes[END_REF]. 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 asumption, 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.

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. [START_REF] Shoup | A Computational Introduction to Number Theory and Algebra[END_REF]. Let X be a finite set and X an X -valued random variable. The collision probability of X, denoted by Col(X), is the probability Col

Measures of randomness

(X) = P r[X = X ] = x∈X P r[X = x] 2 . Definition 2.2 Statistical distance.
Let X be a finite set. If X and Y are X -valued random variables, then the statistical distance SD(X, Y ) between X and Y is defined as

SD(X, Y ) = 1 2 x∈X |P r[X = x] -P r[Y = x]| .
Let U X be a random variable uniformly distributed on X and δ ≤ 1 a positive real number.

Then a random variable X on X is said to be δ -unif orm if SD(X, U X ) ≤ δ.

Lemma 2.1 Relation between SD and Col(X). Let X be a random variable over a finite set X of size |X | and ∆ = SD(X, U X ) be the statistical distance between X and U X , where U X is a uniformly distributed random variable over X . Then,

Col(X) ≥ 1 + 4∆ 2 |X |
To establish this result, we use the following one:

Lemma 2.2 Let X be a finite set and (α x ) x∈X a sequence of real numbers. Then

( x∈X |α x |) 2 |X | ≤ x∈X α 2 x [1]
This inequality is a direct consequence of the Cauchy-Schwarz inequality below:

x∈X |α x | = x∈X |α x |.1 ≤ x∈X α 2 x . x∈X 1 2 ≤ |X |. x∈X α 2 x . [2]
Hence the result. If X is a random variable with values in X , laying

α x = P r[X = x],
since the sum of the probabilities is equal to 1 and as Col(X) = x∈X P r[X = x] 2 we get:

1 |X | ≤ Col(X). [3]
Now we can establish the proof of Lemma 2.1. If ∆ = 0, then the result is immediate.

Assuming ∆ = 0. Let us define q x = |P r[X = x] -1 |X | |/2∆, then x q x = 1.
According to Equation 1, we get:

1 |X | ≤ x∈X q 2 x = 1 4∆ 2 x∈X P r[X = x] - 1 |X | 2 = 1 4∆ 2 x∈X P r[X = x] 2 - 1 |X | ≤ 1 4∆ 2 col(X) - 1 |X |
Hence the expected result.

Definition 2.3 Deterministic (Y, δ)-extractor.
Let X and Y be two finite sets. Let Ext be a function Ext :

X → Y. We say that Ext is a deterministic (Y, δ)-extractor for X if Ext(U X ) is δ-uniform on Y. That is SD(Ext(U X ), U Y ) ≤ δ. Definition 2.4 Two-sources extractor.
Let X , Y and Z be finite sets. The function

F : X × Y → Z is a two-sources extractor if the distribution F (X, Y ) is δ-close to the uniform distribution U Z ∈ Z for every uniformly distributed random variables X ∈ X and Y ∈ Y.

Exponential sums

In this section, we introduce some definitions and results on exponential sums over finite fields and over elliptic curves (see [START_REF] Ahmadi | Exponential Sums over Points of Elliptic Curvese[END_REF][START_REF] Koyagin | Character Sums With Exponential Functions and Their Applications[END_REF][START_REF] Vinogradov | An Introduction to the Theory of Numbers[END_REF]).

Exponential sums over finite fields

Definition 2.5 Character.

Let G be an abelian group. A character of G is a homomorphism from G → C * . A character is trivial if it is identically 1. We denote the trivial character by X 0 or ψ 0 . Definition 2.6 Let F q be a given finite field. An additive character ψ : F + q → C is a character ψ with F q considered as an additive group. A multiplicative character X : F * q → C is a character with F * q = F q -{0} considered as a multiplicative group. We extend X to F q by defining X (0) = 1 if X is trivial, and X (0) = 0 otherwise. Note that the extended X 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: ∀x ∈ F p , e p (x) = e 2iπx p ∈ 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 ψ(x) = e p (T r(x)) where T r(x) = x + x p + ... + x p n-1 is the trace of x. .

See [START_REF] Bourgain | On a variant of sum-product estimate and explicit exponential sum bounds in prime field[END_REF] (bound (1.4)), [START_REF] Vinogradov | An Introduction to the Theory of Numbers[END_REF] pp 142.

Lemma 2.5 For any subsets G, H of F * p n and for any complex coefficients α x , β y with

|α x | ≤ 1, |β y | ≤ 1, the following bound holds, | x∈G y∈H α x β y ψ(xy)| ≤ (p n |G||H|) 1 2 .
See [START_REF] Vinogradov | An Introduction to the Theory of Numbers[END_REF] pp 142.

Exponential sums over points of elliptic curves

Definition 2.9 Elliptic curves.

Let E be an elliptic curve over F p with p ≥ 3 defined by an affine Weieirstrass equation of the form y 2 = x 3 + ax + b with coefficients a, b ∈ F p . It is known that the set E(F p ) of F p -rational points of E, with the point at infinity O as the neutral element, forms an abelian group. The group law operation is denoted by ⊕. Every point P = O ∈ E(F p ) is denote by P = (x(P), y(P)). Given an integer n and a point P ∈ E(F p ), we write nP for the sum of n copies of P: nP = P ⊕ P ⊕ ⊕P.

Definition 2.10 Bilinear sums over additive character. Given two subsets P, Q of E(F p ), and arbitrary complex functions σ, v supported on P and Q we consider the bilinear sums of additive characters.

V σ,v (ψ, P, Q) = P∈P Q∈Q σ(P)v(Q)ψ(x(P ⊕ Q)).
Lemma 2.6 Let E be an elliptic curve defined over F q where q = p n , with n ≥ 1 and let

P∈P |σ(P)| 2 ≤ R and Q∈Q |v(Q)| 2 ≤ T. Then, uniformly over all nontrivial additive character ψ of F q , |V σ,v (ψ, P, Q)| qRT
Let X be the set of group characters on E(F q ). We collect the points P and Q with a given sum S = P ⊕ Q and identify this condition via the character sum over X . This gives

V σ,v (ψ, P, Q) = S∈E(Fq) ψ(x(S)) P∈P Q∈Q σ(P)v(Q) 1 #E(F q ) X∈X X(P ⊕ Q S). Therefore V σ,v (ψ, P, Q) = 1 #E(F q ) X∈X S∈E(Fq) ψ(x(S))X(S) P∈P σ(P)X(P) Q∈Q v(Q)X(Q).
The sum over S is O(q 1/2 ), so

V σ,v (ψ, P, Q)| q 1/2 #E(F q ) X∈X P∈P σ(P)X(P) Q∈Q v(Q)X(Q) .
Then, with the Cauchy inequality we get

  X∈X P∈P σ(P)X(P) Q∈Q v(Q)X(Q)   2 ≤ X∈X P∈P σ(P)X(P) 2 X∈X Q∈Q v(Q)X(Q) 2 ≤ #E(F q ) 2 RT, since X∈X P∈P σ(P)X(P) 2 = P1,P2∈P σ(P 1 )σ(P 2 ) X∈X X(P 1 P 2 ) = #E(F q ) P∈P |σ(P)| 2 ≤ #E(F q )R. Similarly X∈X Q∈Q v(Q)X(Q) 2 ≤ #E(F q )T,
and the desired result follows.

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 assumption. 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.

Descent method and probabilistic solutions

The descent method is based on the 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. [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Helman and related schemes[END_REF] 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 ∈ 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. [START_REF] Hästad | A pseudorandom generator from any one-way function[END_REF] proposed random extractor based on the probabilistic Leftover Hash Lemma, capable of removing all of the entropy random source having sufficient minentropy. 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.

Character method

The character method is based on the standard model. Another approach, not requiring the consideration of an additional perfect random is to use the deterministic randomness 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. [START_REF] Fouque | Hardness of distinguishing the MSB or the LSB of secret keys in Diffie-Hellman schemes[END_REF] proposed a simple extractor capable of extracting the kleast 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. [START_REF] Chevalier | Optimal Randomness Extraction from a Diffie-Hellman Element, Advances in Cryptology[END_REF] also used exponential sums but bound the collision probability of bits extracted to prove the security of their extractor. Authors used the Vinogradov 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. [START_REF] Ciss | On Randomness Extraction in Elliptic Curves[END_REF] 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 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 [START_REF] Bourgain | More on the sum-product phenomenon in prime fields and its applications[END_REF] showed how to get an extractor for 2 sources relying on bounds coming from arithmetic combinatorics. In 2012, Kasher et al. [START_REF] Kasher | Two-source Extractors Secure Against Quantum Adversaries[END_REF] proposed a two-sources extractors in the quantum world, especially against entanglement.

Our Contribution

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 ≥ 1. The main theorem of this section states that the k-least significant bits of

x 1 • 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.

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 G1 (resp. U G2 ) 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 × G 2 -→ {0, 1} k , (x 1 , x 2 ) -→ 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 ∆ = SD(f k (U G1 , U G2 ), U k ) then, 2∆ ≤ 2 k+m+log 2 (m)-(l 1 +l 2 ) 2
We introduce the following notation S(a, (G 1 , G 2 )) = x1∈G1 x2∈G2 e p (ax 1 x 2 ). Let us define K = 2 k , and u 0 = msb m-k (p -1). Let us construct the characteristic function, 1((

x 1 , x 2 ), (x 1 , x 2 ), u) = 1 p p-1 a=0 e p (a(x 1 x 2 -x 1 x 2 -Ku)) using properties (1)
and (2) of Lemma 2.3. Its equal to 1 if x 1 x 2 -x 1 x 2 = Ku(p) and 0 otherwise. Therefore, we can evaluate

Col(f k (U G1 , U G2 )) where U G1 (resp. U G2 ) is uniformly distributed in G 1 (resp. in G 2 ): Col(f k (U G1 , U G2 )) = 1 (q 1 q 2 ) 2 |{((x 1 , x 2 (x 1 , x 2 )) ∈ (G 1 , G 2 ) 2 ∃u ≤ u 0 , x 1 x 2 - x 1 x 2 = Ku(p)}| = 1 (q 1 q 2 ) 2 p (x1,x2)∈(G1,G2) (x 1 ,x 2 )∈(G1,G2) u0 u=0 p-1 a=0 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,

Col(f k (U G1 , U G2 )) = 1 (q 1 q 2 ) 2 p p-1 a=0 (x1,x2)∈(G1,G2) (x 1 ,x 2 )∈(G1,G2) u0 u=0 e p (0) = u 0 + 1 p [4]
For a ∈ F * p ,

Col(f k (U G1 , U G2 )) = 1 (q 1 q 2 ) 2 p p-1 a=1 (x1,x2)∈(G1,G2) (x 1 ,x 2 )∈(G1,G2) u0 u=0 e p (a(x 1 x 2 - x 1 x 2 -Ku)) = 1 (q 1 q 2 ) 2 p p-1 a=1 (x1,x2)∈(G1,G2) e p (ax 1 x 2 ) (x 1 x 2 )∈(G1,G2) e p (-ax 1 x 2 ) u0 u=0 e p (-aKu) = 1 (q 1 q 2 ) 2 p p-1 a=1 S(a, (G 1 , G 2 ))S(-a, (G 1 , G 2 )) u0 u=0 e p (-aKu) = 1 (q 1 q 2 ) 2 p p-1 a=1 |S(a, (G 1 , G 2 ))| 2 u0 u=0 e p (-aKu).
We inject the result of equation (4) in the above result, the collision probability is there equal to:

Col(f k (U G1 , U G2 )) = u 0 + 1 p + 1 (q 1 q 2 ) 2 p p-1 a=1 |S(a, (G 1 , G 2 ))| 2
Therefore Col(f k (U G1 , U G2 )) ≤ u 0 + 1 p + 1 (q 1 q 2 ) 2 p |S(a, (G 1 , G 2 ))| 2 p log 2 (p) ≤ u 0 + 1 p + 1 (q 1 q 2 ) 2 p (pq 1 q 2 p log 2 (p)) ≤ u 0 + 1 p + p log 2 (p) q 1 q 2
Two-source randomnes extractors in finite fields and in elliptic curves 57

Using Lemma 2.1 which gives a relation between the statistical distance ∆, of f k (U G1 U G2 ) with the uniform distribution, and the collision probability:

Col(f k (U G1 , U G2 )) = 1+4∆ 2 2 k
, the previous upper bound combined with some manipulations gives:

2∆ ≤ 2 k .Col(f k (U G1 , U G2 )) -1 ≤ 2 k p + 2 k p(log 2 (p)) q 1 q 2 ≤ 2 k+m+log 2 (m)-(l 1 +l 2 ) 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 {α 1 , α 2 , , α 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 α 1 + x 2 α 2 + . . . + x n α n , where x i ∈ 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 G1 (resp. U G2 ) 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 × G 2 are indistinguishable from a random group element of F k p .

Definition 4.2 Extractor F k on F p n . We define the function

F k : G 1 × G 2 -→ F k p , (x, x ) -→ (x 1 x 1 , x 2 x 2 , , x k x 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 k p . In the terms of the above consideration, if

∆ = SD(F k (U G1 , U G2 ), U k ) then, ∆ ≤ 2 km+nm-(l 1 +l 2 +2) 2
.

Let us introduce the notation

T (a, (G 1 , G 2 )) = x∈G1 x ∈G2 ψ(axx ). Let (x, x ), (y, z) ∈ (G 1 , G 2 ) 2 .
Let us define the following sets:

R = {x k+1 x k+1 α k+1 + x k+2 x k+2 α k+2 + x n x n α n } , a subgroup of F p n C = {((x, x ), (y, z)) ∈ (G 1 , G 2 ) 2 /∃r ∈ R, xx -yz = r} |C| = 1 p n x∈G1,x ∈G2 y∈G1,z∈G2 r∈R a∈F p n ψ(a(xx -yz -r)).
We can evaluate the collision probability:

Col(F k (U G1 , U G2 )) = |C| |G 1 xG 2 | 2 = 1 (q 1 q 2 ) 2 p n (x,x )∈(G1,G2) (y,z)∈(G1,G2) r∈R a∈F p n ψ(a(xx -yz -r)) = 1 (q 1 q 2 ) 2 p n a∈F p n (x,x )∈(G1,G2) ψ(axx ) (y,z)∈(G1,G2) ψ(-ayz) r∈R ψ(-ar).
Then we manipulate the sums, separate some terms (a = 0) which gives 1 p k with the rest. So for a ∈ F p

Col(F k (U G1 , U G2 )) = 1 (q 1 q 2 ) 2 p n a∈F * p n (x,x ψ(axx ) (y,z)∈(G1,G2) ψ(-ayz) r∈R ψ(-ar) Then, for all a ∈ F p n Col(F k (U G1 , U G2 )) = 1 p k + 1 (q 1 q 2 ) 2 p n a∈F * p n (x,x )∈(G1,G2) ψ(axx ) (y,z)∈(G1,G2) ψ(-ayz) r∈R ψ(-ar) = 1 p k + 1 (q 1 q 2 ) 2 p n a∈F * p n |T (a, (G 1 , G 2 ))| 2 r∈R ψ(-ar) ≤ 1 p k +
p n (q 1 q 2 )p n (q 1 q 2 ) 2 p n , by Lemma 2.5 and Theorem 2.4

≤ 1 p k + p n (q 1 q 2 )
.

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

∆ ≤ p n+k-2 q 1 q 2 ≤ 2 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 ≤ (l 1 + l 2 ) -2e -n + 2 then, F k is a ((U G1 , U G2 ), 1 2 e )-deterministic extractor . Proof of corollary 4.1 If k ≤ (l 1 + l 2 ) -2e -n + 2, k+n 2 ≤ l1+l2+2 2 -e 2 k+n 2 ≤ 2 l 1 +l 2 +2 2 2 -e p n+k 4q1q2 ≤ 2 -e
(l1+l2)-2e-mn+2 m then, F k is a ((U G1 , U G2 ), 2 -e )-deterministic extractor .

Randomness extraction in elliptic curves

Let p be a prime greater than 5. Let E be an elliptic curve over the finite field F p and let P, Q be two subgroups of E(F p ). Let denote |P| = q 1 and |Q| = q 2 . Let U P and U Q be two random variables uniformly distributed in P and Q respectively.

Randomness extractor in

E(F p ) Definition 4.3 We define the function extrac k : P×Q -→ {0, 1} k , (P, Q) -→ lsb k (x(P)• x(Q)).
The following theorem shows that extrac k is a good randomness extractor.

Theorem 4.3 Let U k be the uniform distribution in {0, 1} k . Then, ∆(extrac k (U P , U Q ), U k ) 2 k+n+log 2 1 +l 2 +2) 2
.

Let us define K = 2 k , u 0 = msb m-k (p -1). Let us define the characteristic function

1((P, Q), (A, B), u) = 1 p ψ∈Ψ ψ(x(P)x(Q) -x(A)x(B) -Ku) which is equal to 1 if
ψ = ψ 0 and to 0, otherwise. Let us compute the collision probability:

Col(extrac k (U P , U Q )) = 1 (q 1 q 2 ) 2 p P∈P Q∈Q A∈P B∈Q ψ∈Ψ u≤u0 ψ(x(P)x(Q)-x(A)x(B)- Ku).
Then we manipulate the sums, separate some terms (ψ = ψ 0 ) with the rest.

So for (ψ = ψ 0 ),

Col(extrac k (U P , U Q )) = 1 (q 1 q 2 ) 2 p ψ=ψ0 P∈P Q∈Q A∈P B∈Q u≤u0 ψ 0 (0) = 1 (q 1 q 2 ) 2 p ψ=ψ0 P∈P Q∈Q A∈P B∈Q u≤u0 e p (T r(0)) = 1 (q 1 q 2 ) 2 p ψ=ψ0 P∈P Q∈Q A∈P B∈Q u≤u0 1 = u 0 + 1 p
And for (ψ = ψ 0 ),

Col(extrac k (U P , U Q )) = 1 (q 1 q 2 ) 2 p ψ =ψ0 P∈P Q∈Q A∈P B∈Q u≤u0 ψ(x(P)x(Q)-x(A)x(B)- Ku). Then for all ψ, Col(extrac k (U P , U Q )) = u 0 + 1 p + 1 (q 1 q 2 ) 2 p ψ =ψ0 P∈P Q∈Q A∈P B∈Q u≤u0 ψ(x(P)x(Q)- x(A)x(B) -Ku) = u 0 + 1 p + 1 (q 1 q 2 ) 2 p ψ =ψ0 P∈P Q∈Q ψ(x(P)x(Q)) A∈P B∈Q ψ(-x(A)x(B)) u≤u0 ψ(-Ku) = u 0 + 1 p + 1 (q 1 q 2 ) 2 p ψ =ψ0 | P∈P Q∈Q ψ(x(P)x(Q))|| A∈P B∈Q ψ(-x(A)x(B))| u≤u0 ψ(-Ku) = u 0 + 1 p + 1 (q 1 q 2 ) 2 p ψ =ψ0 |V(ψ, P, Q)| 2 u≤u0 ψ(-Ku) ≤ 1 p + 1 (q 1 q 2 ) 2 p ψ =ψ0 q 1 q 2 p u≤u0 ψ(-Ku), by Lemma 2.6 ≤ 1 p + 1 (q 1 q 2 ) 2 p pq 1 q 2 p log 2 (p), since it is shown that ψ =ψ0 u≤u0 ψ(-Ku) ≤ p log 2 (p) ≤ 1 p + 1 (q 1 q 2 )
p log 2 (p).

Therefore, using Lemma 2.1 with some manipulations, we obtain the expected result: ArrayofBits,Integer → ArrayofBits;

∆(extrac k (U P , U Q ), U k ) 2 k-2 p log 2 (p) q 1 q 2 = 2 k+n+log 2 (n)-(l
Axioms A1 initialize=[] A2 createKey(r) = createKey(ConvertToBits(r)) A3 getKeyLength(initialize) = 0 A4 getKeyLength(createKey(r)) = # getKeyLength(createKey(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)

Applications

The ideas behind a randomness extractors is the following one: suppose one got a random 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 impossible.

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) 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 minentropy δn, δ > 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 seize greater than 2 756 with Chevalier's et al. extractor [START_REF] Chevalier | Optimal Randomness Extraction from a Diffie-Hellman Element, Advances in Cryptology[END_REF]. With our extractor f k define in subsection 4.1.1, considering two groups of sizes 2 724 one can extracts 256bits. In this case, f k is an ((U G1 , U G2 ), 2 -80 )-deterministic extractor.

Exemple: key exchange protocol and key extraction from two-sources 1) For the first session, -Alice anb Bob choose a public elliptic curve group of points G = P ; Extrac k : G × G → {0, 1} k -Alice and Bob perform the DH ratchet as follows: i=1; Alice chooses a i ∈ Z * q , sends a i P to Bob; Bob chooses b i ∈ 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.

Conclusion

The problem is: how to ensure the indistinguability of a key session which is a string of bits issue to a shared element after 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 pseudorandom 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 .

Definition 2 . 1

 21 Collision probability.

1 -

 1 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: e p (-a(u 0 + 1))1 -e p (-a) = p log 2 (p)

Corollary 4 . 2

 42 Let p > 2 a prime such as |p| = m. If e > 1 and k > 1 are two integers such as k ≤

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 = 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 )).

  Winterhof bound. Let V be an additive subgroup of F p n and let ψ be an additive caracter of F p n . Then, Bilinear character sums. Let p be a prime number, G and H be two multiplicative subgroups of F * p . For all a ∈ F p * , let introduce the following notation: S(a, (G, H)) =

	See [24] pp 70
	Theorem 2.4 a∈F p n x∈V	ψ(ax) ≤ p n
	See [23]
	Definition 2.8 x∈G y∈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	|	x∈G y∈H	(e p (nxy))| ≤ (p|G||H|)	1 2
	Definition 2.7 Single character sums.
	Let p be a prime number, G a multiplicative subgroup of F * p . For all a ∈ F p * , let
	introduce the following notation: S(a, G) =	e p (ax).
						x∈G
	Lemma 2.3 Let p be a prime number, G a multiplicative subgroup of F * p .
	1) if a = 0,	p-1 x=0 e p (ax) = p
	2) For all a ∈ F * p ,			p-1 x=0 e p (ax) = 0
	3) For all x 0 ∈ G and all a ∈ 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 ∈ F * p :
					e p (ax) ≤	√ p
				x∈G

. Specification: Abstract Data Type

  Let us define the function Extrack : P×Q -→ F k p , (P, -→ (t 1 , t 2 , , t k ), where x(P) • x(Q) = t 1 α 1 + t 2 α 2 + +t n α n .The theorem below shows that Extrac k is a good randomness extractor over E(F p n ). Let U k be the uniform distribution in F k p . Then,∆(Extrac k (U P , U Q ), U k ) 2

	4.2.2. Randomness extractor in E(F p n )
	Definition 4.4 Theorem 4.4 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.3Sort ArrayofBits;
	Functions
	initialize:		→ ArrayofBits;
	createKey:	Integer	→ ArrayofBits;
	getKeyLength:	ArrayofBits	→	Integer;
	testParameterEntropy ArrayofBits,Integer →	Boolean;
	lsb-k:
				1 +l 2 +2)
			2

Two-source randomnes extractors in finite fields and in elliptic curves 51

* n