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 a given sufficiently large prime p, and a fixed elliptic curve over the prime field <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb {F}_p$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation>, if there is an oracle that outputs the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\frac{\delta }{\log _2 p}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>δ</mi> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>p</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation>-fraction of the most (least) significant bits of the x-coordinate of the ECDH key, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation> is the number of output bits that satisfies <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$0<\frac{\delta }{\log _2 p}<1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo><</mo> <mfrac> <mi>δ</mi> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>p</mi> </mrow> </mfrac> <mo><</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\frac{\delta }{\log _2 p}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>δ</mi> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>p</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation> is close to 0, then one can give a heuristic algorithm to compute all the bits within polynomial time in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\log _2 p$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>p</mi> </mrow> </math></EquationSource> </InlineEquation>. The known fraction <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\frac{\delta }{\log _2 p}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>δ</mi> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mi>p</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation> in our result can be any constant between (0, 1). Therefore, it is much better than some constant fractions of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\frac{5}{6}, \frac{1}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mn>5</mn> <mn>6</mn> </mfrac> <mo>,</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> in previous works [<CitationRef CitationID="CR33">33</CitationRef>, <CitationRef CitationID="CR36">36</CitationRef>]. 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.

New Results on Elliptic Curve Hidden Number Problem for ECDH Key Exchange

期刊论文
发表日期：

2026年3月6日

查看全文

Jun Xu,
Santanu Sarkar,
Huaxiong Wang,
Lei Hu

摘要

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 a given sufficiently large prime p, and a fixed elliptic curve over the prime field $\mathbb {F}_p$ $F_{p}$ , if there is an oracle that outputs the $\frac{\delta }{\log _2 p}$ $\frac{δ}{{log}_{2} p}$ -fraction of the most (least) significant bits of the x-coordinate of the ECDH key, where $\delta $ $δ$ is the number of output bits that satisfies $0<\frac{\delta }{\log _2 p}<1$ $0 < \frac{δ}{{log}_{2} p} < 1$ and $\frac{\delta }{\log _2 p}$ $\frac{δ}{{log}_{2} p}$ is close to 0, then one can give a heuristic algorithm to compute all the bits within polynomial time in $\log _2 p$ ${log}_{2} p$ . The known fraction $\frac{\delta }{\log _2 p}$ $\frac{δ}{{log}_{2} p}$ in our result can be any constant between (0, 1). Therefore, it is much better than some constant fractions of $\frac{5}{6}, \frac{1}{2}$ $\frac{5}{6}, \frac{1}{2}$ in previous works [33, 36]. 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.