Paper 2018/1109

Faster SeaSign signatures through improved rejection sampling

Thomas Decru, Lorenz Panny, and Frederik Vercauteren

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.

Note: Fixed small error in code and reduced signature size. Added 2 formulas to clarify analysis.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Isogeny-based cryptographysignaturesSeaSignrejection samplinggroup actions.
Contact author(s)
decruthomas @ gmail com
History
2019-01-25: last of 2 revisions
2018-11-16: received
See all versions
Short URL
https://ia.cr/2018/1109
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1109,
      author = {Thomas Decru and Lorenz Panny and Frederik Vercauteren},
      title = {Faster SeaSign signatures through improved rejection sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1109},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1109}},
      url = {https://eprint.iacr.org/2018/1109}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.