Cryptology ePrint Archive: Report 2016/1189

On the Bit Security of Elliptic Curve Diffie--Hellman

Barak Shani

Abstract: This paper gives the first bit security result for the elliptic curve Diffie--Hellman key exchange protocol for elliptic curves defined over prime fields. About $5/6$ of the most significant bits of the $x$-coordinate of the Diffie--Hellman key are as hard to compute as the entire key. A similar result can be derived for the $5/6$ lower bits. The paper also generalizes and improves the result for elliptic curves over extension fields, that shows that computing one component (in the ground field) of the Diffie--Hellman key is as hard to compute as the entire key.

Category / Keywords: public-key cryptography / hidden number problem, bit security, elliptic curve Diffie--Hellman

Original Publication (with minor differences): IACR-PKC-2017

Date: received 29 Dec 2016, last revised 3 Mar 2017

Contact author: barak shani at auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20170303:084709 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]