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: Contribution to journal › Article › Academic

88 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
Number of pages	14
Journal	IACR Cryptology ePrint Archive
Volume	2018
Issue number	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

@article{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",

journal = "IACR Cryptology ePrint Archive",

publisher = "IACR",

number = "2018/1109",

}

TY - JOUR

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 - Article

VL - 2018

JO - IACR Cryptology ePrint Archive

JF - IACR Cryptology ePrint Archive

IS - 2018/1109

ER -

Faster SeaSign signatures through improved rejection sampling

Abstract

Keywords

Access to Document

Fingerprint

Cite this