Cryptology ePrint Archive: Report 2005/324

Extracting bits from coordinates of a point of an elliptic curve

Nicolas G\"urel

Abstract: In the classic Diffie-Hellman protocol based on a generic group $\G$, Alice and Bob agree on a common secret $K_{AB}$ (master secret) which is indistinguishable from another element of $\G$ but not from a random bits-string of the same length. In this paper, we present a new deterministic method to extract bits from $K_{AB}$ when $\G$ is an elliptic curve defined over a quadratic extension of a finite field. In the last section, we show that it is also possible to extract a few bits when $\G$ is an elliptic curve defined over a prime field.

Category / Keywords: public-key cryptography / Elliptic curve cryptosystem, key derivation, pseudo-random extractors.

Date: received 12 Sep 2005

Contact author: gurel at lix polytechnique fr

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050913:201009 (All versions of this report)

Discussion forum: Show discussion | Start new discussion