Faster SeaSign signatures through improved rejection sampling

Thomas Decru, Lorenz Panny, Frederik Vercauteren

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

7 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages271-285
Number of pages15
ISBN (Print)9783030255091
DOIs
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

Conference

Conference10th International Conference on Post-Quantum Cryptography, PQCrypto 2019
CountryChina
CityChongquin
Period8/05/1910/05/19

Keywords

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

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

Cite this