The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

This paper presents a generalized framework for the SQIsign signature scheme by incorporating level structures into the isogeny challenge, which leads to a new explicit Deuring correspondence for supersingular elliptic curves and solutions to constrained norm equations.

The Gist

Imagine you are trying to prove you own a secret treasure map without ever showing the map itself. In the world of cryptography, this is called a digital signature. You want to sign a message to prove it's really from you, but you don't want to reveal your private key.

For a long time, the best way to do this in a "post-quantum" world (where future quantum computers might break current codes) was a method called SQIsign. It's like a high-stakes game of "Find the Path" on a magical map made of elliptic curves (weird, donut-shaped mathematical shapes).

The paper you provided introduces a new, upgraded version of this game called SQInstructor. Here is the breakdown of what they did, using simple analogies.

1. The Old Game: SQIsign (The "Vanishing Act")

In the original SQIsign game, the "Verifier" (the person checking your signature) gives you a challenge: "Find a path from Point A to Point B that completely destroys a specific landmark on the map."

• The Challenge: The landmark is a specific point on the curve.
• The Response: You must draw a path (an isogeny) that makes that point disappear (turn into zero).
• The Problem: While this works, it's like trying to solve a maze by only being allowed to walk in straight lines. It's efficient, but it's hard to prove mathematically that you can't cheat, and the "signing" process is slow and complicated.

2. The New Game: SQInstructor (The "Relocation Mission")

The authors of this paper realized: "Why do we have to destroy the landmark? Why not just move it?"

They introduced the concept of Level Structures. Think of a level structure not as a single point, but as a special arrangement of furniture in a room.

• The Old Way: "Destroy the chair."
• The New Way (SQInstructor): "Take the chair and move it to a specific new spot in the room."

In the SQInstructor game:

1. The Setup: You have a starting room (your public key) with a specific furniture arrangement (the level structure).
2. The Challenge: The Verifier says, "I want you to move that furniture arrangement to a different room (the challenge curve) and arrange it exactly like this new pattern."
3. The Response: You draw a path that carries the furniture from the old room to the new room, ensuring the furniture ends up in the exact configuration requested.

3. Why is this a big deal? (The "Translator" Analogy)

The magic of this system relies on something called the Deuring Correspondence. Imagine you have two languages:

• Language A (Curves): Hard to speak, slow to translate, but very secure.
• Language B (Quaternions): Easy to speak, fast to translate, but you can't write the final answer in this language.

The Deuring Correspondence is a universal translator.

• In the old game, the translator was a bit clunky. It could get you from A to B, but it struggled with the "furniture arrangement" (level structures).
• In this paper, the authors built a super-translator. They figured out exactly how to translate the "furniture arrangement" rules from the hard language (Curves) into the easy language (Quaternions), solve the puzzle there, and translate the solution back.

They showed that you can now solve these "move the furniture" puzzles efficiently, even when the furniture arrangement is very complex.

4. Two Ways to Play (1D vs. 2D)

The paper explores two ways to execute this new game:

• The "One-Dimensional" Way (The Classic Route):

  • Imagine walking through a maze one step at a time.
  • This is slower but allows for very advanced tricks later (like creating "ring signatures," where a group signs a message but no one knows who specifically did it).
  • The authors wrote new algorithms to make this step-by-step walking much faster.

• The "Two-Dimensional" Way (The High-Speed Route):

  • Imagine taking a helicopter over the maze instead of walking.
  • This is much faster and is the method used by the current NIST standard candidate (SQIsign).
  • The authors adapted their new "furniture moving" rules to work with this helicopter method. They proved it's just as secure as the original, but now it can handle these more complex "move the furniture" challenges.

5. The Result: A Better Signature

By using this new framework, the authors created SQInstructor.

• It's Secure: It relies on the same hard math problems as the original, so quantum computers still can't break it.
• It's Flexible: It allows for different types of "furniture arrangements" (level structures), which opens the door to new types of cryptographic tools.
• It's Fast: Their tests show it performs almost exactly as well as the current state-of-the-art SQIsign, but with a more robust mathematical foundation.

Summary

Think of SQIsign as a master locksmith who can pick a lock by breaking a specific pin.
SQInstructor is a master locksmith who can pick the same lock by rearranging the pins to a specific pattern.

The paper proves that rearranging the pins is just as secure, perhaps even more versatile, and they figured out the exact mathematical instructions (algorithms) to do it quickly. This gives cryptographers a new, powerful tool to build future-proof digital signatures.

Technical Summary

Here is a detailed technical summary of the paper "The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures."

1. Problem Statement

The paper addresses the need to generalize the SQIsign signature scheme, a leading candidate for post-quantum cryptography based on supersingular isogenies. While SQIsign is highly compact and efficient, its security proofs and construction rely heavily on specific constraints regarding the Deuring correspondence (the equivalence between supersingular elliptic curves and maximal orders in quaternion algebras).

The authors identify that the standard SQIsign protocol can be reinterpreted through the lens of level structures (bases of torsion subgroups). In the original protocol, the response is an isogeny that annihilates a specific torsion point (kernel). The authors propose a broader framework where the response is an isogeny that maps one level structure to another. This generalization aims to:

• Provide a unified theoretical framework for isogeny-based signatures.
• Enable new instantiations using different types of level structures (e.g., Borel, Split Cartan, Scalar).
• Facilitate the construction of advanced cryptographic primitives (like ring signatures and chameleon hashes) that are difficult to instantiate with standard SQIsign.
• Solve new constrained norm equations in quaternion algebras required for these generalizations.

2. Methodology

The paper develops a comprehensive framework called SQInstructor, which generalizes the Deuring correspondence to include elliptic curves equipped with level structures.

A. Generalized Deuring Correspondence

The authors extend the classical Deuring correspondence to supersingular elliptic curves with a $\Gamma$-level structure (where $\Gamma$ is a subgroup of $GL_2(\mathbb{Z}/N\mathbb{Z})$).

• Mathematical Foundation: They define a subring of the endomorphism ring, $\mathcal{O}(E, S)$, consisting of endomorphisms that preserve the level structure $S$.
• Ideal Correspondence: They prove that isogenies mapping one level structure to another correspond to locally principal left ideals in the suborder $\mathcal{O}(E, S)$.
• Explicit Construction: They provide an explicit algorithm (Algorithm 1: InStructIdeal) to compute the matrix representation of an isogeny on torsion points, allowing the translation of ideal operations into isogeny operations even for large, non-smooth levels.

B. The SQInstructor Protocol

They define a generic Sigma-protocol (identification scheme) based on this correspondence:

1. Key Generation: The secret key is a left ideal $I_{sk}$ in $\mathcal{O}(E_0)$, defining a public curve $E_{pk}$ with a chosen level structure $S_{pk}$.
2. Commitment: The prover sends a curve $E_{com}$ derived from a random ideal.
3. Challenge: The verifier sends a random level structure $S_{com}$ on $E_{com}$.
4. Response: The prover computes an isogeny $\phi_{rsp}$ such that $\phi_{rsp}(S_{pk}) = S_{com}$.
5. Verification: The verifier checks that the isogeny maps the structures correctly.

C. Instantiations

The paper explores two specific instantiations of this framework:

1. 1-Dimensional (1D) Instantiation: Uses the KLPT algorithm (Kohel-Lauter-Petit-Tignol) adapted for level structures. This involves solving constrained norm equations in the quaternion algebra $B_{p,\infty}$ to find ideals of smooth norm that respect the level structure constraints.
2. 2-Dimensional (2D) Instantiation: Uses higher-dimensional isogenies (specifically $(2,2)$-isogenies) to compute the response. This approach bypasses the need for KLPT and offers performance comparable to the state-of-the-art NIST candidate SQIsign.

3. Key Contributions

• Generalized Deuring Correspondence: The authors rigorously extend the Deuring correspondence to supersingular curves with arbitrary level structures (Borel, Split Cartan, Scalar), proving the bijection between isogenies of level structures and locally principal ideals in specific suborders.
• Constrained Norm Equations: They develop new algorithms (variants of SigningKLPT, specifically ScalarSigningKLPT and BorelSigningKLPT) to solve norm equations within suborders defined by level structures. This is a significant algorithmic contribution for 1D implementations.
• Security Analysis:
  • Soundness: Proven to be 2-special sound, relying on the hardness of the Endomorphism Ring Problem (finding a non-scalar endomorphism).
  • Zero-Knowledge: Analyzed under the Isogeny Oracle model (and hint-assisted models), showing that the protocol is zero-knowledge even with the added complexity of level structures.
  • EUF-CMA: The signature scheme is proven secure in the Random Oracle Model.
• Practical Implementations:
  • A proof-of-concept implementation of the 1D variant using Borel structures.
  • A full implementation of the 2D variant, benchmarked against the reference SQIsign code.

4. Results

• Performance (2D Variant): The 2D instantiation of SQInstructor achieves performance comparable to SQIsign.
  • Key Generation/Signing: Slightly slower than SQIsign due to the overhead of handling level structure matrices and the slightly longer isogeny chains required for the $(2,2)$-isogeny representation.
  • Signature Size: Slightly larger (e.g., ~272 bytes vs. 224 bytes for NIST III security) due to the inclusion of the challenge matrix and auxiliary curve data.
  • Verification: Slightly slower but within the same order of magnitude.
• 1D Variant: The 1D variant produces larger signatures and is less efficient than the 2D version but is crucial for applications requiring simulatability (e.g., ring signatures and chameleon hashes), which are difficult to achieve with 2D isogenies.
• Parameter Selection: The paper provides concrete parameter sets for NIST security levels (I, III, V), determining the optimal level $N$ based on the torsion available in the starting curve $E_0$.

5. Significance

• Theoretical Unification: SQInstructor unifies various isogeny-based protocols under a single "level structure" paradigm, clarifying the relationship between SQIsign, SIDH-like assumptions, and other primitives.
• Enabling Advanced Primitives: By providing a robust 1D instantiation with simulatable transcripts, the paper opens the door to constructing ring signatures and chameleon hashes in the isogeny setting, which were previously theoretical or inefficient.
• Algorithmic Advancement: The development of algorithms to solve norm equations in suborders (specifically for Borel and Scalar structures) advances the state of the art in quaternion algebra computations, which are central to isogeny cryptography.
• Future-Proofing: The framework demonstrates that the Deuring correspondence is flexible enough to accommodate various structural constraints, suggesting that isogeny-based cryptography can evolve beyond the specific constraints of the original SQIsign design while maintaining security and efficiency.

In summary, SQInstructor is a significant step forward in isogeny-based cryptography, offering a flexible framework that maintains the high efficiency of modern 2D isogeny techniques while recovering the simulatability of 1D techniques for advanced cryptographic applications.