Faster SeaSign signatures through improved rejection sampling

Thomas Decru, Lorenz Panny, Frederik Vercauteren

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)


We speed up the isogeny-based “SeaSign” signature scheme recently proposed by De Feo and Galbraith. The core idea in SeaSign is to apply the “Fiat–Shamir with aborts” transform to the parallel repeated execution of an identification scheme based on CSIDH. We optimize this general transform by allowing the prover to not answer a limited number of said parallel executions, thereby lowering the overall probability of rejection. The performance improvement ranges between factors of approximately 4.4 and 65.7 for various instantiations of the scheme, at the expense of roughly doubling the signature sizes.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 10th International Conference, PQCrypto 2019, Revised Selected Papers
EditorsJintai Ding, Rainer Steinwandt
Place of PublicationCham
Number of pages15
ISBN (Print)9783030255091
Publication statusPublished - 14 Jul 2019
Event10th International Conference on Post-Quantum Cryptography, PQCrypto 2019 - Chongquin, China
Duration: 8 May 201910 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11505 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Conference on Post-Quantum Cryptography, PQCrypto 2019


  • Group actions
  • Isogeny-based cryptography
  • Rejection sampling
  • SeaSign
  • Signatures


Dive into the research topics of 'Faster SeaSign signatures through improved rejection sampling'. Together they form a unique fingerprint.

Cite this