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 problembit securityelliptic 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/1189}},
      url = {https://eprint.iacr.org/2016/1189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.