On the Bit Security of Elliptic Curve Diffie--Hellman

Barak Shani

Paper 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.

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in PKC 2017
DOI: 10.1007/978-3-662-54365-8_15
Keywords: hidden number problem bit security elliptic curve Diffie--Hellman
Contact author(s): barak shani @ auckland ac nz
History: 2017-04-26: last of 2 revisions; 2017-01-01: received; See all versions
Short URL: https://ia.cr/2016/1189
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1189,
      author = {Barak Shani},
      title = {On the Bit Security of Elliptic Curve Diffie--Hellman},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1189},
      year = {2016},
      doi = {10.1007/978-3-662-54365-8_15},
      url = {https://eprint.iacr.org/2016/1189}
}