We revisit the Commutative Isogeny Hidden Number Problem (CI-HNP), an analogue of the classical Hidden Number Problem in the CSURF setting, where an adversary is tasked with recovering a shared elliptic curve \( E_{AB} \) over a prime field GF(p) from partial information about the most significant bits (MSBs) of the Montgomery coefficient. In particular, we focus on improving the recovery bound for the CSURF protocol. Meers and Nowakowski (Asiacrypt 2023) demonstrated that an adversary can recover \( E_{AB} \) in polynomial time when the total unknown portion is bounded by 73.2% of size of prime p. We present an enhanced attack that improves this bound to 77.9%. Our improvement is achieved by refining the application of Coppersmith method. Our result highlights the need for a thorough reassessment of bit security in isogeny-based cryptographic protocols like CSURF, particularly in the context of partial information attacks.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Enhanced Bound for the Commutative Isogeny Hidden Number Problem in CSURF

  • Santanu Sarkar

摘要

We revisit the Commutative Isogeny Hidden Number Problem (CI-HNP), an analogue of the classical Hidden Number Problem in the CSURF setting, where an adversary is tasked with recovering a shared elliptic curve \( E_{AB} \) over a prime field GF(p) from partial information about the most significant bits (MSBs) of the Montgomery coefficient. In particular, we focus on improving the recovery bound for the CSURF protocol. Meers and Nowakowski (Asiacrypt 2023) demonstrated that an adversary can recover \( E_{AB} \) in polynomial time when the total unknown portion is bounded by 73.2% of size of prime p. We present an enhanced attack that improves this bound to 77.9%. Our improvement is achieved by refining the application of Coppersmith method. Our result highlights the need for a thorough reassessment of bit security in isogeny-based cryptographic protocols like CSURF, particularly in the context of partial information attacks.