Paper 2022/1239
Improving Bounds on Elliptic Curve Hidden Number Problem for ECDH Key Exchange
Abstract
Elliptic Curve Hidden Number Problem (ECHNP) was first introduced by Boneh, Halevi and HowgraveGraham at Asiacrypt 2001. To rigorously assess the bit security of the DiffieHellman key exchange with elliptic curves (ECDH), the DiffieHellman variant of ECHNP, regarded as an elliptic curve analogy of the Hidden Number Problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of sidechannel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the DiffieHellman variant of ECHNP and demonstrate that, for any given positive integer $d$, a given sufficiently large prime $p$, and a fixed elliptic curve over the prime field $\mathbb{F}_p$, if there is an oracle that outputs about $\frac{1}{d+1}$ of the most (least) significant bits of the $x$coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in $\log_2 p$. When $d>1$, the heuristic result $\frac{1}{d+1}$ significantly outperforms both the rigorous bound $\frac{5}{6}$ and heuristic bound $\frac{1}{2}$. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2022
 Keywords
 Elliptic curve Hidden number problem Modular inversion hidden number problem Lattice Coppersmith method.
 Contact author(s)

xujun @ iie ac cn
sarkar santanu bir @ gmail com
HXWang @ ntu edu sg
hulei @ iie ac cn  History
 20220919: approved
 20220919: received
 See all versions
 Short URL
 https://ia.cr/2022/1239
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1239, author = {Jun Xu and Santanu Sarkar and Huaxiong Wang and Lei Hu}, title = {Improving Bounds on Elliptic Curve Hidden Number Problem for {ECDH} Key Exchange}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1239}, year = {2022}, url = {https://eprint.iacr.org/2022/1239} }