Another look at some isogeny hardness assumptions

Simon-Philipp Merz, Romy Minko, Christophe Petit

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)
518 Downloads (Pure)


The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in 24λ/5 steps on a classical computer. This is an improvement over the expected classical security of 2λ , where λ denotes the chosen security parameter.
Original languageEnglish
Title of host publicationTopics in Cryptology – CT-RSA 2020
Subtitle of host publicationThe Cryptographers’ Track at the RSA Conference 2020
EditorsStanislaw Jarecki
Number of pages16
ISBN (Electronic)978-3-030-40185-6, 978-3-030-40186-3
Publication statusE-pub ahead of print - 14 Feb 2020
EventThe Cryptographer's Track at the RSA Conference (CT-RSA 2020) - San Francisco, United States
Duration: 24 Feb 202028 Feb 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceThe Cryptographer's Track at the RSA Conference (CT-RSA 2020)
Country/TerritoryUnited States
CitySan Francisco


  • elliptic curves
  • isogenies
  • undeniable signatures


Dive into the research topics of 'Another look at some isogeny hardness assumptions'. Together they form a unique fingerprint.

Cite this