### Improving Bounds on Elliptic Curve Hidden Number Problem for ECDH Key Exchange

##### Abstract

Elliptic Curve Hidden Number Problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie--Hellman key exchange with elliptic curves (ECDH), the Diffie--Hellman variant of EC-HNP, 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 side-channel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie--Hellman variant of EC-HNP 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.

Available format(s)
Category
Public-key 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
2022-09-19: approved
See all versions
Short URL
https://ia.cr/2022/1239

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},
note = {\url{https://eprint.iacr.org/2022/1239}},
url = {https://eprint.iacr.org/2022/1239}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.