SQIsign

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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 E_1 and E_2 can be connected with an isogeny \varphi , written as \varphi : E_1 \rightarrow E_2 , which maps all elements of E_1 onto 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 \varphi : E_1 \rightarrow E_2 given E_1 and E_2 ", which is believed to be hard. An endomorphism of an elliptic curve E is an isogeny that maps E onto itself, i.e. \varphi : E \rightarrow E . The set of all endomophisms of an elliptic curve is known as its endomorphism ring, written as \textrm{End}(E) . The endomorphism problem can be formulated as "given E , find \textrm{End}(E) ". Even computing a non-trivial part of \textrm{End}(E) is known to be as hard as computing the full \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 E_1 and E_2 , one can compute one of (\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. The sigma protocol works as follows. The prover has E_{pk} and \textrm{End}(E_{pk}) and publishes E_{pk} as their public key while keeping \textrm{End}(E_{pk}) private. The prover then tries to convince the verifier that they know \textrm{End}(E_{pk}) , which is hard to compute from just E_{pk} due to the endomorphism problem. The protocol proceeds in 4 phases. In phase 1, the prover commits to a random elliptic curve E_{com} and \textrm{End}(E_{com}) and sends E_{com} to the verifier. In the second phase, the verifier generates a random isogeny \varphi_{chl} : E_{pk} \rightarrow E_{chl} and its corresponding elliptic curve E_{chl} . Due to the isogeny path problem, it would be hard to compute the isogeny \varphi : E_{pk} \rightarrow E_{chl} . In the third phase, the prover calculates \textrm{End}(E_{chl}) from \textrm{End}(E_{pk}) (i.e. their private key) and \varphi_{chl} : E_{pk} \rightarrow E_{chl} , since this problem is easy. They then calculate the isogeny \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. 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 \varphi_{chl} is not a sub-isogeny of \varphi_{rsp} as an attacker could otherwise cheat and provide a forged isogeny without knowing at least part of the endomorphism ring. SQIsign fixes the pair (E_0, \textrm{End}(E_0)) and represents the private key as \varphi_{sk} : E_0 \rightarrow E_{pk} and the commitment as \varphi_{com} : E_0 \rightarrow E_{com} 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 reference implementation 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 SQIsign2D 2 : Improvement upon the SQIsign2D design.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1356037265 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

13 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.