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 26 Apr 2017

Contact author: barak shani at auckland ac nz

Available format(s): PDF | BibTeX Citation

Note: The main algorithm is randomized and not deterministic as appears in the published version. This affects the formulation of the claims in the main results.

Version: 20170426:173535 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]