Cryptology ePrint Archive: Report 2020/1240

SQISign: compact post-quantum signatures from quaternions and isogenies

Luca De Feo and David Kohel and Antonin Leroux and Christophe Petit and Benjamin Wesolowski

Abstract: We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

Category / Keywords: public-key cryptography / Isogeny-based cryptography, digital-signature, post-quantum

Original Publication (with minor differences): IACR-ASIACRYPT-2020

Date: received 8 Oct 2020

Contact author: antonin leroux at polytechnique org

Available format(s): PDF | BibTeX Citation

Version: 20201009:113426 (All versions of this report)

Short URL: ia.cr/2020/1240


[ Cryptology ePrint archive ]