| Abstract: |
| The Elliptic Curve Hidden Number Problem (EC-HNP) was introduced at Asiacrypt 2001, and its Diffie-Hellman variant proposed at PKC 2017 serves for evaluating ECDH bit security and side-channel cryptanalysis. In this talk, we present the Coppersmith method for solving the multivariate modular polynomials in this variant. For a fixed elliptic curve over $\mathbb{F}_p$ with large prime $p$, if an oracle returns $\delta/\log_2 p$ fraction of the most (least) significant bits of the ECDH key`s $x$-coordinate, we give a heuristic polynomial-time algorithm in $\log_2 p$ to recover the full secret. Our result allows any constant ratio in $(0,1)$, which improves over the bounds $5/6$ and $1/2$ in earlier works. Although no rigorous ECDH bit security is derived, experiments on NIST curves with small lattices validate the heuristic effectiveness. |
|