Title: SQISign: Compact Post-Quantum Signature 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.
