Paper 2015/614

Bit Security of the Hyperelliptic Curves Diffie-Hellman Problem

Fangguo Zhang

Abstract

The Diffie-Hellman problem as a cryptographic primitive plays an important role in modern cryptology. The Bit Security or Hard-Core Bits of Diffie-Hellman problem in arbitrary finite cyclic group is a long-standing open problem in cryptography. Until now, only few groups have been studied. Hyperelliptic curve cryptography is an alternative to elliptic curve cryptography. Due to the recent cryptanalytic results that the best known algorithms to attack hyperelliptic curve cryptosystems of genus $g<3$ are the generic methods and the recent implementation results that hyperelliptic curve cryptography in genus 2 has the potential to be competitive with its elliptic curve cryptography counterpart. In this paper, we generalize Boneh and Shparlinksi's method and result about elliptic curve to the case of Jacobians of hyperelliptic curves. We prove that the least significant bit of each coordinate of hyperelliptic curves Diffie-Hellman secret value in genus 2 is hard as the entire Diffie-Hellman value, and then we also show that any bit is hard as the entire Diffie-Hellman value. Finally, we extend our techniques and results to hyperelliptic curves of any genus.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
isszhfg @ mail sysu edu cn
History
2015-06-30: received
Short URL
https://ia.cr/2015/614
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/614,
      author = {Fangguo Zhang},
      title = {Bit Security of the Hyperelliptic Curves Diffie-Hellman Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2015/614},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/614}},
      url = {https://eprint.iacr.org/2015/614}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.