This post is about SQISign, an exciting post-quantum signature scheme based on isogenies. The blog post is intended for people who understand SIDH well, but are not experts at quaternions and Eichler orders. I do not claim to explain (or understand) all the details. I am mainly trying to give an overview of what are the main technical achievements of the SQISign authors.
First some background. Previously there were three isogeny-based signature schemes. A scheme hased on SIDH was given by Yoo, Azarderakhsh, Jalali, Jao and Soukharev. The basic idea is simple: Given a public key the prover wants to prove that they know the secret isogeny . To do this, as in SIDH, commit to an isogeny and the value , where and where and . The verifier sends a single bit, and the prover reveals either and its image on , or .
A variant of this scheme was proposed by Galbraith, Petit and Silva. Their paper also included a completely different (and more complicated) scheme based on quaternions and endomorphism rings. Thirdly, the SeaSign signature by De Feo and Galbraith is based on CSIDH. In all three cases, the basic form is a 3-move identification protocol (Sigma protocol) with single bit challenges. The SeaSign scheme manages to increase the challenge size by using a Merkle tree and some other ideas. But even with SeaSign, it is necessary to repeat the scheme a number of times in parallel to ensure that the probability a forger can guess the challenge is negligble.
The fundamental problem in isogeny signatures has been to create a scheme that has an exponentially large challenge set, so that the scheme doesn’t have to be repeated. SQISign achieves this in an ingenious way, by using the Kohel-Lauter-Petit-Tignol (KLPT) algorithm.
The idea is simple enough at first sight. Again we want to prove knowledge of the secret isogeny . The commitment is a curve such that the prover/signer knows an isogeny . However, instead of a single bit challenge, the challenge is now an isogeny . The signer/prover, knowing the secret key, can compute the isogeny . However it is insecure to publish this isogeny, since it would leak the kernel of and hence reveal the private key. Instead, we’d like to use the KLPT algorithm to create an isogeny which is “independent” of (this is exactly what KLPT does). If there was an efficient way to do this then we’d have a cool signature scheme. See the below figure, taken from the SQISign paper.
There are two big problems with this idea. The first is that we can’t run the KLPT algorithm on . The KLPT algorithm relies on the norm in the quaternion order having a very special form that allows to reduce solving norm equations to solving binary (two variable) quadratic forms (using Cornacchia’s algorithm). The endomorphism ring of is not expected to be so well-behaved. So we can’t run KLPT with . The second problem is that an attacker could easily forge signatures by choosing such that the attacker knows an isogeny . Then, given the challenge , the forger knows an isogeny from to , and could win.
The SQISign paper solves both problems. Now would be a good time to mention that the authors of SQISign are an isogeny “dream team” of De Feo, Kohel, Leroux, Petit and Wesolowski. A deep understanding of KLPT is necessary to create the scheme, and the paper is a very impressive work.
We start with the special curve of j-invariant 1728. It has a “nice” endomorphism ring . The KLPT algorithm exploits the fact that isogenies from correspond to left- ideals in . Equivalent ideals correspond to isogenies with the same image curve.
The most important thing a reader of this paper has to understand is that is the only curve we can work with, in terms of ideals and endomorphisms. So every computation has to be pulled back to in some way. This requires a whole bunch of sneaky constructions, starting with the private key. The private key is not one isogeny , but two. Precisely, is an isogeny of “small” prime order corresponding to an ideal . That’s nice in quaternion-land, but we can’t compute the public key, so we need to compute an equivalent ideal whose norm is a power of small primes, and thus compute the corresponding isogeny . The public key of a signer is and the private key is both and .
The commitment is a “random” isogeny of degree coprime to the degrees of both and . The prover can compute a left -ideal corresponding to .
The challenge (which will be created using the Fiat-Shamir transform in the signature scheme) is the isogeny . This isogeny is fully known to the prover, for example its kernel is known. There is an exponentially large set of possible challenges, which is what makes the signature scheme interesting. The degree of is co-prime to everything else. The prover needs to compute an ideal corresponding to , and to do this we pull back the kernel of under , compute the ideal and then push forward (via Lemma 3 of the paper). This results in , which is a left--ideal.
Now comes the really subtle bit. We have the three isogenies , and and three ideals . The isogeny corresponds to . Somehow we need to compute an equivalent ideal, but this is a left--ideal, which is no good to us. The trick is to pull back under , which we can do since the degree of is coprime to the norm of . (This is the part where it is necessary to have two different private keys.) This ideal corresponds to an isogeny for some curve . Then we would run KLPT on this ideal to get a random ideal of suitable smooth norm, then push forward via or and we’re done, right? Wrong!
We have two different isogenies , and the pushforward of one of them to is an isogeny to . But the problem is: the pushforward of the other does not necessarily have an image curve isomorphic to , which is what we need. How to enforce this requirement? This is where the Eichler orders come in. Eichler orders are intersections of two maximal orders in a quaternion algebra. The Eichler order of interest in this paper is . (This is the reason why the degree of is taken as small as possible.) The key result is Corollary 1 of the paper, which restricts the equivalence of ideals to multiplication by elements in the Eichler order. It is necessary to develop a variant of KLPT to ensure this restriction is possible.
The paper contains several optimisations and also some new computational assumptions. One assumption is that there is no meet-in-the-middle attack on , which seems plausible (though surprising at first sight). Other assumptions (see Section 7.3) are about the randomness of the outputs of the KLPT algorithm in this setting.
What about the attack I mentioned earlier (the “second problem”) choosing by computing an isogeny . This attack is prevented by imposing a condition on the degree of . The attacker can’t run the same algorithm as the signer, since they have no way to pull back isogenies to and run KLPT.
To conclude, the exciting thing about SQISign is the exponentially large set of challenges, which means the signing process does not need to be repeated. This is why the signatures are very short compared with other post-quantum signatures. I have no opinion on the practicality of the scheme.
— Steven Galbraith