SQIsign


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 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.
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.
These times have been improved with new variations like SQIsign-east.
The name stands for "Short Quaternion and Isogeny Signature" as it makes use of isogenies and quaternions.

Inner workings

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.
SQIsign primarily operates on elliptic curves. Two elliptic curves and can be connected with an isogeny, written as, which maps all elements of onto.
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 given and ", which is believed to be hard.
An endomorphism of an elliptic curve is an isogeny that maps onto itself, i.e..
The set of all endomophisms of an elliptic curve is known as it's endomorphism ring, written as.
The endomorphism problem can be formulated as "given, find ". Even computing a non-trivial part of is known to be as hard as computing the full.
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 and, one can compute one of given the other two in polynomial time, i.e. the problem is easy.
The sigma protocol works as follows. The prover has and and publishes as their public key while keeping private. The prover then tries to convince the verifier that they know, which is hard to compute from just due to the endomorphism problem.

The protocol proceeds in 4 phases.

In phase 1, the prover commits to a random elliptic curve and and sends to the verifier.

In the second phase, the verifier generates a random isogeny and its corresponding elliptic curve. Due to the isogeny path problem, it would be hard to compute the isogeny.

In the third phase, the prover calculates from and, since this problem is easy. They then calculate the isogeny 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.

In the fourth phase, the verifier checks whether the isogeny truly maps from the committed elliptic curve to the challenge elliptic curve.
In order to make the sigma protocol secure, phase 4 has to be amended with a check that is not a sub-isogeny of as an attacker could otherwise cheat and provide a forged isogeny without knowing at least part of the endomorphism ring.
SQIsign fixes the pair and represents the private key as and the commitment as although this is computationally equivalent to the process described above.
The proof of knowledge protocol is transformed to a signature scheme using the Fiat-Shamir transform.

Security

SQIsign's security relies on the hardness of the endomorphism ring problem, which is currently considered hard.
The authors also provide a rationale for the chosen parameters in the last chapter of the specification.
While SQIsign makes use of a similar construction, the weaknesses of SIDH do not translate to it.
There is a security proof for SQIsign.

Implementations

There is a hosted on GitHub.

SQIsign 2.0

The team behind SQIsign improved the original design in their round 2 submission and incorporated improvements from the SQIsign2D-West variant.
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%.

Variants

There are a couple of variants based on the original SQIsign:
  • SQIsignHD: New dimensions in cryptography
  • SQIsign2D-West: The fast, the small, and the safer
  • SQIsign2D‑East: A new signature scheme using 2-dimensional isogenies
  • SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies
  • SQIsign2D2: Improvement upon the SQIsign2D design.