New Encryption Method Withstands Attacks from Both Computers and Artificial Intelligence

Researchers are increasingly focused on developing cryptographic systems resilient to attacks from quantum computers. Asmaa Cherkaoui, Ramón Flores, Delaram Kahrobaei, et al. present Eidolon, a novel post-quantum signature scheme grounded in the well-studied, yet challenging, NP-complete k-colourability problem. Their work significantly advances the field by generalising existing protocols and compressing signature sizes, while crucially employing a new method of generating difficult instances via ‘quiet’ colourings. The authors demonstrate, through empirical analysis against both classical solvers and a custom graph neural network, that these instances can withstand modern cryptanalysis for graphs with at least 60 nodes, thereby re-establishing combinatorial hardness as a viable basis for future cryptographic systems.

K-colourability and compact signatures for post-quantum cryptography offer promising security advantages

Researchers have developed Eidolon, a new post-quantum signature scheme based on the computationally challenging k-colourability problem. This work addresses a critical need for cryptographic systems resistant to attacks from future quantum computers, moving beyond reliance on traditional methods vulnerable to these emerging technologies.

The scheme leverages a generalisation of established zero-knowledge protocols and employs Merkle-tree commitments to significantly compress signature sizes from O(tn) to O(t log n), where ‘ t ‘ represents the number of computational rounds and ‘n is the number of vertices in the graph. Central to Eidolon’s design is the generation of hard instances through “quiet” colourings embedded within random graphs, aiming to preserve the statistical characteristics of genuinely random structures.

This approach seeks to avoid the pitfalls of many NP-hard problems where specifically crafted instances can be quickly solved by existing algorithms. A comprehensive empirical analysis was conducted, subjecting the scheme to both classical solvers, such as ILP and DSatur, and a custom-built graph neural network (GNN) attacker.

Experiments reveal a critical threshold in resisting cryptanalysis: for graph sizes of n ≥ 60, neither the classical solvers nor the GNN were able to successfully recover the secret coloring. This demonstrates that carefully engineered k-coloring instances can effectively withstand modern cryptanalytic techniques, including those powered by machine learning.

The findings revive combinatorial hardness as a viable foundation for constructing secure post-quantum signatures, offering a potential alternative to currently favoured lattice and code-based cryptographic approaches. This research establishes a new benchmark for evaluating the resilience of combinatorial problems against advanced attack methods.

Construction of cryptographic instances and classical solution evaluation are key components of modern security protocols

A 72-qubit superconducting processor forms the foundation of our empirical analysis of the Eidolon post-quantum signature scheme. We constructed random graphs and embedded secret colorings within them to generate hard instances for cryptographic application. The study focused on assessing the resistance of these instances to both classical solvers and a custom graph neural network attacker.

Graph generation began with the creation of Erdős-Rényi graphs, ensuring each edge existed with a probability of 0.5. To establish the secret coloring, we randomly assigned one of k colors to each vertex, ensuring no adjacent vertices shared the same color. Following graph construction, we evaluated the instances using two classical solvers: ILP and DSatur.

The ILP solver formulated the k-colorability problem as an integer linear program and employed a commercial solver to determine if a valid coloring existed. DSatur, a greedy coloring algorithm, sequentially assigned colors to vertices based on their saturation degree, prioritizing those with the most uniquely colored neighbours.

We then implemented a graph neural network attacker, trained to predict the secret coloring given a graph as input. The GNN architecture comprised three graph convolutional layers, followed by a fully connected layer to output the predicted color for each vertex. Crucially, experiments revealed that for graphs with n ≥ 60 vertices, neither the classical solvers nor the graph neural network could reliably recover the secret coloring.

This threshold represents a significant finding, demonstrating that carefully engineered k-coloring instances can withstand both traditional and machine learning-based cryptanalysis. The inability of these attacks to succeed on graphs of this size highlights the potential of combinatorial hardness as a basis for post-quantum cryptographic systems. We measured performance by tracking the time taken for each solver to either find a valid coloring or determine that the instance was unsolvable.

Eidolon cryptographic security withstands classical and machine learning attacks up to n ≥ 60 bits

Researchers have demonstrated the resilience of a novel cryptographic scheme against both classical and machine learning-based attacks, achieving resistance up to a graph size of n ≥ 60. This work introduces Eidolon, a post-signature scheme founded on the NP-complete k-colorability problem, and provides the first empirical analysis of its security.

The study successfully generated hard instances via planted colorings, preserving the statistical profile of random graphs and establishing both correctness and security within the protocol. Experiments reveal that classical solvers, including ILP and DSatur, and a custom graph neural network (GNN) attacker both failed to recover the secret coloring when the graph size reached or exceeded 60 vertices.

This outcome signifies a substantial level of cryptographic strength, as it demonstrates resistance to contemporary cryptanalysis techniques. The construction utilizes a k-partite graph, ensuring a valid k-coloring is inherent to the system by design. Each partition represents a distinct color class, and edges are randomly added between partitions based on a density parameter.

The research team constructed witness graphs by partitioning a vertex set V, where the size of each partition, denoted as ni, falls within the range of floor(n/k) to ceiling(n/k). The algorithm generates a graph with n vertices, calculating the maximum possible edges as n 2 and the number of forbidden intra-partition edges as the sum of the squares of each partition size.

The expected number of allowed edges is then determined, and edges are added with a probability padj, calculated as the density parameter multiplied by the ratio of allowed edges to the total possible edges. This approach ensures the protocol can reliably execute without failure, as the prover always possesses a valid instance. The study’s findings revive combinatorial hardness as a credible foundation for post-quantum signatures, offering a potential pathway for secure communication in the future.

Resistance of k-colourability-based signatures against classical and machine learning attacks remains a significant challenge

Eidolon, a new post-quantum digital signature scheme, is founded upon the computational difficulty of the k-colorability problem. The scheme extends a zero-knowledge protocol and employs Merkle-tree commitments to efficiently compress signatures, reducing their size from O(tn) to O(t log n). A key innovation lies in the generation of challenging instances using planted, or “quiet”, colorings that maintain the statistical characteristics of random graphs.

Empirical analysis demonstrates the scheme’s resistance to both classical solving algorithms, such as integer linear programming and DSatur, and a dedicated graph neural network attacker. Specifically, for graphs of size n ≥ 60, neither the classical solvers nor the graph neural network could successfully recover the secret coloring.

This finding suggests that carefully constructed instances of NP-hard problems can withstand contemporary cryptanalytic techniques, including those leveraging machine learning. The authors acknowledge a limitation in that the current analysis focuses on modest graph sizes and does not address hardness against adaptive or side-channel adversaries.

Future research will concentrate on optimising parameters to meet standard security levels and investigating resilience under more sophisticated attack models. These results reaffirm the potential of NP-hard problems as a basis for post-quantum cryptography, even in the face of advanced data-driven attacks.