Accueil > Résultats de la recherche > Suite de la publication

Randomness extraction in elliptic curves and secret key derivation at the end of Diffie-Hellman protocol

A deterministic extractor for an elliptic curve, that converts a uniformly random point on the curve to a random $k$-bit-string with a distribution close to uniform, is an important tool in cryptography. Such extractors can be used for example in key derivation functions, in key exchange protocols and to design cryptographically secure pseudorandom number generator. In this paper, we present a simple and efficient deterministic extractor for an elliptic curve $E$ defined over $\mathbb{F}_{p^n}$, where $p$ is prime and $n$ is a positive integer. Our extractor, denoted by $\mathcal{D}_k$, for a given random point $P$ on $E$, outputs the $k$-first $\mathbb{F}_{p}$-coordinates of the abscissa of the point $P$. This extractor confirms the two conjectures stated by R. R. Farashahi and R. Pellikaan in \cite{qe} and by R. R. Farashahi, A. Sidorenko and R. Pellikaan in \cite{be}, related to the extraction of bits from coordinates of a point of an elliptic curve. As applications of our extractor, for elliptic curves $E(\mathbb{F}_{2^n})$ over binary finite fields $\mathbb{F}_{2^n}$, we have shown that under the DDH assumption, the $k$-first $\mathbb{F}_{2}$-coefficients (the $k$ least significant bits) of the abscissa of the point $P$ of a random group-element in a subgroup $G$ of $E(\mathbb{F}_{2^n})$, are indistinguishable from a random bit-string of the same length. The large $|G|$ is the main drawback here for elliptic curve over binary field because $|G|$ is grater than $\sqrt{2^{n}}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This paper is the full version of the extended abstract that appear in "Nitaj, Abderrahmane and David Pointcheval (ed.), Progress in cryptology-AFRICACRYPT 2011. 4th international conference on cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 6737, 290-297 (2011)"


Auteur(s) : Ciss, Abdoul Aziz and Sow, Djiby
Pages : 360–365
Année de publication : 2012
Revue : Int. J. Appl. Cryptogr.
N° de volume : 4
Type : Article
Mise en ligne par : SOW Djiby