Cryptology ePrint Archive: Report 2018/1109

Faster SeaSign signatures through improved rejection sampling

Thomas Decru and 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.

Category / Keywords: cryptographic protocols / Isogeny-based cryptography, signatures, SeaSign, rejection sampling, group actions.

Date: received 15 Nov 2018, last revised 25 Jan 2019

Contact author: decruthomas at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20190125:132636 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]