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

Jonas Meers; Julian Nowakowski

Paper 2023/1409

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

Jonas Meers

, Ruhr University Bochum

Julian Nowakowski

, Ruhr University Bochum

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 $CDH$ of two curves, an adversary must compute the shared curve . We show that we can recover in polynomial time by using Coppersmith's method as long as the oracle outputs (CSIDH) and (CSURF) of the most significant bits of the , where 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 close to zero within a few minutes of computation.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in ASIACRYPT 2023
Keywords: Coppersmith Isogenies CSIDH CSURF Hidden Number Problem Cryptanalysis
Contact author(s): jonas lehmann-c6j @ rub de
julian nowakowski @ rub de
History: 2023-09-24: approved; 2023-09-19: 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}
}