We prove that for planted k-SAT instances with k >= 7 at clause density alpha/alpha_s >= 0.21, a positive fraction of variables are frozen directly in the planted model---without requiring transfer from the random model via quiet planting. The expected number of "support clauses" per variable (clauses in which that variable is the unique satisfying literal) exceeds 1 at remarkably low density: alpha/alpha_s ~ 0.20 for k = 7, compared to the random-model freezing threshold at alpha_f/alpha_s ~ 0.90. We prove that the resulting frozen-core structure implies topological disconnection of the solution subgraph across cluster boundaries, with a cycle-robustness argument showing that short cycles in the factor graph cannot quench the supercritical repair cascade. As an immediate corollary, the Hilbert space spanned by satisfying assignments decomposes into orthogonal sectors preserved by any unitary generated by the adjacency matrix---blocking quantum walks, QAOA at all depths, and quantum annealing. We construct a post-quantum commitment scheme whose binding property reduces to the hardness of solving planted k-SAT, provide formal proofs of completeness, soundness, and zero-knowledge, and derive a digital signature scheme with existential unforgeability via the Fiat-Shamir transform. We present a six-vector quantum attack analysis with proved barriers against five algorithmic families. We give concrete parameter recommendations at NIST security levels 1, 3, and 5, and position the scheme within the landscape of SAT-based and CSP-based cryptographic constructions. We prove that the Grover query complexity for breaking the binding property is Omega(2^{fn/2}); empirical cryptanalysis of Glucose and MiniSat CDCL solvers on our exact distribution yields a classical attack cost of 2^{0.234n} operations, enabling concrete parameter selection at NIST security levels 1, 3, and 5. Empirical validation across 100 random seeds at n = 16 confirms complete cluster isolation at every instance tested.
Graph theory has emerged as a foundational mathematical tool in the realms of cryptography and network security. Its ability to model complex relationships, systems, and interactions through vertices and edges enables innovative solutions for encryption, authentication, key distribution, intrusion detection, and secure routing. This research article provides a comprehensive review of recent advancements and applications of graph-theoretical techniques in cryptographic protocols and secure network systems.The study begins by outlining the theoretical underpinnings of graph theory relevant to secure communications, including graph isomorphism, expander graphs, Hamiltonian paths, and graph coloring. It then explores how graph-based methods are utilized in modern cryptographic systems such as zero-knowledge proofs, public-key cryptography, and lightweight encryption schemes. The article also discusses graph-theoretic approaches in blockchain consensus models, attack graph analysis, intrusion detection systems (IDS), and secure routing in wireless sensor networks (WSNs).Recent advancements such as post-quantum cryptography based on hard graph problems, dynamic attack graphs in adaptive security systems, and trust graphs in distributed environments are highlighted. Data from peer-reviewed publications from 2010 to 2025 are synthesized, and key trends are visualized through tables, graphs, and diagrams. The paper also identifies existing challenges, including scalability, computational complexity, and graph-theoretical attack vectors.The discussion critically interprets these findings, connects them to existing literature, and proposes directions for future research, including graph-based AI models for threat prediction and hypergraph frameworks for modeling higher-order trust relationships.Overall, this study offers an integrated perspective on how graph theory continues to transform the cryptographic and security landscape, contributing to the development of resilient, efficient, and scalable secure systems.
This paper studies the \emph{unimodular isomorphism problem} (UIP) of convex lattice polytopes: given two convex lattice polytopes $P$ and $P'$, decide whether there exists a unimodular affine transformation mapping $P$ to $P'$. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( $\mathrm{Sikiri\acute{c}}$, $\mathrm{Sch\ddot{u}rmann}$, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP.
Ethereum is currently the second largest blockchain by market capitalization and a popular platform for cryptocurrencies. As it has grown, the high value present and the anonymity afforded by the technology have led Ethereum to become a hotbed for various cybercrimes. This paper seeks to understand how these fraudulent schemes may be characterized and develop methods for detecting them. One key feature introduced by Ethereum is the ability to use programmable smart contracts to execute code on the blockchain. A common use of smart contracts is implementing fungible tokens with the ERC-20 interface. Such tokens can be used to impersonate legitimate tokens and defraud users. By parsing the event logs emitted by these ERC-20 contracts over 20 different periods of 100K blocks, we construct token transfer graphs for each of the available ERC-20 tokens on the blockchain. By analyzing these graphs, we find a set of characteristics by which suspicious contracts are distinguished from legitimate ones. These observations result in a simple model that can identify scam contracts with an average of 88.7% accuracy. This suggests that the mechanism by which fraudulent schemes function strongly correlates with their transfer graphs and that these graphs may be used to improve scam-detection mechanisms, contributing to making Ethereum safer.
Sandip Das, A. Lahiri, Soumen Nandi, Sagnik Sen · 5 authors
An ( n , m ) -graph is characterized by n types of arcs and m types of edges. A homomorphism of an ( n , m ) -graph G to an ( n , m ) -graph H , is a vertex mapping that preserves adjacency, direction, and type. The ( n , m ) -chromatic number of G , denoted by χ n , m ( G ) , is the minimum value of | V ( H ) | such that there exists a homomorphism of G to H . The theory of homomorphisms of ( n , m ) -graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic , Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of G is bounded by a function of χ n , m ( G ) but not the other way around. Additionally, we show that the acyclic chromatic number of G is bounded by a function of χ n , m ( G ) , a result already known in the reverse direction. Furthermore, we prove that the ( n , m ) -chromatic number for the family of graphs with maximum average degree less than 2 + 2 4 ( 2 n + m ) − 1 , including the subfamily of planar graphs with girth at least 8 ( 2 n + m ) , equals 2 ( 2 n + m ) + 1 . This improves upon previous findings, which proved the ( n , m ) -chromatic number for planar graphs with girth at least 10 ( 2 n + m ) − 4 is 2 ( 2 n + m ) + 1 . It is established that the ( n , m ) -chromatic number for the family T 2 of partial 2-trees is both bounded below and above by quadratic functions of ( 2 n + m ) , with the lower bound being tight when ( 2 n + m ) = 2 . We prove 14 ≤ χ ( 0 , 3 ) ( T 2 ) ≤ 15 and 14 ≤ χ ( 1 , 1 ) ( T 2 ) ≤ 21 which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof.
Numberlink is a logic puzzle with an objective to connect all pairs of cells with the same number by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, the protocol shows how to physically count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Finally, we show that our protocol can be modified to verify a solution of the well-known $k$ vertex-disjoint paths problem, both the undirected and directed settings.
We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs G(n,p=c/n). Let P_c(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability P_c(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c \to c^* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c^* where P_c(0) > 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. Moreover, our results show that these algorithms take exponential time, not just below the 3-colorability threshold, but just above the degree c=1 at which the giant component first appears. In addition, we give experimental evidence and heuristic arguments that this tail takes the form P_c(b) ~ b^{-1} up to an exponential cutoff.