### SQISign: compact post-quantum signatures from quaternions and isogenies

Luca De Feo, David Kohel, Antonin Leroux, 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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
Isogeny-based cryptographydigital-signaturepost-quantum
Contact author(s)
antonin leroux @ polytechnique org
History
2021-01-19: revised
See all versions
Short URL
https://ia.cr/2020/1240

CC BY

BibTeX

@misc{cryptoeprint:2020/1240,
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{https://eprint.iacr.org/2020/1240}},
url = {https://eprint.iacr.org/2020/1240}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.