Sqisign Isogeny Signatures

Short answer: SQIsign is a post-quantum digital signature scheme built from isogenies between supersingular elliptic curves and quaternion algebras. Its 2020 introduction reported very small public keys and signatures, at the cost of slow signing. The scheme was presented at Asiacrypt 2020 and has follow-up work on making it practical. It is a research scheme whose figures come from the authors' own implementation.

What the scheme is

The paper, "SQISign: compact post-quantum signatures from quaternions and isogenies" by De Feo, Kohel, Leroux, Petit and Wesolowski, introduces a signature scheme whose name stands for Short Quaternion and Isogeny Signature. It uses isogeny graphs of supersingular elliptic curves, and the signature scheme is derived from a new one-round, high-soundness interactive identification protocol. The authors say the soundness of the identification protocol follows from classical assumptions.

Reported sizes and speed

Targeting the post-quantum NIST level 1 of security, the authors report from their implementation signatures of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes. They state that the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, their C implementation takes 0.6 seconds for key generation, 2.5 seconds for signing and 50 milliseconds for verification. These timings describe the 2020 implementation. A project page for the scheme lists later papers, including a 2022 paper on new algorithms for the Deuring correspondence aimed at making SQIsign practical and secure, so later versions may differ from these figures.

The zero-knowledge piece

The paper says the zero-knowledge property depends on a second contribution: a new algorithm for finding an isogeny path between two supersingular elliptic curves of known endomorphism rings. A previous algorithm, by Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a special curve, and the authors say that leakage would break the protocol's zero-knowledge property. Their algorithm does not directly reveal such a path. Subject to a new computational assumption, they prove the resulting identification protocol is zero-knowledge.

Reading the numbers

The size claim compares the combined signature and public key, which is 204 plus 64 bytes in the authors' report, against other post-quantum signature schemes. That is a size comparison only. The paper's own timings show the trade: key generation at 0.6 seconds and signing at 2.5 seconds are slow next to the 50 millisecond verification. A scheme with small outputs and slow signing suits some uses better than others, and the right choice depends on how often signatures are made and how much they cost to store or send. The project page summarises the scheme as having very compact keys and signatures and a complex signing procedure, which fits the 2020 figures.

Follow-up work

The 2022 paper listed on the project page, by De Feo, Leroux, Longa and Wesolowski, carries the title "New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures". Its title signals the aim of improving both practicality and security of the scheme. Readers should check the current specification for up-to-date sizes and speeds.

What this does not tell you

The paper's security rests on a new computational assumption, and it is a research proposal. It does not say the scheme is standardized or deployed. Isogeny-based cryptography has seen attacks on other schemes, so security claims about any one scheme need the continuing scrutiny the field gives them. Performance figures from 2020 should not be applied to current implementations.

FAQ

What does SQIsign stand for?

Short Quaternion and Isogeny Signature.

What is it built from?

Isogeny graphs of supersingular elliptic curves and quaternion algebras.

How small are the signatures?

The authors report 204 bytes with a 64-byte public key at NIST level 1.

Is it fast?

Verification takes 50 ms in the 2020 implementation, but signing takes 2.5 seconds.

Is it standardized?

These papers do not report that it is.