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

Andrea Basso; Giacomo  Borin; Wouter Castryck; Maria  Corte-Real Santos; Riccardo Invernizzi; Antonin  Leroux; Luciano Maino; Frederik Vercauteren; Benjamin Wesolowski

doi:10.1007/978-3-031-91826-1_10

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

Andrea Basso^*
, Giacomo Borin
, Wouter Castryck
, Maria Corte-Real Santos
, Riccardo Invernizzi
, Antonin Leroux
, Luciano Maino
, Frederik Vercauteren
, Benjamin Wesolowski

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

14 Citations (Scopus)

81 Downloads (Pure)

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 q and the prover simply replies with an efficient representation of an isogeny of degree q 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 1.8× faster than all SQIsign variants, whereas verification is 1.4× times slower. The sizes of the public key and signature are comparable to existing schemes.

Original language	English
Title of host publication	Public-Key Cryptography – PKC 2025
Subtitle of host publication	28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings
Editors	Tibor Jager, Jiaxin Pan
Publisher	Springer, Cham
Pages	300-332
Number of pages	33
Volume	3
ISBN (Electronic)	9783031918261
ISBN (Print)	9783031918254
DOIs	https://doi.org/10.1007/978-3-031-91826-1_10
Publication status	Published - 5 May 2025
Event	PKC 2025 - Røros, Norway Duration: 12 May 2025 → 15 May 2025 https://pkc.iacr.org/2025/

Publication series

Name	Lecture Notes in Computer Science
Volume	15676 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	PKC 2025
Country/Territory	Norway
City	Røros
Period	12/05/25 → 15/05/25
Internet address	https://pkc.iacr.org/2025/

Bibliographical note

Publisher Copyright:
© International Association for Cryptologic Research 2025.

Access to Document

10.1007/978-3-031-91826-1_10

Full-text PDF (accepted manuscript)
This is the accepted author manuscript (AAM) of the article which has been made Open Access under the University of Bristol's Scholarly Works Policy. The final published version (Version of Record) can be found on the publisher's website. The copyright of any third-party content, such as images, remains with the copyright holder.
Accepted author manuscript, 756 KBLicence: CC BY

https://eprint.iacr.org/2025/135Licence: CC BY

Handle.net

Persistent link

Cite this

Basso, A., Borin, G., Castryck, W., Corte-Real Santos, M., Invernizzi, R., Leroux, A., Maino, L., Vercauteren, F., & Wesolowski, B. (2025). PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies. In T. Jager, & J. Pan (Eds.), Public-Key Cryptography – PKC 2025: 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings (Vol. 3, pp. 300-332). (Lecture Notes in Computer Science; Vol. 15676 LNCS). Springer, Cham. https://doi.org/10.1007/978-3-031-91826-1_10

Basso, Andrea ; Borin, Giacomo ; Castryck, Wouter et al. / PRISM : Simple And Compact Identification and Signatures From Large Prime Degree Isogenies. Public-Key Cryptography – PKC 2025: 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings. editor / Tibor Jager ; Jiaxin Pan. Vol. 3 Springer, Cham, 2025. pp. 300-332 (Lecture Notes in Computer Science).

@inproceedings{1050e61f4764412ebb5d896e78827f51,

title = "PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies",

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 q and the prover simply replies with an efficient representation of an isogeny of degree q 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 1.8× faster than all SQIsign variants, whereas verification is 1.4× times slower. The sizes of the public key and signature are comparable to existing schemes.",

author = "Andrea Basso and Giacomo Borin and Wouter Castryck and \{Corte-Real Santos\}, Maria and Riccardo Invernizzi and Antonin Leroux and Luciano Maino and Frederik Vercauteren and Benjamin Wesolowski",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2025.; PKC 2025 ; Conference date: 12-05-2025 Through 15-05-2025",

year = "2025",

month = may,

day = "5",

doi = "10.1007/978-3-031-91826-1\_10",

language = "English",

isbn = "9783031918254",

volume = "3",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "300--332",

editor = "Tibor Jager and Jiaxin Pan",

booktitle = "Public-Key Cryptography – PKC 2025",

address = "Switzerland",

url = "https://pkc.iacr.org/2025/",

}

Basso, A, Borin, G, Castryck, W, Corte-Real Santos, M, Invernizzi, R, Leroux, A, Maino, L, Vercauteren, F & Wesolowski, B 2025, PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies. in T Jager & J Pan (eds), Public-Key Cryptography – PKC 2025: 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings. vol. 3, Lecture Notes in Computer Science, vol. 15676 LNCS, Springer, Cham, pp. 300-332, PKC 2025, Røros, Norway, 12/05/25. https://doi.org/10.1007/978-3-031-91826-1_10

PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies. / Basso, Andrea; Borin, Giacomo ; Castryck, Wouter et al.
Public-Key Cryptography – PKC 2025: 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings. ed. / Tibor Jager; Jiaxin Pan. Vol. 3 Springer, Cham, 2025. p. 300-332 (Lecture Notes in Computer Science; Vol. 15676 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - PRISM

T2 - PKC 2025

AU - Basso, Andrea

AU - Borin, Giacomo

AU - Castryck, Wouter

AU - Corte-Real Santos, Maria

AU - Invernizzi, Riccardo

AU - Leroux, Antonin

AU - Maino, Luciano

AU - Vercauteren, Frederik

AU - Wesolowski, Benjamin

PY - 2025/5/5

Y1 - 2025/5/5

N2 - 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 q and the prover simply replies with an efficient representation of an isogeny of degree q 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 1.8× faster than all SQIsign variants, whereas verification is 1.4× times slower. The sizes of the public key and signature are comparable to existing schemes.

AB - 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 q and the prover simply replies with an efficient representation of an isogeny of degree q 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 1.8× faster than all SQIsign variants, whereas verification is 1.4× times slower. The sizes of the public key and signature are comparable to existing schemes.

UR - https://pkc.iacr.org/2025/

U2 - 10.1007/978-3-031-91826-1_10

DO - 10.1007/978-3-031-91826-1_10

M3 - Conference Contribution (Conference Proceeding)

SN - 9783031918254

VL - 3

T3 - Lecture Notes in Computer Science

SP - 300

EP - 332

BT - Public-Key Cryptography – PKC 2025

A2 - Jager, Tibor

A2 - Pan, Jiaxin

PB - Springer, Cham

Y2 - 12 May 2025 through 15 May 2025

ER -

Basso A, Borin G, Castryck W, Corte-Real Santos M, Invernizzi R, Leroux A et al. PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies. In Jager T, Pan J, editors, Public-Key Cryptography – PKC 2025: 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12–15, 2025, Proceedings. Vol. 3. Springer, Cham. 2025. p. 300-332. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-91826-1_10

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

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this