International Association for Cryptologic Research

International Association
for Cryptologic Research


SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies

Luca De Feo
David Kohel
Antonin Leroux
Christophe Petit
Benjamin Wesolowski
DOI: 10.1007/978-3-030-64837-4_3
Search ePrint
Search Google
Award: Best Paper Award
Abstract: We introduce a new signature scheme, \emph{SQISign}, (for \emph{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.
Video from ASIACRYPT 2020
  title={SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Luca De Feo and David Kohel and Antonin Leroux and Christophe Petit and Benjamin Wesolowski},