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

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 EA, EB and access to an oracle that outputs some of the most significant bits of the CDH of two curves, an adversary must compute the shared curve EAB = CDH(EA, EB).

We show that we can recover EAB in polynomial time by using Coppersmith’s method as long as the oracle outputs 13/24 + eps (CSIDH) and 31/41 + eps of the most significant bits of the CDH, where eps > 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 eps close to zero within a few minutes of computation.