CryptoDB
SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies
| Authors: | |
|---|---|
| Download: | |
| 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
BibTeX
@article{asiacrypt-2020-30712,
title={SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies},
booktitle={Advances in Cryptology - ASIACRYPT 2020},
publisher={Springer},
doi={10.1007/978-3-030-64837-4_3},
author={Luca De Feo and David Kohel and Antonin Leroux and Christophe Petit and Benjamin Wesolowski},
year=2020
}