Paper 2020/1240

SQISign: compact post-quantum signatures from quaternions and isogenies

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


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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Isogeny-based cryptographydigital-signaturepost-quantum
Contact author(s)
antonin leroux @ polytechnique org
2021-01-19: revised
2020-10-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Luca De Feo and David Kohel and Antonin Leroux and Christophe Petit and Benjamin Wesolowski},
      title = {SQISign: compact post-quantum signatures from quaternions and isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1240},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.