7 A Short, Incomplete, and Poorly Written Explanation of SQISign (2026-09-17)

I was supposed to do a passion presentation to some friends tonight. I decided to poorly explain SQISign (the presentations were for a nontechnical audience and had to fit in five minutes). Something came up, I can’t go. What follows is an adaptation of the incomplete slide deck I had prepared.

7.1 Background

7.1.1 “Basic” Modern Algebra

• Group: set equipped with a binary operation that acts like addition (associative, commutative, has inverse, etc.)
• Ring: set equipped with multiplication and addition that act just like over the integers $\mathbb{Z}$ except multiplication doesn’t need to commute ($ab$ does not need to equal $ba$)
• Ring homomorphism: function $f : R \mapsto S$ for two rings $R, S$ such that $f(a + b) = f(a) + f(b)$, $f(ab) = f(a)f(b)$, and $f(1_R) = 1_S$ for all $a, b \in R$
• Field: ring where multiplication is commutative and where every nonzero element has a multiplicative inverse such that $aa^{-1}=a^{-1}a=1_K$ for all $a\neq 0_K$
• Finite field: field with finitely many elements (number of elements must be a power of a prime)
• Algebraic closure: $\bar{K}$ for field $K$ such that $\bar{K}$ is a field, every element of $K$ is in $\bar{K}$, and every polynomial with coefficients in $K$ has all of its zeroes in $\bar{K}$
• Characteristic of a field: number of times you can add a nonzero element to itself until you get $0_F$, always prime, and generally set to zero if there is no such number
• Central simple algebra: a ring $R$ associated with a commutative ring $K$ equipped with a ring homomorphism from $K$ into the largest commutative subring of $R$. That subring must be $K$ itself (so it’s central) and every homomorphism $h : R \mapsto S$ either maps every member of $R$ to a unique member of $S$ or maps them all to a single member of $S$ (so it’s simple)

7.1.2 “Basic” Linear Algebra

• Quaternion algebra: a central simple algebra $B$ defined over $\mathbb{Q}$ (the rational numbers, the set of fractions with integer numerators and denominators) with elements $1, i, j, k$ satisfying $ii=a$, $jj=b$, $ij=k$, and $ji=-k$ for some integers $a, b$. The conjugate $\bar{\alpha}$ of $\alpha \in B = a + bi + cj + dk$ is given by $\bar{\alpha} = a - bi - cj - dk$, and the reduced norm $\text{nrd}(\alpha)$ is the product $\alpha\bar{\alpha}$
• Module: like a vector space except scalars can come from any ring instead of having to be a field
• Lattice: a subset $L$ of $B$ where, for some four elements $\{a, b, c, d\} \subseteq L$, all elements of $B$ are of the form $ta + xb + yc + zd$ for $t, x, y, z \in \mathbb{Z}$
• Order: lattice $\mathcal{O} \subseteq B$ that is also a subring of $B$
• Maximal order: order $\mathcal{O}_M$ such that there is no other order $\mathcal{O}_L \neq \mathcal{O}_M$ that fully contains $\mathcal{O}_M$
• Integral left $\mathcal{O}$-ideal: lattice $I$ contained in $\mathcal{O}$ for which $io \in I$ for all $i \in I$, $o \in \mathcal{O}$. We’ll simply call these $\mathcal{O}$-ideals from now on
• $\mathcal{O}$-ideal class: set $\text{cls}(I)$ of ideals for which, for any two $I, J \in \text{cls}(I)$, there exists $\alpha \in B$ such that all members of $I$ are equal to a member of $J$ multiplied by $\alpha$

7.1.3 “Basic” Geometry

• Elliptic curve over a field $K$: set of points $E/K$ in $\bar{K}^2$ where $E/K = \{P\in \bar{K}^2 : P_y^2 = P_x^3 + aP_x + b\} \cup \{P_{\infty}\}$, where $P_{\infty}$ is the point at infinity (makes the math work) and $a, b \in K$ are fixed for all points in the curve. We exclude any such curve where there are singular points, i.e. points satisfying $2P_y = -3P_x^2 - a = 0_K$
• Elliptic curves form groups! You can take two points $P_1, P_2 \in E/K$ and “add” them to get a third point $P_1 + P_2 \in E/K$. The identity point is $P_{\infty}$, and every point $P$ has an associated point $-P$ such that $P + (-P) = P_{\infty}$
• Morphism: function $\phi : E_1/K \mapsto E_2/K$ such that $\phi(P^1_{\infty})=P^2_{\infty}$ and $\phi(P)_x, \phi(P)_y$ are each of the form $n[P]d[P]^{-1}$ where $n, d$ are polynomials with coefficients in $K$. All morphisms have the property that $\phi(P + Q) = \phi(P) + \phi(Q)$. Morphisms form a group $\text{Hom}(E_1/K,E_2/K)$ under addition: $\phi + \psi$ is unique and given by $(\phi + \psi)(P) = \phi(P) + \psi(P)$
• Isogeny: morphism that is not the unique constant morphism $\phi_k(E_1/K)=P^2_{\infty}$
• Endomorphism: morphism in $\text{Hom}(E/K, E/K)$, or equivalently in $\text{End}(E/K)$. $\text{End}(E/K)$ forms a group with the same group law as all morphisms
• Isomorphism: isogeny with an inverse that is also an isogeny. We define the isomorphism class of an elliptic curve $E/K$ to be the set of elliptic curves for which there exists an isomorphism mapping their points to each other
• Supersingular elliptic curve: curve $E/K$ for which the number of points (aside from $P_{\infty}$) that are also in $K^2$ is a finite multiple of the characteristic of $K$, that is, $\# E(K) \equiv 1 \pmod{\text{char}(K)}$
• Deuring correspondence, part one: $\text{End}(E/K)$, for supersingular $E/K$, forms a maximal order in $B$, the quaternion algebra given by the set of pairs $(\psi, q)$ of endomorphisms of $E/K$ and rational numbers.
• Deuring correspondence, part two: there is a unique bijection (function mapping every element of a set to a unique element of another set, covering the entire other set) mapping ideal classes $\text{cls}(I)$ to isomorphism classes of an elliptic curve $E/K$. We denote by $\text{cls}(I)\star E/K$ a representative of the isomorphism class mapped to by $\text{cls}(I)$. We next denote by $I\star E/K$ the isogeny associated with the ideal $I$
• Finding isogenies between elliptic curves over a field $K$ is very hard computationally if at least one curve is selected randomly! Finding $\text{cls}(I)\star E/K$ from $\text{cls}(I)$ is much, much easier (and likewise with $I\star E/K$ from $I$)

7.1.4 “Basic” Cryptography

• Interactive proof: series of communications between a Prover and a Verifier where the Prover seeks to probabilistically convince the Verifier of something
• Sigma protocol: three-round interactive proof where the Prover demonstrates knowledge of a secret without revealing that secret. The Prover derives a committment from the secret and sends it to the Verifier, who sends back a random challenge. The Prover combines the committment and challenge into a response and returns it to the Verifier, completing the protocol
• Digital signature algorithm: cryptographic algorithm whereby a Signer takes a Message and produces a Signature that (theoretically, probabilistically) demonstrates to the Verifier that the Signer was the one who produced the Signature
• Fiat-Shamir transformation: due to Amos Fiat and Adi Shamir, take the sigma protocol and replace the challenge with the hash of a message and a nonce. This produces a digital signature algorithm from a sigma protocol

7.2 SQISign

7.2.1 Parameters

• $p$ is a prime of the form $c2^f - 1$ for $f > 1$, odd $c$
• $\mathbb{F}_p$ is the finite field (up to isomorphism) with $p$ elements
• $\mathbb{F}_{p^2}$ is the finite field (up to isomorphism) with $p^2$ elements given by the set of polynomials with coefficients in $\mathbb{F}_p$ where we consider two members $a, b$ equal (or congruent) if there exists a polynomial $q \in \mathbb{F}_p[X]$ such that $a = b + q(X^2 + 1)$
• $\text{i} \equiv -1$ in $\mathbb{F}_p$
• $E_0/\mathbb{F}_{p^2}$ is the supersingular elliptic curve given by the zeros in $\bar{\mathbb{F}}_{p^2}$ of $y^2 - x^3 - x$
• $B_{p,\infty}$ is the quaternion algebra over $\mathbb{Q}$ with $ii=-1$, $jj=-p$, $k=ij=-ji$
• $1, i, j, k$ is the standard basis of $B_{p,\infty}$ over $\mathbb{Q}$
• $\mathcal{O}_0$ is the maximal order of $B_{p,\infty}$ generated by $\left(1, i, \frac{i+j}{2}, \frac{1+k}{2}\right)$
• $\lambda \in \mathbb{Z}^+$ is an arbitrary “security parameter”

7.2.2 Key Generation

• A digital signature algorithm almost always relies on a Signing Key and a Verifying Key; the Signing Key can be used by the Signer to produce Signatures and the Verifying Key can be used by the Verifier to check that Signatures were produced by the Signer (or any holder of the Signing Key)
• An SQISign Signing Key is an $\mathcal{O}_0$-ideal $I_{\text{sk}}$ with odd prime $\text{nrd}(I_{\text{sk}})$ such that $\text{cls}(I_{\text{sk}})$ is uniformly random with a corresponding secret isogeny $\phi_{\text{sk}} = I_{\text{sk}} \star E_0$
• The Verifying Key is an elliptic curve (up to isomorphism) $E_{\text{pk}}/\mathbb{F}_{p^2} = \text{cls}(I_{\text{sk}}) \star E_0$ together with two points $P_{\text{pk}}, Q_{\text{pk}} \in E_{\text{pk}}/\mathbb{F}_{p^2}$ for which any finite sum of those two points forms a cyclic group with $2^{\lambda}$

Comments