Faster SeaSign signatures through improved rejection sampling

Thomas Decru; Lorenz Panny; Frederik Vercauteren

Faster SeaSign signatures through improved rejection sampling

Thomas Decru
, Lorenz Panny
, Frederik Vercauteren

Research output: Working paper › Preprint › Academic

113 Downloads (Pure)

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 language	English
Publisher	International Association for Cryptologic Research
Number of pages	14
Volume	2018/1109
Publication status	Published - 2018

Keywords

cryptographic protocols
Isogeny-based cryptography, signatures, SeaSign, rejection sampling, group actions

Access to Document

publishers versionFinal published version, 563 KB

https://eprint.iacr.org/2018/1109

Cite this

@techreport{025a3b64a8df4a3c9701bf140550cf42,

title = "Faster SeaSign signatures through improved rejection sampling",

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. ",

keywords = "cryptographic protocols, Isogeny-based cryptography, signatures, SeaSign, rejection sampling, group actions",

author = "Thomas Decru and Lorenz Panny and Frederik Vercauteren",

year = "2018",

language = "English",

volume = "2018/1109",

publisher = "International Association for Cryptologic Research",

type = "WorkingPaper",

institution = "International Association for Cryptologic Research",

}

TY - UNPB

T1 - Faster SeaSign signatures through improved rejection sampling

AU - Decru, Thomas

AU - Panny, Lorenz

AU - Vercauteren, Frederik

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - cryptographic protocols

KW - Isogeny-based cryptography, signatures, SeaSign, rejection sampling, group actions

M3 - Preprint

VL - 2018/1109

BT - Faster SeaSign signatures through improved rejection sampling

PB - International Association for Cryptologic Research

ER -

Faster SeaSign signatures through improved rejection sampling

Abstract

Keywords

Access to Document

Fingerprint

Cite this