Paper 2025/135

PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies

Andrea Basso, IBM Research - Zurich
Giacomo Borin, IBM Research - Zurich
Wouter Castryck, KU Leuven
Maria Corte-Real Santos, École Normale Supérieure de Lyon
Riccardo Invernizzi, KU Leuven
Antonin Leroux, Direction Générale de l'Armement
Luciano Maino, University of Bristol
Frederik Vercauteren, KU Leuven
Benjamin Wesolowski, École Normale Supérieure de Lyon
Abstract

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime and the prover simply replies with an efficient representation of an isogeny of degree from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. Our optimized C implementation of the signature scheme shows that signing is roughly faster than all SQIsign variants, whereas verification is times slower. The sizes of the public key and signature are comparable to existing schemes.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
post-quantumisogeniessignaturesidentification
Contact author(s)
andrea basso @ bristol ac uk
prism @ gbor in
wouter castryck @ gmail com
maria corte_real_santos @ ens-lyon fr
riccardo invernizzi @ esat kuleuven be
antonin leroux @ polytechnique org
luciano maino @ bristol ac uk
frederik vercauteren @ gmail com
benjamin wesolowski @ ens-lyon fr
History
2025-01-28: approved
2025-01-28: received
See all versions
Short URL
https://ia.cr/2025/135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/135,
      author = {Andrea Basso and Giacomo Borin and Wouter Castryck and Maria Corte-Real Santos and Riccardo Invernizzi and Antonin Leroux and Luciano Maino and Frederik Vercauteren and Benjamin Wesolowski},
      title = {{PRISM}: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/135},
      year = {2025},
      url = {https://eprint.iacr.org/2025/135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.