New Digital Signatures Resist Quantum Attacks Using Complex Mathematical Graphs

Scientists are developing new cryptographic methods to withstand the threat posed by quantum computing. Asmaa Cherkaoui (Laboratory of Mathematical Analysis, Algebra and Applications, Hassan II University), Faraz Heravi (University of Texas, Austin), and Delaram Kahrobaei (Queens College, City University of New York) et al. present Spinel, a novel post-quantum digital signature scheme that merges the established security of SPHINCS+ with a recently developed family of algebraic hash functions. This research is significant because it introduces a hashing approach rooted in the complexity of navigating expander graphs over SLn(Fp), a mathematical problem considered resistant even to quantum adversaries. The authors demonstrate both the theoretical and empirical security of this new hash function and its successful integration into a practical and feasible signature scheme, thereby broadening the scope of post-quantum cryptographic tools.

This work addresses the critical need for cryptographic systems that are secure beyond classical computational hardness assumptions, moving towards reliance on mathematically robust foundations.

Spinel integrates the established security of the SPHINCS+ signature framework with a newly designed family of algebraic hash functions, offering a potential strengthening of theoretical security guarantees. The core innovation lies in basing the hash function’s security on the presumed difficulty of navigating expander graphs over SLn(Fp), a mathematical problem believed to be resistant even to quantum adversaries.
Researchers first provided empirical validation of the security of this new hash function, complementing existing theoretical analyses. Extensive testing using the standard NIST Statistical Test Suite across 15 categories demonstrated its strong output randomness and suitability for cryptographic applications.

This hash function was then seamlessly integrated into the SPHINCS+ framework, creating a secure signature scheme with enhanced theoretical underpinnings. Detailed modelling and analysis subsequently determined the security degradation introduced by this integration, guiding the selection of optimal parameters for the scheme.

The team implemented both the novel hash function and the complete Spinel signature scheme, providing detailed empirical results that demonstrate its practical feasibility. Performance benchmarks were conducted to assess computational efficiency and to characterise signature and key lengths across a range of parameter settings.

This approach establishes a foundation for designing algebraic hash-based signature schemes, broadening the toolkit available for post-quantum cryptography and offering a diversification of security assumptions. This research represents a significant step towards building cryptographic systems resilient to the threat of quantum computation.

By combining a well-established hash-based signature framework with a novel, mathematically grounded hash function, Spinel offers a promising path for securing digital communications in the quantum era. The demonstrated feasibility and performance characteristics suggest that this approach could contribute to the development of practical and robust post-quantum cryptographic solutions.

FORS Parameterisation and Key Generation via Merkle Trees

A Forest of Random Subsets, or FORS, construction forms a key component of the signature scheme described in this work. To establish the foundation for secure signatures, the methodology parameterizes FORS with two integers: k, representing the number of trees, and t, defined as 2 raised to the power of a, denoting the number of leaves per tree, where ‘a’ signifies the tree height.

A message digest of m = ka bits is then parsed into k indices, each selecting a specific leaf within its corresponding tree. The secret key comprises kt strings, each n-bits long, derived deterministically from a master secret seed via a pseudorandom function, ensuring stateless key generation. For each tree, the t secret values constitute the leaves of a binary Merkle tree of height a.

The root of each tree is computed using a tweakable hash function, denoted as H, with unique domain separators applied to each node to prevent collisions both across trees and within layers. The public key is generated by compressing the k roots using another invocation of the tweakable hash function, Th, instantiated with distinct tweaks for domain separation.

During signing, FORS outputs the k secret leaf values, along with their corresponding authentication paths, sequences of sibling nodes, for each leaf within its respective tree. Verification involves recomputing each tree root from the revealed leaf and its authentication path, then applying Th to obtain a candidate public key, which is subsequently compared against the known, stored public key. This forest structure ensures that even with shared indices across messages, secret values and authentication paths remain independent, bolstering security against adaptive chosen-message attacks and enabling reductions to the collision resistance of the underlying hash function.

Empirical validation of a Tillich-Zémor hash function within the SPHINCS+ signature scheme

Researchers introduced Spinel, a post-quantum digital signature scheme combining SPHINCS+ with a novel family of algebraic hash functions derived from the Tillich-Zémor paradigm. This hash function’s security is rooted in the presumed hardness of navigating expander graphs over SL_n(F_p) groups. Initial empirical evidence confirms the security of this hash function, complementing existing theoretical analyses and paving the way for a secure signature scheme integration.

The work demonstrates how this hash function integrates within the SPHINCS+ framework, resulting in a secure signature scheme with defined security degradations. The implemented hash function successfully passed all 15 categories of the standard NIST Statistical Test Suite, providing empirical validation of its output randomness and security properties.

This constitutes the first empirical evidence supporting the theoretical analyses of the hash function’s resistance to collision and preimage attacks. Parameter selection within the scheme was informed by a detailed analysis of security degradation, ensuring practical security and efficiency. Researchers then implemented the proposed Spinel signature scheme and conducted empirical evaluations of its performance.

Benchmarking revealed computational efficiency and signature lengths for a range of parameters, demonstrating feasibility in practical applications. The study details the design of an algebraic hash-based signature scheme, expanding the available toolkit for post-quantum cryptography. This approach builds upon the foundations of SPHINCS+ by incorporating a hash function based on well-studied mathematical problems, strengthening the theoretical basis of its security.

Algebraic hashes and security modelling within a SPHINCS+ signature scheme

Spinel, a new stateless hash-based signature scheme, combines the security of SPHINCS+ with a novel family of algebraic hash functions derived from the Tillich-Zemor paradigm. This construction utilises the presumed hardness of navigating expander graphs over SL_n(F_p), a mathematical problem considered difficult even for powerful adversaries.

Empirical evidence supports the security of this new hash function, complementing existing theoretical analyses and enabling its integration into the SPHINCS+ framework. The scheme’s security degradation under signature exposure has been modelled and analysed, informing the selection of appropriate parameters for practical implementation.

A concrete instantiation of Spinel, utilising a 512-bit digest, has been implemented and benchmarked, demonstrating its feasibility for applications where signatures are generated infrequently, such as public-key certificates. The design maintains the established structure of SPHINCS+, preserving formal security guarantees in a post-quantum cryptographic landscape.

A trade-off exists between computational overhead, stemming from matrix operations, and the desired security level. While functionally viable, the current implementation incurs performance and bandwidth costs. Future work could focus on optimisations like signature compression techniques, analogous to those used in SPHINCS+C, or structured Merkle tree variants, to reduce these costs without compromising security. Further exploration of the hash function design space may also yield alternative security assumptions and parameters, broadening the applicability of this approach.