SQIsign is a post-quantum signature scheme submitted to first round of the post-quantum standardisation process. It is based around a proof of knowledge of an elliptic curve^[a] endomorphism that can be transformed to a signature scheme using the Fiat–Shamir transform.

It promises small key sizes between 64 and 128 bytes and small signature sizes between 177 and 335 bytes, which outperforms other post-quantum signature schemes that have a trade-off between signature and key sizes. SQIsign, however, has higher signing and verification times.^[4] The original paper concluded that their C implementation takes 0.6 s for key generation, 2.5 s for a sign operation and 0.05 s or 50 ms for a verification operation.^[5]

These times have been improved with new variations like SQIsign-east.^[6]

The name stands for "Short Quaternion and Isogeny Signature" as it makes use of isogenies and quaternions.

SQIsign is a sigma protocol for a proof of knowledge that is turned into a signature scheme using the Fiat-Shamir transform. The knowledge that is proven is an elliptic curve endomorphism.^[7]: 5

SQIsign primarily operates on elliptic curves. Two elliptic curves ${\displaystyle E_{1}}$ and ${\displaystyle E_{2}}$ can be connected with an isogeny ${\displaystyle \varphi }$, written as ${\displaystyle \varphi :E_{1}\rightarrow E_{2}}$, which maps all elements of ${\displaystyle E_{1}}$ onto ${\displaystyle E_{2}}$. The fundamental problem that isogeny-based cryptography like SQIsign is based on is called the isogeny path problem and can be formulated as "find an isogeny ${\displaystyle \varphi :E_{1}\rightarrow E_{2}}$ given ${\displaystyle E_{1}}$ and ${\displaystyle E_{2}}$", which is believed to be hard. An endomorphism of an elliptic curve ${\displaystyle E}$ is an isogeny that maps ${\displaystyle E}$ onto itself, i.e. ${\displaystyle \varphi :E\rightarrow E}$. The set of all endomophisms of an elliptic curve is known as it's endomorphism ring, written as ${\displaystyle {\textrm {End}}(E)}$. The endomorphism problem can be formulated as "given ${\displaystyle E}$, find ${\displaystyle {\textrm {End}}(E)}$". Even computing a non-trivial part of ${\displaystyle {\textrm {End}}(E)}$ is known to be as hard as computing the full ${\displaystyle {\textrm {End}}(E)}$. This problem is known to be as hard as the isogeny path problem for supersingular curves like the ones SQIsign uses. Furthermore, given two elliptic curves ${\displaystyle E_{1}}$ and ${\displaystyle E_{2}}$, one can compute one of ${\displaystyle ({\textrm {End}}(E_{1}),{\textrm {End}}(E_{2}),\varphi :E_{1}\rightarrow E_{2})}$ given the other two in polynomial time, i.e. the problem is easy.^[7]: 5

The sigma protocol works as follows. The prover has ${\displaystyle E_{pk}}$ and ${\displaystyle {\textrm {End}}(E_{pk})}$ and publishes ${\displaystyle E_{pk}}$ as their public key while keeping ${\displaystyle {\textrm {End}}(E_{pk})}$ private. The prover then tries to convince the verifier that they know ${\displaystyle {\textrm {End}}(E_{pk})}$, which is hard to compute from just ${\displaystyle E_{pk}}$ due to the endomorphism problem.^[7]: 5
The protocol proceeds in 4 phases.
In phase 1, the prover commits to a random elliptic curve ${\displaystyle E_{com}}$ and ${\displaystyle {\textrm {End}}(E_{com})}$ and sends ${\displaystyle E_{com}}$ to the verifier.^[7]: 5
In the second phase, the verifier generates a random isogeny ${\displaystyle \varphi _{chl}:E_{pk}\rightarrow E_{chl}}$ and its corresponding elliptic curve ${\displaystyle E_{chl}}$. Due to the isogeny path problem, it would be hard to compute the isogeny ${\displaystyle \varphi :E_{pk}\rightarrow E_{chl}}$.^[7]: 5
In the third phase, the prover calculates ${\displaystyle {\textrm {End}}(E_{chl})}$ from ${\displaystyle {\textrm {End}}(E_{pk})}$ (i.e. their private key) and ${\displaystyle \varphi _{chl}:E_{pk}\rightarrow E_{chl}}$, since this problem is easy. They then calculate the isogeny ${\displaystyle \varphi _{rsp}:E_{com}\rightarrow E_{chl}}$ that maps from the committed elliptic curve from phase 1 to the challenge elliptic curve from step 2. This can be done if and only if one knows the endomorphism ring of the prover's public key.^[7]: 5
In the fourth phase, the verifier checks whether the isogeny truly maps from the committed elliptic curve to the challenge elliptic curve.^[7]: 5

In order to make the sigma protocol secure, phase 4 has to be amended with a check that ${\displaystyle \varphi _{chl}}$ is not a sub-isogeny of ${\displaystyle \varphi _{rsp}}$ as an attacker could otherwise cheat and provide a forged isogeny without knowing at least part of the endomorphism ring.^[7]: 6

SQIsign fixes the pair ${\displaystyle (E_{0},{\textrm {End}}(E_{0}))}$ and represents the private key as ${\displaystyle \varphi _{sk}:E_{0}\rightarrow E_{pk}}$ and the commitment as ${\displaystyle \varphi _{com}:E_{0}\rightarrow E_{com}}$ although this is computationally equivalent to the process described above.^[7]: 6

The proof of knowledge protocol is transformed to a signature scheme using the Fiat-Shamir transform.^[7]: 5

SQIsign's security relies on the hardness of the endomorphism ring problem, which is currently considered hard.^[8][9]

The authors also provide a rationale for the chosen parameters in the last chapter of the specification.^[1]

While SQIsign makes use of a similar construction, the weaknesses of SIDH do not translate to it.^[1]

There is a security proof for SQIsign.^[10]

There is a reference implementation hosted on GitHub.

The team behind SQIsign improved the original design in their round 2 submission and incorporated improvements from the SQIsign2D-West variant.^[7]

This has improved the signing time by a factor of 20 and the verification time by a factor of 6 while increasing the security level and reducing the signature size by 14%.^[7]: 6

There are a couple of variants based on the original SQIsign:^[11]

• SQIsignHD: New dimensions in cryptography^[12]
• SQIsign2D-West: The fast, the small, and the safer^[13]
• SQIsign2D‑East: A new signature scheme using 2-dimensional isogenies^[3]
• SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies^[14]
• SQIsign2D²: Improvement upon the SQIsign2D design.^[15]