Skip to Main content Skip to Navigation
Conference papers

SQISign: compact post-quantum signatures from quaternions and isogenies

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.
Complete list of metadata
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Thursday, December 3, 2020 - 11:53:22 AM
Last modification on : Friday, January 21, 2022 - 3:23:21 AM
Long-term archiving on: : Thursday, March 4, 2021 - 6:57:51 PM


Files produced by the author(s)


  • HAL Id : hal-03038004, version 1


Luca de Feo, David Kohel, Antonin Leroux, Christophe Petit, Benjamin Wesolowski. SQISign: compact post-quantum signatures from quaternions and isogenies. ASIACRYPT 2020 - 26th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2020, Daejeon (virtual), South Korea. ⟨hal-03038004⟩



Les métriques sont temporairement indisponibles