🔢 mathematics

Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing

This paper introduces Spinel, a post-quantum digital signature scheme that integrates a new family of algebraic hash functions based on the hardness of navigating expander graphs over $\mathrm{SL}_n(\mathbb{F}_p)$ into the SPHINCS+ framework.

Original authors: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

Published 2026-02-12

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Upgrading the "Digital Wax Seal"

Imagine you are sending a super-secret letter through the mail. To make sure no one has tampered with it, you use a digital wax seal (a digital signature).

Currently, most of these seals are made using math problems that are very hard for today’s computers to solve. However, scientists are building Quantum Computers—super-powered machines that act like "math wizards." These wizards can crack our current digital seals almost instantly.

To protect our secrets, we need a new kind of seal. This paper introduces Spinel, a new, ultra-tough digital seal designed to withstand even the most powerful math wizards.

1. The Foundation: The "Lego Set" (SPHINCS+)

The researchers didn't reinvent the entire wheel. Instead, they used a very famous, highly trusted blueprint for a digital seal called SPHINCS+.

Think of SPHINCS+ as a massive, complex Lego castle. This castle is incredibly strong because it’s built out of many smaller, interlocking parts (like tiny towers and walls). The security of this castle depends entirely on the bricks used to build it.

Currently, those bricks are made of "standard" materials (like SHA-256). These materials are good, but their strength is mostly based on "we haven't found a way to break them yet." They are like standard clay bricks—reliable, but we don't have a deep mathematical proof that they can't be crushed by a giant hammer.

2. The Innovation: The "Diamond Bricks" (SLn(Fp) Hashing)

The authors of this paper decided to swap out those clay bricks for something much more exotic: Diamond Bricks.

Instead of using standard math, they use a concept called "Group Theory" (specifically, something called $SL_n(F_p)$ ).

The Analogy: The Infinite Maze
Imagine a giant, multidimensional maze. To create a "hash" (the fingerprint of your message), you take your message and use it as a set of instructions to walk through this maze.

The instructions might say: "Turn left, then take three steps forward, then turn right."
By the time you finish the walk, you end up at a specific spot in the maze. That spot is your "seal."

The "Diamond Bricks" here are the rules of this maze. The researchers chose a maze so complex and so "well-mixed" that even if a Quantum Wizard tried to work backward from your final position to find your original instructions, they would get lost in the infinite turns and dead ends.

3. Testing the Strength: The "Stress Test"

Before they claimed their new seal was ready, they put it through two major tests:

The Randomness Test (The "Chaos" Test): They used a standard suite of tests (NIST) to make sure the "spots" in the maze were truly random. If the spots followed a predictable pattern, a wizard could guess them. The results showed that the Spinel maze is beautifully chaotic—just like it should be.
The Exposure Test (The "Wear and Tear" Test): In digital signatures, every time you use a key, you leak a tiny bit of information (like a seal getting slightly thinner every time it's pressed). The researchers mathematically modeled how much "wear and tear" the Spinel seal can take before it becomes unsafe to use.

4. The Trade-off: The "Heavyweight Champion"

Nothing in life is free. Because these "Diamond Bricks" are much more complex than "Clay Bricks," the Spinel seal is a bit heavier and slower to make.

The Speed: It takes more "brainpower" (computer cycles) to calculate the walk through the maze than it does to use standard math.
The Size: The signature (the seal itself) is a bit larger.

The Verdict: Spinel isn't meant to be used for every tiny text message you send. It is designed for the "Heavyweight" stuff—like official government documents or high-security bank certificates—where you want the absolute strongest, most mathematically proven protection possible, even if it takes a few extra milliseconds to process.

Summary

Spinel takes a world-class security architecture (SPHINCS+) and upgrades its engine with a new, mathematically "hard" fuel (Algebraic Hashing). It’s a move from "we hope this works" to "we have a mathematical fortress that even quantum computers will struggle to climb."

Technical Summary: Spinel – A Post-Quantum Signature Scheme Based on $SL_n(\mathbb{F}_p)$ Hashing

1. Problem Statement

The transition to post-quantum cryptography (PQC) is driven by the threat large-scale quantum computers pose to classical digital signatures (e.g., RSA, ECDSA). While hash-based signature schemes like SPHINCS+ are leading candidates for quantum resistance, their security relies on the properties of cryptographic hash functions (like SHA-256 or SHAKE-256). The security of these functions is primarily heuristic, meaning it is based on the lack of successful cryptanalysis rather than a reduction to a well-defined, hard mathematical problem.

The authors identify a gap in the current PQC landscape: the lack of hash-based signature schemes that utilize algebraic hash functions—functions whose security is rooted in proven mathematical hardness assumptions (such as navigating expander graphs)—to provide a more robust theoretical foundation.

2. Methodology

The authors propose Spinel, a signature scheme that integrates a new family of algebraic hash functions into the existing, standardized SPHINCS+ framework.

The Algebraic Hash Function: Spinel utilizes a hash function derived from the Tillich–Zémor paradigm. It operates on the special linear group $SL_4(\mathbb{F}_p)$ . The hash is computed by interpreting the input as a sequence of symbols that drive a non-backtracking random walk on the Cayley graph of the group. The final group element (a $4 \times 4$ matrix) serves as the hash digest.
Integration with SPHINCS+: Spinel is a "structurally faithful" variant of SPHINCS+. It retains the entire architecture of SPHINCS+, including:
- WOTS+ (Winternitz One-Time Signatures) for leaf authentication.
- FORS (Forest of Random Subsets) for few-time signatures.
- Hypertree construction for stateless operation.
- Tweakable Hashing: Every hash call is domain-separated using a unique 256-bit address (ADRS) to prevent multi-target attacks.
Parameterization: The authors fix the dimension $n=4$ and the prime $p = 2^{31}-1$ . They use a 512-bit digest (achieved by serializing the $4 \times 4$ matrix with 32-bit entries) to ensure a 256-bit collision resistance level.

3. Key Contributions

New Signature Scheme (Spinel): The first instantiation of a SPHINCS+-like scheme using group-theoretic, algebraic hash functions.
Empirical Validation of the Hash: While the hash function had theoretical security proofs, the authors provided the first empirical evidence of its randomness by passing all 15 categories of the NIST Statistical Test Suite (STS).
Security Degradation Modeling: The authors modeled how the security of the FORS component degrades as more signatures are issued under a single key (signature exposure), providing a mathematical framework for selecting parameters based on an "operational signature budget."
Implementation and Benchmarking: A complete C implementation of the scheme and the hash function.

4. Results

Statistical Randomness: The Spinel hash function passed the NIST STS tests, demonstrating that the $SL_4(\mathbb{F}_p)$ walk produces outputs indistinguishable from a random source.
Performance Trade-offs:
- Computational Cost: Spinel is computationally heavier than SHAKE-256-based SPHINCS+. Signing is significantly slower than verification (by roughly three orders of magnitude), making it most suitable for applications like public-key certificates where signing is infrequent.
- Signature Size: Spinel signatures are larger than standard SPHINCS+ due to the 512-bit digest requirement and the overhead of matrix operations.
- Parameter Sensitivity: The authors demonstrated that increasing the number of FORS trees ( $k$ ) or the tree height ( $b$ ) allows for better resistance to signature exposure but affects the speed/size balance.
Feasibility: Despite the higher overhead, the results show the scheme is functionally viable and practical for high-security, low-frequency signing environments.

5. Significance

Spinel represents a significant step toward diversifying the post-quantum toolkit. By moving away from purely heuristic hash functions toward those based on the hardness of navigating expander graphs in $SL_n(\mathbb{F}_p)$ , the authors provide a path toward signature schemes with stronger, more mathematically grounded security guarantees. This work lays the foundation for a new class of "algebraic hash-based signatures" that could serve as a critical fallback or enhancement in the post-quantum era.