Welcome to the resource topic for
**2023/1409**

**Title:**

Solving the Hidden Number Problem for CSIDH and CSURF via Automated Coppersmith

**Authors:**
Jonas Meers, Julian Nowakowski

**Abstract:**

We define and analyze the Commutative Isogeny Hidden

Number Problem which is the natural analogue of the Hidden Number Problem in the CSIDH and CSURF setting. In short, the task is as follows: Given two supersingular elliptic curves (E_A), (E_B) and access to an oracle that outputs some of the most significant bits of the ({\mathsf{CDH}}) of two curves, an adversary must compute the shared curve (E_{AB}={\mathsf{CDH}}(E_A,E_B)).

We show that we can recover (E_{AB}) in polynomial time by using Coppersmithâ€™s method as long as the oracle outputs ({\frac{13}{24}} + \varepsilon \approx 54%) (CSIDH) and ({\frac{31}{41}} + \varepsilon \approx 76%) (CSURF) of the most significant bits of the ({\mathsf{CDH}}), where \varepsilon > 0 is an arbitrarily small constant. To this end, we give a purely combinatorial restatement of Coppersmithâ€™s method, effectively concealing the intricate aspects of lattice theory and allowing for near-complete automation. By leveraging this approach, we attain recovery attacks with \varepsilon close to zero within a few minutes of computation.

**ePrint:**
https://eprint.iacr.org/2023/1409

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .