Paper 2019/950

Another look at some isogeny hardness assumptions

Simon-Philipp Merz, Romy Minko, and Christophe Petit

Abstract

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 $2^{4\lambda/5}$ steps on a classical computer. This is an improvement over the expected classical security of $2^{\lambda}$, where $\lambda$ denotes the chosen security parameter.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
post-quantum cryptographyisogeny-based cryptographycryptanalysis
Contact author(s)
simon-philipp merz 2018 @ rhul ac uk
History
2019-12-01: last of 3 revisions
2019-08-21: received
See all versions
Short URL
https://ia.cr/2019/950
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/950,
      author = {Simon-Philipp Merz and Romy Minko and Christophe Petit},
      title = {Another look at some isogeny hardness assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/950},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/950}},
      url = {https://eprint.iacr.org/2019/950}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.