Paper Info
Title
Optimal Randomness Extraction from a Diffie-Hellman Element
Abstract
In this paper, we study a quite simple deterministic randomness extractor from random Diffie-Hellman elements defined over a prime order multiplicative subgroup G of a finite field ${\mathbb Z}_p$ (the truncation), and over a group of points of an elliptic curve (the truncation of the abscissa). Informally speaking, we show that the least significant bits of a random element in $G\subset {\mathbb Z}_p^*$ or of the abscissa of a random point in $\mathcal{E}({\mathbb F}_p)$ are indistinguishable from a uniform bit-string. Such an operation is quite efficient, and is a good randomness extractor, since we show that it can extract nearly the same number of bits as the Leftover Hash Lemma can do for most Elliptic Curve parameters and for large subgroups of finite fields. To this aim, we develop a new technique to bound exponential sums that allows us to double the number of extracted bits compared with previous known results proposed at ICALP'06 by Fouque et al . It can also be used to improve previous bounds proposed by Canetti et al . One of the main application of this extractor is to mathematically prove an assumption proposed at Crypto '07 and used in the security proof of the Elliptic Curve Pseudo Random Generator proposed by the NIST. The second most obvious application is to perform efficient key derivation given Diffie-Hellman elements.
Year
DOI
Venue
2009
10.1007/978-3-642-01001-9_33
EUROCRYPT
Keywords
Field
DocType
diffie-hellman element,optimal randomness extraction,elliptic curve pseudo random,good randomness extractor,finite field,simple deterministic randomness extractor,random element,random diffie-hellman element,mathbb z,mathbb f,random point,least significant bit,diffie hellman,pseudo random generator,elliptic curve,exponential sum
Discrete mathematics,Randomness extractor,Random element,Leftover hash lemma,Finite field,Combinatorics,Abscissa,Pseudorandom generator,Mathematics,Elliptic curve,Randomness
Conference
Volume
ISSN
Citations 
5479
0302-9743
17
PageRank 
References 
Authors
0.80
22
4
Name
Order
Citations
PageRank
Céline Chevalier122515.82
Pierre-Alain Fouque21762107.22
David Pointcheval378133.25
Sébastien Zimmer42059.29