Paper 2023/1409
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 \(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 nearcomplete automation. By leveraging this approach, we attain recovery attacks with $\varepsilon$ close to zero within a few minutes of computation.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2023
 Keywords
 CoppersmithIsogeniesCSIDHCSURFHidden Number ProblemCryptanalysis
 Contact author(s)

jonas lehmannc6j @ rub de
julian nowakowski @ rub de  History
 20230924: approved
 20230919: received
 See all versions
 Short URL
 https://ia.cr/2023/1409
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1409, author = {Jonas Meers and Julian Nowakowski}, title = {Solving the Hidden Number Problem for {CSIDH} and {CSURF} via Automated Coppersmith}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1409}, year = {2023}, url = {https://eprint.iacr.org/2023/1409} }