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 it's 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==