PRISM is an isogeny-based cryptographic framework that relies on the hardness of computing a large prime-degree isogeny from a supersingular elliptic curve with an unknown endomorphism ring. It includes both an identification scheme PRISM-id and a signature scheme PRISM-sig. In this work, we present two attacks on PRISM-id. First, we analyze the probability that a randomly sampled prime q in PRISM-id results in a q-torsion subgroup defined over a small extension field, and we show that this probability is higher than claimed in the original proposal. Exploiting this observation, we construct classical forgery attacks on PRISM-id. The first attack addresses the scenario in which the attacker cannot reject a challenge. It succeeds with probability \(\tilde{\varTheta }(2^{-(\lambda + \log \lambda )(1-\varepsilon )})\) and runs in expected time \(\tilde{O}(\max \{2^{3\lambda \varepsilon }, 2^{\lambda (\varepsilon + 1/2)}\})\) for any positive real number \(\varepsilon < 1/3\) . Setting \(\varepsilon = 1/4\) yields success probability \(\tilde{\varTheta }(2^{-3(\lambda + \log \lambda )/4})\) and expected time complexity \(\tilde{O}(2^{3\lambda /4})\) . The second forgery attack covers the scenario in which the attacker is allowed to reject challenges. It always succeeds and runs in expected time \(\tilde{O}(2^{6\lambda /7})\) . Finally, we describe an attack against the underlying hardness assumption of PRISM-id that runs in expected time \(\tilde{O}(2^{\lambda /2})\) . Note that our results do not affect the security of PRISM-sig.

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

Attacks on PRISM-id via Torsion over Small Extension Fields

  • Kohei Nakagawa,
  • Hiroshi Onuki

摘要

PRISM is an isogeny-based cryptographic framework that relies on the hardness of computing a large prime-degree isogeny from a supersingular elliptic curve with an unknown endomorphism ring. It includes both an identification scheme PRISM-id and a signature scheme PRISM-sig. In this work, we present two attacks on PRISM-id. First, we analyze the probability that a randomly sampled prime q in PRISM-id results in a q-torsion subgroup defined over a small extension field, and we show that this probability is higher than claimed in the original proposal. Exploiting this observation, we construct classical forgery attacks on PRISM-id. The first attack addresses the scenario in which the attacker cannot reject a challenge. It succeeds with probability \(\tilde{\varTheta }(2^{-(\lambda + \log \lambda )(1-\varepsilon )})\) and runs in expected time \(\tilde{O}(\max \{2^{3\lambda \varepsilon }, 2^{\lambda (\varepsilon + 1/2)}\})\) for any positive real number \(\varepsilon < 1/3\) . Setting \(\varepsilon = 1/4\) yields success probability \(\tilde{\varTheta }(2^{-3(\lambda + \log \lambda )/4})\) and expected time complexity \(\tilde{O}(2^{3\lambda /4})\) . The second forgery attack covers the scenario in which the attacker is allowed to reject challenges. It always succeeds and runs in expected time \(\tilde{O}(2^{6\lambda /7})\) . Finally, we describe an attack against the underlying hardness assumption of PRISM-id that runs in expected time \(\tilde{O}(2^{\lambda /2})\) . Note that our results do not affect the security of PRISM-sig.