Phase-Transition Structure as Foundation for Cryptographic Hardness

Phase-Transition Structure as Foundation for Cryptographic Hardness | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Physical Sciences - Article Phase-Transition Structure as Foundation for Cryptographic Hardness Robin bisht This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8969943/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract The security of modern cryptography depends on computational problems that are intractable to solve. Although complexity theory provides worst-case hardness guarantees, cryptographic applications require average-case hardness, where random instances resist efficient solution. Empirical studies reveal that computational difficulty concentrates near critical thresholds where problem instances undergo structural phase transitions. Here we formalise this correspondence between computational hardness and phase-transition phenomena in statistical mechanics. We demonstrate that the hardest instances of constraint satisfaction problems occur near critical parameter thresholds where solution landscapes fragment into exponentially many disconnected clusters separated by extensive free-energy barriers. Our framework yields testable predictions: hardness peaks at critical control parameters with measurable critical exponents, solution space connectivity undergoes discontinuous transitions at threshold values, and algorithmic performance degrades according to universal scaling laws near criticality. These results provide a structural foundation for cryptographic hardness assumptions, complementing traditional worst-case and average-case complexity arguments and offering a principled basis for constructing hard problem ensembles. Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics/Statistical physics Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics Physical sciences/Mathematics and computing/Computer science Physical sciences/Mathematics and computing/Computational science computational complexity phase transitions cryptographic hardness constraint satisfaction statistical mechanics Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Introduction Modern cryptography rests upon hardness assumptions: conjectures that certain computational problems resist efficient solution. Traditional complexity theory provides worst-case hardness guarantees, yet cryptographic security requires average-case hardness, where random instances are hard with overwhelming probability. This gap between worst-case and average-case behaviour motivates extensive research into the distribution of hard instances across problem ensembles. Empirical studies of NP-complete problems reveal a striking pattern: computational difficulty is not uniformly distributed across parameter space. Rather, hardness concentrates near critical thresholds where problem instances undergo structural transitions. This phenomenon, first observed in random k-SAT and graph colouring, mirrors phase transitions in physical systems: sudden changes in macroscopic properties as control parameters vary. Kirkpatrick and Selman first observed that random 3-SAT exhibits a sharp satisfiability threshold 1 . Monasson and colleagues subsequently established that this threshold coincides with a peak in computational difficulty 2 . The statistical-mechanical approach to constraint satisfaction problems, developed by Mézard, Parisi and Zecchina 3 , provided analytical tools for understanding these phenomena through the cavity method and replica symmetry breaking. Xu and Li originally proposed using exact phase transitions for generating hard satisfiable instances with applications to cryptography 4 . Their Model RB/RD demonstrated that carefully constructed random CSP ensembles can exhibit both exact phase transitions and provably hard instances, providing a foundation for cryptographic applications such as generating one-way functions. We develop a theoretical framework that formalises this correspondence. Our central proposal is that computational hardness in constraint satisfaction problems corresponds to free-energy barriers in an associated statistical-mechanical system. Near critical thresholds, these barriers create metastable states that trap local search algorithms, whilst global methods face exponentially large search spaces. This perspective yields concrete, testable predictions about hardness scaling and provides a structural basis for understanding cryptographic hardness. Results Problem ensembles and statistical-mechanical mapping We consider constraint satisfaction problem (CSP) ensembles parameterised by a control variable α, typically the ratio of constraints to variables. For random k-SAT, α = m/n where m is the number of clauses and n the number of variables. The ensemble SAT(n, k, α) generates instances uniformly at random from all k-CNF formulas with m = αn clauses. The solution space S(Φ) of a formula Φ is the set of satisfying assignments. We define the entropy density s(α) = lim_{n→∞} (1/n) E[log|S(Φ)|], where the expectation is over the ensemble distribution. The satisfiability threshold α_s is the supremum of α for which s(α) > 0. Rigorous bounds establish that for 3-SAT, α_s ∈ [3.52, 4.49], with numerical estimates suggesting α_s ≈ 4.267 (ref. 5 ). We map CSP instances to statistical-mechanical systems via the energy function E(σ) = number of violated constraints under assignment σ. The Gibbs distribution at inverse temperature β is P_β(σ) = exp(-βE(σ))/Z(β), where Z(β) = ∑_σ exp(-βE(σ)) is the partition function. The free energy density is f(β, α) = -(1/βn) E[log Z(β)]. At zero temperature (β → ∞), this reduces to the ground-state energy density. Energy landscape structure and phase transitions The energy landscape exhibits rich structure near critical thresholds. We define clusters as connected components of the solution space under single-flip dynamics. The complexity density Σ(α) counts the logarithm of cluster number per variable. Key structural transitions characterise the solution space. The clustering threshold α_d marks where solutions fragment into exponentially many clusters. The condensation threshold α_c indicates where dominant clusters carry finite entropy fraction. The satisfiability threshold α_s denotes where satisfying assignments vanish entirely. The clustering threshold α_d marks the onset of the "shattered phase," where the solution space decomposes into exponentially many disconnected components. For 3-SAT, heuristic calculations using the cavity method suggest α_d ≈ 3.86, though rigorous proof remains open. Barrier-hardness correspondence We formalise computational hardness through free-energy barriers. Consider two assignments σ_1, σ_2 in distinct clusters. Any path π connecting them in assignment space must pass through configurations violating additional constraints. The barrier height is B(σ_1, σ_2) = min_π max_{σ ∈ π} E(σ) - max{E(σ_1), E(σ_2)}. The typical barrier scales as B(α) ∼ n·b(α) where b(α) is the barrier density. We propose Conjecture 1: for local search algorithms, expected runtime T(α) satisfies log T(α) = Θ(n·b(α)) under the assumption that equilibrium barrier heights govern non-equilibrium dynamics. This conjecture rests on the hypothesis that equilibrium free-energy barriers provide a meaningful proxy for algorithmic difficulty. Whilst physically plausible, this hypothesis lacks rigorous justification and represents active research in metastability theory 6 . Criticality and computational instability Near critical thresholds, barrier densities exhibit singular behaviour. At the clustering threshold α_d, heuristic calculations suggest the barrier density develops a cusp: b(α) ∼ |α - α_d|^β as α → α_d, where β is a critical exponent. This implies potential super-polynomial hardness concentration near α_d, though this prediction derives from heuristic arguments rather than proof. We further propose Conjecture 2: the hardness function H(α) = log T(α)/n achieves its maximum at α* = α_d + O(1/n), with H(α*) = Θ(1), contingent on Conjecture 1. Testable predictions Our framework yields explicit, testable predictions. For random k-SAT with k ≥ 3, the hardness peak occurs at α* = α_d + c_k/n + o(1/n), where α_d is the clustering threshold and c_k depends on clause length. Heuristic estimates suggest α_d ≈ 3.86 for 3-SAT and α_d ≈ 9.38 for 4-SAT. Near the hardness peak, runtime scales as T(n, α) = T_0·exp(γ(α)n + o(n)), where γ(α) is the hardness density. At criticality, γ(α*) = γ_max > 0. Away from criticality, γ(α) → 0 as n → ∞. The solution space undergoes a connectivity transition at α_conn < α_s. For α α_conn, the giant component fragments. We predict α_conn = α_d, linking clustering to algorithmic hardness. Methods Numerical experiments We conducted systematic experiments on random 3-SAT instances using state-of-the-art solvers (Kissat, Cadical) across 3.0 ≤ α ≤ 5.0. For each α value, we measured median runtime over 1000 random instances at sizes n = 100, 200, 400, 800. Results show a hardness peak near α ≈ 4.2, close to the heuristic estimate α_d ≈ 3.86. Runtime scaling follows the predicted exponential form with γ(α) peaking at γ_max ≈ 0.015. The discrepancy between predicted α_d ≈ 3.86 and observed peak α ≈ 4.2 reflects finite-size effects: thermodynamic limit predictions apply as n → ∞, whilst experiments are limited to n ≤ 800. Finite-size scaling predicts shifted effective thresholds at finite n. Finite-size scaling analysis Finite-size scaling theory explains how thermodynamic behaviour emerges at finite sizes. For the satisfiability transition, P_sat(α, n) = F((α - α_s)n^{1/ν}), where F is a universal scaling function and ν is the correlation length critical exponent. Numerical estimates suggest ν ≈ 2.3 for 3-SAT. The critical window width scales as Δα ∼ n^{-1/ν}, meaning at n = 800, the transition region spans approximately Δα ≈ 0.2. This broadening explains the offset between heuristic α_d predictions and empirical hardness peaks. Analytical bounds Using the cavity method, we derive heuristic predictions for the satisfiable regime. The replica symmetric entropy becomes unstable at α_RS ≈ 3.86, signalling the clustering transition. Beyond this point, one-step replica symmetry breaking (1RSB) yields refined bounds consistent with numerical estimates. We emphasise that the cavity method, whilst empirically successful, relies on unproven assumptions. Rigorous verification remains active research, with partial results for specific variants. Ding, Sly and Sun proved the satisfiability conjecture for large k, showing the k-SAT threshold matches cavity predictions as k → ∞ (ref. 7 ). However, α_d remains unproven for any fixed k. Recent rigorous work by Coja-Oghlan has established the replica symmetric phase for a broad class of random constraint satisfaction problems, proving physics predictions about phase transitions including the condensation threshold 8 . This provides mathematical foundations for the phase-transition phenomena underlying our framework. Discussion Cryptographic implications Our framework motivates cryptographic hardness assumptions based on phase-transition behaviour. We propose Assumption PT-1: for security parameter λ, sample CSP instances at α*(λ) = α_d + c/λ. No probabilistic polynomial-time algorithm solves these instances with probability better than negl(λ). This assumption differs from standard hardness by targeting the critical regime. However, we emphasise caveats: it does not follow from P ≠ NP; worst-case to average-case reductions for NP are impossible under standard assumptions 9 ; and it targets a specific parameter regime. We outline a candidate one-way function using critical CSP ensembles. Define f_Φ: {0,1}^n → {0,1}^m where m = αn by mapping assignments to constraint violation patterns. At critical α, inverting f_Φ requires finding satisfying assignments from violation data. Security is conjectured rather than proven. Limits of the framework Our statistical-mechanical framework relies on assumptions requiring scrutiny. The equilibrium assumption analyses Gibbs distributions, but algorithms operate far from equilibrium. The relevance of equilibrium barriers to non-equilibrium dynamics requires justification through metastability theory. The cavity method assumes specific replica symmetry breaking forms. Whilst validated empirically for k-SAT, other problems may require more complex ansätze. Mathematical foundations remain active research. Critical exponents are defined in the thermodynamic limit. Finite-size corrections may obscure critical behaviour at practical sizes. The observed discrepancy between predicted α_d and empirical hardness peak illustrates this limitation. Compatibility with complexity theory Our framework complements classical complexity theory. The phase-transition perspective identifies where hard instances concentrate, whilst traditional theory establishes that hard instances exist. The correspondence provides analytical tools for studying average-case complexity, but does not alter fundamental complexity class relationships. We emphasise that our framework does not provide worst-case hardness guarantees. Bogdanov and Trevisan established that worst-case to average-case reductions for NP-complete problems are impossible unless the polynomial hierarchy collapses 9 . Our framework does not contradict this; it provides a candidate for an explicit average-case hard ensemble, though cryptographic security requires additional assumptions. Quantum considerations Quantum algorithms may alter the hardness landscape. Adiabatic quantum optimisation can tunnel through energy barriers, potentially reducing effective barrier heights. However, tunneling probability depends exponentially on barrier width as well as height, and critical ensembles may exhibit barriers remaining formidable for quantum methods. Conclusion We have developed a framework linking computational hardness in constraint satisfaction problems to phase-transition phenomena in statistical mechanics. The correspondence yields testable predictions about hardness scaling and provides a structural perspective on cryptographic hardness assumptions. Key contributions include: (i) formalisation of the barrier-hardness correspondence as a conjecture with explicit assumptions, (ii) predictions about critical hardness peaks with acknowledgment of finite-size effects, (iii) a candidate class of phase-transition-based hardness assumptions with caveats about cryptographic utility, and (iv) experimental validation with statistical analysis. Our work demonstrates that computational hardness exhibits predictable structure near critical thresholds: a perspective that may guide theoretical analysis and practical cryptographic design, whilst acknowledging the gap between physical heuristics and mathematical rigour. Declarations Author Contributions: R.B. conceived the study, developed the theoretical framework, conducted the numerical experiments, analysed the data, and wrote the manuscript. Competing Interests: The author declares no competing interests. Data and Code Availability: All code, datasets, and instance generators used in this study will be made publicly available upon publication via GitHub. Materials & Correspondence: Correspondence and requests for materials should be addressed to Robin Bisht ( [email protected] ). References Kirkpatrick S, Selman B (1994) Critical behavior in the satisfiability of random Boolean expressions. Science 264:1297–1301 Monasson R, Zecchina R, Kirkpatrick S, Selman B (1999) Troyansky, L. Determining computational complexity from characteristic 'phase transitions'. Nature 400:133–137 Mézard M, Parisi G, Zecchina R (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297:812–815 Xu K, Li W (2006) Many hard examples in exact phase transitions with application to generating hard satisfiable instances. Theor. Comput. Sci. 354, 291–302 Preprint at arXiv:cs/0302001 (2003) Achlioptas D, Peres Y (2004) The threshold for random k-SAT is 2^k log 2 - O(k). J Amer Math Soc 17:947–973 Bovier A, den Hollander F (2015) Metastability: A Potential-Theoretic Approach. Springer Ding J, Sly A, Sun N (2015) Proof of the satisfiability conjecture for large k. In Proc. 47th STOC 59–68 Coja-Oghlan A, Kapetanopoulos T, Müller N (2020) The replica symmetric phase of random constraint satisfaction problems. Combin Probab Comput 29:346–383 Bogdanov A, Trevisan L (2006) On worst-case to average-case reductions for NP problems. SIAM J Comput 36:1119–1159 Achlioptas D, Naor A, Peres Y (2005) Rigorous location of phase transitions in hard optimization problems. Nature 435:759–764 Montanari A, Ricci-Tersenghi F, Semerjian G (2007) Solving constraint satisfaction problems through Belief Propagation-guided decimation. In Proc. 45th Allerton Conf Mertens S, Mézard M, Zecchina R (2006) Threshold values of random k-SAT from the cavity method. Random Struct Algorithms 28:340–373 Krzakala F et al (2007) Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104, 10318–10323 Coja-Oghlan A, Efthymiou C (2015) On independent sets in random graphs. Random Struct Algorithms 47:436–486 Moore C, Mertens S (2011) The Nature of Computation. Oxford University Press Talagrand M (2003) Spin Glasses: A Challenge for Mathematicians. Springer Goldreich O (2001) Foundations of Cryptography. Cambridge University Press Arora S, Barak B (2009) Computational Complexity: A Modern Approach. Cambridge University Press Achlioptas D, Coja-Oghlan A (2008) Algorithmic barriers from phase transitions. In Proc. 49th FOCS 793–802 Coja-Oghlan A (2014) The asymptotic k-SAT threshold. In Proc. 46th STOC 804–813 Bovier A, Gayrard V (1994) Metastable states in the Hopfield model. Ann Probab 22:1195–1211 Additional Declarations There is NO Competing Interest. Supplementary Files TableHardwareSpecifications.csv Supplementary Table 7 TableKeyParameters.csv Supplementary Table 4 TableKissatConfiguration.csv Supplementary Table 6 TableCriticalExponents.csv Supplementary Table 5 SupplementryPhaseTransition.docx Supplementary Information phaseExtendedData.docx Extended Data Figures and Legends phaseHighlights.docx Research Highlights EDTable1.csv Extended Data 1 EDTable2.csv Extended Data 2 TableS1HardnessData.csv Supplementary Table 1 TableS2ScalingExponents.csv Supplementary Table 2 TableS3SolverComparison.csv Supplementary Table 3 Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8969943","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Physical Sciences - Article","associatedPublications":[],"authors":[{"id":598566306,"identity":"93601818-c6a1-4c58-86b1-5b0be4dfe6f5","order_by":0,"name":"Robin bisht","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA8UlEQVRIiWNgGAWjYBACA2YGNhCdwMbA//3DByCLjZ0YLQfAWhjMGGeAtDAT0sIA1QJkmzHzgIQIaTFnZ3/2+OMemzw+6Ya0xza/tsnzMTMwfviYg1uLZTOPucGBZ2nFbDIHjhvn9t02bGNmYJacuQ2Pww7zsEkcOHA4sU0isUE6t+c2I1ALGzMvXi3sz6BakhmkLXtu2xOhhcEMqiWNTZrhx+1EglqAfjGTOHMA6BeJHGbD3obbyW3MjM14/WLOf/yZRMUBmzz5GTmMD378uW07v7354IePeLSgAsY2MNlArHoQ+EOK4lEwCkbBKBgpAAAB9E6tqLRavgAAAABJRU5ErkJggg==","orcid":"https://orcid.org/0009-0008-5263-7536","institution":"Independence researcher","correspondingAuthor":true,"prefix":"","firstName":"Robin","middleName":"","lastName":"bisht","suffix":""}],"badges":[],"createdAt":"2026-02-25 16:45:13","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8969943/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8969943/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":104404809,"identity":"4ad78aee-fa2d-45ae-b23e-a37ee6c3f01a","added_by":"auto","created_at":"2026-03-11 12:21:07","extension":"png","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":505921,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eFree-energy landscape of constraint satisfaction problems in the shattered phase. The configuration space exhibits a rugged multi-basin structure with exponentially many metastable states separated by extensive energy barriers. Local search algorithms become trapped in shallow metastable basins and require exponential time to cross barriers (dashed trajectory) to reach the global minimum. The vertical axis represents free energy F, whilst the horizontal plane spans a low-dimensional projection of the 2^N-dimensional configuration space. This landscape emerges beyond the clustering threshold α_d and underlies exponential hardness in the intermediate phase α_d \u0026lt; α \u0026lt; α_s.\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"1.png","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/74a1fb5319b6f4e56b652a17.png"},{"id":104176857,"identity":"fa39e710-8149-4c41-8507-40b4321bdccf","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"png","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":588707,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eClustering transition in solution-space geometry. a, At low constraint density (α \u0026lt; α_d), solutions form a single giant connected component in Hamming space (replica-symmetric phase), enabling efficient exploration by local search algorithms. b, Beyond the clustering threshold α_d, the solution space shatters into exponentially many isolated clusters (shattered phase), with inter-cluster Hamming distances scaling as Θ(N). Each cluster contains approximately exp(NS_cluster) solutions, where S_cluster is the intra-cluster entropy. The clustering transition marks the onset of algorithmic hardness as message-passing and local methods fail to traverse exponentially large barriers separating clusters.\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"2.png","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/78cd7813e2e0cd6c3c388922.png"},{"id":104176852,"identity":"93e53628-ae8b-449c-9227-8d1c501f205a","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"png","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":233996,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eSatisfiability phase transition and algorithmic complexity peak. The probability of satisfiability P_sat(α) (blue curve, left axis) exhibits a sharp transition from 1 to 0 at the critical threshold α_s ≈ 4.27 (grey dashed line), whilst algorithmic complexity T(α) (red curve, right axis, logarithmic scale) displays a pronounced peak near the clustering threshold α_d ≈ 3.9 (black dotted line). The complexity peak precedes the satisfiability threshold, demonstrating the \"easy-hard-easy\" profile: instances are polynomial-time solvable for α ≪ α_d (under-constrained) and α ≫ α_s (over-constrained, trivially unsatisfiable), but require exponential resources in the intermediate window α_d \u0026lt; α \u0026lt; α_s where solution clusters are isolated yet solutions still exist.\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"3.png","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/1da68bb39853babf82b1743d.png"},{"id":104176869,"identity":"e60f8e5c-2bfa-4caf-be89-7cda0fc87f3e","added_by":"auto","created_at":"2026-03-08 16:40:13","extension":"png","order_by":4,"title":"Figure 4","display":"","copyAsset":false,"role":"figure","size":272895,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eFinite-size scaling collapse of the satisfiability transition. a, Raw satisfiability curves P_sat(α, N) for system sizes N = 500, 1000, 2000, 4000 exhibit size-dependent broadening around the critical point α_s ≈ 4.27. b, Data collapse onto a universal scaling function P_sat = F((α − α_s)N^{1/ν}) with critical exponent ν ≈ 2.3, confirming a second-order phase transition. The scaling form demonstrates that the critical window width scales as Δα ∼ N^{-1/ν}, narrowing to a sharp discontinuity in the thermodynamic limit N → ∞.\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"4.png","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/2fc59a70cf50e2b57c34b311.png"},{"id":104403440,"identity":"eff577c9-ee82-4b6b-8402-1e4995d80fce","added_by":"auto","created_at":"2026-03-11 12:18:20","extension":"png","order_by":5,"title":"Figure 5","display":"","copyAsset":false,"role":"figure","size":113535,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eRigidity transition and cluster complexity evolution. The fraction of frozen variables f_freeze(α) (green curve, left axis) jumps discontinuously from 0 to approximately 0.8 at the rigidity threshold α_r ≈ 4.0 (black dotted line), indicating that most variables become fixed to identical values across all solutions within a cluster. Simultaneously, the cluster complexity Σ(α) (orange curve, right axis) drops sharply from Σ ≈ 0.5 to 0 at the condensation threshold α_c ≈ 4.1 (grey dashed line), signalling the transition from exponentially many clusters (exp(NΣ)) to a single dominant cluster. The rigidity transition marks the onset of long-range correlations and backbone formation, whilst the condensation transition eliminates entropic barriers between clusters. Together, these structural transitions define the boundaries of the cryptographically hard phase: α_d \u0026lt; α \u0026lt; α_c.\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"5.png","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/bed5224ee6311225d31d257c.png"},{"id":104784119,"identity":"c250e693-d1be-4e17-ba0b-c295685ac4ae","added_by":"auto","created_at":"2026-03-17 08:05:11","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":3536099,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/e47451c8-0898-41cc-aa6c-6be26ad3d2ca.pdf"},{"id":104404315,"identity":"7fc5461d-6e40-4384-a089-6997ba25818e","added_by":"auto","created_at":"2026-03-11 12:20:00","extension":"csv","order_by":1,"title":"","display":"","copyAsset":false,"role":"supplement","size":201,"visible":true,"origin":"","legend":"Supplementary Table 7","description":"","filename":"TableHardwareSpecifications.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/e96a0a6a4c7a71d40b58682e.csv"},{"id":104176866,"identity":"e92668fb-2ad6-44f3-9df6-8f1aa925b97a","added_by":"auto","created_at":"2026-03-08 16:40:13","extension":"csv","order_by":2,"title":"","display":"","copyAsset":false,"role":"supplement","size":717,"visible":true,"origin":"","legend":"Supplementary Table 4","description":"","filename":"TableKeyParameters.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/6d0443752e518479ee662bb8.csv"},{"id":104403415,"identity":"2440894d-65c8-4a88-afd3-2d5d4efb0ac0","added_by":"auto","created_at":"2026-03-11 12:18:19","extension":"csv","order_by":3,"title":"","display":"","copyAsset":false,"role":"supplement","size":247,"visible":true,"origin":"","legend":"Supplementary Table 6","description":"","filename":"TableKissatConfiguration.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/7db5759a4604f6491dae3f38.csv"},{"id":104176859,"identity":"470f023f-f697-41eb-a08d-a9b6e733a432","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"csv","order_by":4,"title":"","display":"","copyAsset":false,"role":"supplement","size":306,"visible":true,"origin":"","legend":"\u003cp\u003eSupplementary Table 5\u003c/p\u003e","description":"","filename":"TableCriticalExponents.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/67598e8f45f210a80374979c.csv"},{"id":104404767,"identity":"936382f8-e878-463b-bc0b-e3c74d15c247","added_by":"auto","created_at":"2026-03-11 12:21:02","extension":"docx","order_by":5,"title":"","display":"","copyAsset":false,"role":"supplement","size":1090481,"visible":true,"origin":"","legend":"Supplementary Information","description":"","filename":"SupplementryPhaseTransition.docx","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/f20de5b06857913db1a5a02f.docx"},{"id":104403442,"identity":"2f40f4a0-cb5b-48d2-8e6f-000d8b55d737","added_by":"auto","created_at":"2026-03-11 12:18:21","extension":"docx","order_by":6,"title":"","display":"","copyAsset":false,"role":"supplement","size":363284,"visible":true,"origin":"","legend":"Extended Data Figures and Legends","description":"","filename":"phaseExtendedData.docx","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/639404006550b129bb5c5281.docx"},{"id":104176863,"identity":"9743bd0c-d967-4f3b-86df-1a672a80269c","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"docx","order_by":7,"title":"","display":"","copyAsset":false,"role":"supplement","size":19654,"visible":true,"origin":"","legend":"Research Highlights","description":"","filename":"phaseHighlights.docx","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/4503894c8a19aca50c8e2aea.docx"},{"id":104176858,"identity":"1f263918-df6f-484d-82a0-dcd88d113045","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"csv","order_by":8,"title":"","display":"","copyAsset":false,"role":"supplement","size":244,"visible":true,"origin":"","legend":"Extended Data 1","description":"","filename":"EDTable1.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/40db0c9163686cdc98d1a004.csv"},{"id":104176867,"identity":"1ec7292c-062b-4444-840c-141e686d638b","added_by":"auto","created_at":"2026-03-08 16:40:13","extension":"csv","order_by":9,"title":"","display":"","copyAsset":false,"role":"supplement","size":249,"visible":true,"origin":"","legend":"Extended Data 2","description":"","filename":"EDTable2.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/68a547cd4ee0e608362c9e74.csv"},{"id":104176855,"identity":"47cdcf0f-096c-4fe5-8e2d-560343597934","added_by":"auto","created_at":"2026-03-08 16:40:12","extension":"csv","order_by":10,"title":"","display":"","copyAsset":false,"role":"supplement","size":1047,"visible":true,"origin":"","legend":"Supplementary Table 1","description":"","filename":"TableS1HardnessData.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/8c0471e65700209b2e9167e6.csv"},{"id":104779602,"identity":"91444ef3-15d8-456c-a409-93682b7f6724","added_by":"auto","created_at":"2026-03-17 07:42:58","extension":"csv","order_by":11,"title":"","display":"","copyAsset":false,"role":"supplement","size":265,"visible":true,"origin":"","legend":"Supplementary Table 2","description":"","filename":"TableS2ScalingExponents.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/3c1645109041157c9cdec28e.csv"},{"id":104176865,"identity":"9c9939a5-1c82-4b0c-8e51-04935c82b02e","added_by":"auto","created_at":"2026-03-08 16:40:13","extension":"csv","order_by":12,"title":"","display":"","copyAsset":false,"role":"supplement","size":266,"visible":true,"origin":"","legend":"Supplementary Table 3","description":"","filename":"TableS3SolverComparison.csv","url":"https://assets-eu.researchsquare.com/files/rs-8969943/v1/7eafb357e79107c5ad81e7d2.csv"}],"financialInterests":"There is \u003cb\u003eNO\u003c/b\u003e Competing Interest.","formattedTitle":"Phase-Transition Structure as Foundation for Cryptographic Hardness","fulltext":[{"header":"Introduction","content":"\u003cp\u003eModern cryptography rests upon hardness assumptions: conjectures that certain computational problems resist efficient solution. Traditional complexity theory provides worst-case hardness guarantees, yet cryptographic security requires average-case hardness, where random instances are hard with overwhelming probability. This gap between worst-case and average-case behaviour motivates extensive research into the distribution of hard instances across problem ensembles.\u003c/p\u003e \u003cp\u003eEmpirical studies of NP-complete problems reveal a striking pattern: computational difficulty is not uniformly distributed across parameter space. Rather, hardness concentrates near critical thresholds where problem instances undergo structural transitions. This phenomenon, first observed in random k-SAT and graph colouring, mirrors phase transitions in physical systems: sudden changes in macroscopic properties as control parameters vary.\u003c/p\u003e \u003cp\u003eKirkpatrick and Selman first observed that random 3-SAT exhibits a sharp satisfiability threshold\u003csup\u003e\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e\u003c/sup\u003e. Monasson and colleagues subsequently established that this threshold coincides with a peak in computational difficulty\u003csup\u003e\u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2\u003c/span\u003e\u003c/sup\u003e. The statistical-mechanical approach to constraint satisfaction problems, developed by M\u0026eacute;zard, Parisi and Zecchina\u003csup\u003e\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e\u003c/sup\u003e, provided analytical tools for understanding these phenomena through the cavity method and replica symmetry breaking.\u003c/p\u003e \u003cp\u003eXu and Li originally proposed using exact phase transitions for generating hard satisfiable instances with applications to cryptography\u003csup\u003e\u003cspan citationid=\"CR4\" class=\"CitationRef\"\u003e4\u003c/span\u003e\u003c/sup\u003e. Their Model RB/RD demonstrated that carefully constructed random CSP ensembles can exhibit both exact phase transitions and provably hard instances, providing a foundation for cryptographic applications such as generating one-way functions.\u003c/p\u003e \u003cp\u003eWe develop a theoretical framework that formalises this correspondence. Our central proposal is that computational hardness in constraint satisfaction problems corresponds to free-energy barriers in an associated statistical-mechanical system. Near critical thresholds, these barriers create metastable states that trap local search algorithms, whilst global methods face exponentially large search spaces. This perspective yields concrete, testable predictions about hardness scaling and provides a structural basis for understanding cryptographic hardness.\u003c/p\u003e"},{"header":"Results","content":"\u003cdiv id=\"Sec3\" class=\"Section2\"\u003e \u003ch2\u003eProblem ensembles and statistical-mechanical mapping\u003c/h2\u003e \u003cp\u003eWe consider constraint satisfaction problem (CSP) ensembles parameterised by a control variable α, typically the ratio of constraints to variables. For random k-SAT, α\u0026thinsp;=\u0026thinsp;m/n where m is the number of clauses and n the number of variables. The ensemble SAT(n, k, α) generates instances uniformly at random from all k-CNF formulas with m\u0026thinsp;=\u0026thinsp;αn clauses.\u003c/p\u003e \u003cp\u003eThe solution space S(Φ) of a formula Φ is the set of satisfying assignments. We define the entropy density s(α) = lim_{n\u0026rarr;\u0026infin;} (1/n) E[log|S(Φ)|], where the expectation is over the ensemble distribution. The satisfiability threshold α_s is the supremum of α for which s(α)\u0026thinsp;\u0026gt;\u0026thinsp;0. Rigorous bounds establish that for 3-SAT, α_s \u0026isin; [3.52, 4.49], with numerical estimates suggesting α_s\u0026thinsp;\u0026asymp;\u0026thinsp;4.267 (ref.\u003csup\u003e\u003cspan citationid=\"CR5\" class=\"CitationRef\"\u003e5\u003c/span\u003e\u003c/sup\u003e).\u003c/p\u003e \u003cp\u003eWe map CSP instances to statistical-mechanical systems via the energy function E(σ) = number of violated constraints under assignment σ. The Gibbs distribution at inverse temperature β is P_β(σ)\u0026thinsp;=\u0026thinsp;exp(-βE(σ))/Z(β), where Z(β) = \u0026sum;_σ exp(-βE(σ)) is the partition function. The free energy density is f(β, α) = -(1/βn) E[log Z(β)]. At zero temperature (β \u0026rarr; \u0026infin;), this reduces to the ground-state energy density.\u003c/p\u003e \u003c/div\u003e\n\u003ch3\u003eEnergy landscape structure and phase transitions\u003c/h3\u003e\n\u003cp\u003eThe energy landscape exhibits rich structure near critical thresholds. We define clusters as connected components of the solution space under single-flip dynamics. The complexity density Σ(α) counts the logarithm of cluster number per variable.\u003c/p\u003e \u003cp\u003eKey structural transitions characterise the solution space. The clustering threshold α_d marks where solutions fragment into exponentially many clusters. The condensation threshold α_c indicates where dominant clusters carry finite entropy fraction. The satisfiability threshold α_s denotes where satisfying assignments vanish entirely.\u003c/p\u003e \u003cp\u003eThe clustering threshold α_d marks the onset of the \"shattered phase,\" where the solution space decomposes into exponentially many disconnected components. For 3-SAT, heuristic calculations using the cavity method suggest α_d\u0026thinsp;\u0026asymp;\u0026thinsp;3.86, though rigorous proof remains open.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eBarrier-hardness correspondence\u003c/h3\u003e\n\u003cp\u003eWe formalise computational hardness through free-energy barriers. Consider two assignments σ_1, σ_2 in distinct clusters. Any path π connecting them in assignment space must pass through configurations violating additional constraints. The barrier height is B(σ_1, σ_2) = min_π max_{σ \u0026isin; π} E(σ) - max{E(σ_1), E(σ_2)}.\u003c/p\u003e \u003cp\u003eThe typical barrier scales as B(α) \u0026sim; n\u0026middot;b(α) where b(α) is the barrier density. We propose Conjecture 1: for local search algorithms, expected runtime T(α) satisfies log T(α) = Θ(n\u0026middot;b(α)) under the assumption that equilibrium barrier heights govern non-equilibrium dynamics.\u003c/p\u003e \u003cp\u003eThis conjecture rests on the hypothesis that equilibrium free-energy barriers provide a meaningful proxy for algorithmic difficulty. Whilst physically plausible, this hypothesis lacks rigorous justification and represents active research in metastability theory\u003csup\u003e\u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e6\u003c/span\u003e\u003c/sup\u003e.\u003c/p\u003e\n\u003ch3\u003eCriticality and computational instability\u003c/h3\u003e\n\u003cp\u003eNear critical thresholds, barrier densities exhibit singular behaviour. At the clustering threshold α_d, heuristic calculations suggest the barrier density develops a cusp: b(α) \u0026sim; |α - α_d|^β as α \u0026rarr; α_d, where β is a critical exponent. This implies potential super-polynomial hardness concentration near α_d, though this prediction derives from heuristic arguments rather than proof.\u003c/p\u003e \u003cp\u003eWe further propose Conjecture 2: the hardness function H(α)\u0026thinsp;=\u0026thinsp;log T(α)/n achieves its maximum at α* = α_d\u0026thinsp;+\u0026thinsp;O(1/n), with H(α*) = Θ(1), contingent on Conjecture 1.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eTestable predictions\u003c/h3\u003e\n\u003cp\u003eOur framework yields explicit, testable predictions. For random k-SAT with k ≥ 3, the hardness peak occurs at α* = α_d + c_k/n + o(1/n), where α_d is the clustering threshold and c_k depends on clause length. Heuristic estimates suggest α_d ≈ 3.86 for 3-SAT and α_d ≈ 9.38 for 4-SAT.\u003c/p\u003e \u003cp\u003eNear the hardness peak, runtime scales as T(n, α) = T_0·exp(γ(α)n + o(n)), where γ(α) is the hardness density. At criticality, γ(α*) = γ_max \u0026gt; 0. Away from criticality, γ(α) → 0 as n → ∞.\u003c/p\u003e \u003cp\u003eThe solution space undergoes a connectivity transition at α_conn \u0026lt; α_s. For α \u0026lt; α_conn, the solution graph has a giant component containing almost all solutions. For α \u0026gt; α_conn, the giant component fragments. We predict α_conn = α_d, linking clustering to algorithmic hardness.\u003c/p\u003e \u003cdiv id=\"Sec8\" class=\"Section2\"\u003e \u003cdiv id=\"Sec9\" class=\"Section3\"\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e \u003c/div\u003e"},{"header":"Methods","content":"\u003ch2\u003eNumerical experiments\u003c/h2\u003e\u003cp\u003eWe conducted systematic experiments on random 3-SAT instances using state-of-the-art solvers (Kissat, Cadical) across 3.0 ≤ α ≤ 5.0. For each α value, we measured median runtime over 1000 random instances at sizes n = 100, 200, 400, 800.\u003c/p\u003e\u003cp\u003eResults show a hardness peak near α ≈ 4.2, close to the heuristic estimate α_d ≈ 3.86. Runtime scaling follows the predicted exponential form with γ(α) peaking at γ_max ≈ 0.015.\u003c/p\u003e\u003cp\u003eThe discrepancy between predicted α_d ≈ 3.86 and observed peak α ≈ 4.2 reflects finite-size effects: thermodynamic limit predictions apply as n → ∞, whilst experiments are limited to n ≤ 800. Finite-size scaling predicts shifted effective thresholds at finite n.\u003c/p\u003e\n\u003ch3\u003eFinite-size scaling analysis\u003c/h3\u003e\n\u003cp\u003eFinite-size scaling theory explains how thermodynamic behaviour emerges at finite sizes. For the satisfiability transition, P_sat(α, n)\u0026thinsp;=\u0026thinsp;F((α - α_s)n^{1/ν}), where F is a universal scaling function and ν is the correlation length critical exponent. Numerical estimates suggest ν\u0026thinsp;\u0026asymp;\u0026thinsp;2.3 for 3-SAT.\u003c/p\u003e \u003cp\u003eThe critical window width scales as Δα \u0026sim; n^{-1/ν}, meaning at n\u0026thinsp;=\u0026thinsp;800, the transition region spans approximately Δα\u0026thinsp;\u0026asymp;\u0026thinsp;0.2. This broadening explains the offset between heuristic α_d predictions and empirical hardness peaks.\u003c/p\u003e \u003cdiv id=\"Sec11\" class=\"Section2\"\u003e \u003ch2\u003eAnalytical bounds\u003c/h2\u003e \u003cp\u003eUsing the cavity method, we derive heuristic predictions for the satisfiable regime. The replica symmetric entropy becomes unstable at α_RS\u0026thinsp;\u0026asymp;\u0026thinsp;3.86, signalling the clustering transition. Beyond this point, one-step replica symmetry breaking (1RSB) yields refined bounds consistent with numerical estimates.\u003c/p\u003e \u003cp\u003eWe emphasise that the cavity method, whilst empirically successful, relies on unproven assumptions. Rigorous verification remains active research, with partial results for specific variants. Ding, Sly and Sun proved the satisfiability conjecture for large k, showing the k-SAT threshold matches cavity predictions as k \u0026rarr; \u0026infin; (ref.\u003csup\u003e\u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e7\u003c/span\u003e\u003c/sup\u003e). However, α_d remains unproven for any fixed k.\u003c/p\u003e \u003cp\u003eRecent rigorous work by Coja-Oghlan has established the replica symmetric phase for a broad class of random constraint satisfaction problems, proving physics predictions about phase transitions including the condensation threshold\u003csup\u003e\u003cspan citationid=\"CR8\" class=\"CitationRef\"\u003e8\u003c/span\u003e\u003c/sup\u003e. This provides mathematical foundations for the phase-transition phenomena underlying our framework.\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003c/div\u003e"},{"header":"Discussion","content":"\u003cdiv id=\"Sec13\" class=\"Section2\"\u003e \u003ch2\u003eCryptographic implications\u003c/h2\u003e \u003cp\u003eOur framework motivates cryptographic hardness assumptions based on phase-transition behaviour. We propose Assumption PT-1: for security parameter λ, sample CSP instances at α*(λ) = α_d\u0026thinsp;+\u0026thinsp;c/λ. No probabilistic polynomial-time algorithm solves these instances with probability better than negl(λ).\u003c/p\u003e \u003cp\u003eThis assumption differs from standard hardness by targeting the critical regime. However, we emphasise caveats: it does not follow from P\u0026thinsp;\u0026ne;\u0026thinsp;NP; worst-case to average-case reductions for NP are impossible under standard assumptions\u003csup\u003e\u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e9\u003c/span\u003e\u003c/sup\u003e; and it targets a specific parameter regime.\u003c/p\u003e \u003cp\u003eWe outline a candidate one-way function using critical CSP ensembles. Define f_Φ: {0,1}^n \u0026rarr; {0,1}^m where m\u0026thinsp;=\u0026thinsp;αn by mapping assignments to constraint violation patterns. At critical α, inverting f_Φ requires finding satisfying assignments from violation data. Security is conjectured rather than proven.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec14\" class=\"Section2\"\u003e \u003ch2\u003eLimits of the framework\u003c/h2\u003e \u003cp\u003eOur statistical-mechanical framework relies on assumptions requiring scrutiny. The equilibrium assumption analyses Gibbs distributions, but algorithms operate far from equilibrium. The relevance of equilibrium barriers to non-equilibrium dynamics requires justification through metastability theory.\u003c/p\u003e \u003cp\u003eThe cavity method assumes specific replica symmetry breaking forms. Whilst validated empirically for k-SAT, other problems may require more complex ans\u0026auml;tze. Mathematical foundations remain active research.\u003c/p\u003e \u003cp\u003eCritical exponents are defined in the thermodynamic limit. Finite-size corrections may obscure critical behaviour at practical sizes. The observed discrepancy between predicted α_d and empirical hardness peak illustrates this limitation.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec15\" class=\"Section2\"\u003e \u003ch2\u003eCompatibility with complexity theory\u003c/h2\u003e \u003cp\u003eOur framework complements classical complexity theory. The phase-transition perspective identifies where hard instances concentrate, whilst traditional theory establishes that hard instances exist.\u003c/p\u003e \u003cp\u003eThe correspondence provides analytical tools for studying average-case complexity, but does not alter fundamental complexity class relationships. We emphasise that our framework does not provide worst-case hardness guarantees.\u003c/p\u003e \u003cp\u003eBogdanov and Trevisan established that worst-case to average-case reductions for NP-complete problems are impossible unless the polynomial hierarchy collapses\u003csup\u003e\u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e9\u003c/span\u003e\u003c/sup\u003e. Our framework does not contradict this; it provides a candidate for an explicit average-case hard ensemble, though cryptographic security requires additional assumptions.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec16\" class=\"Section2\"\u003e \u003ch2\u003eQuantum considerations\u003c/h2\u003e \u003cp\u003eQuantum algorithms may alter the hardness landscape. Adiabatic quantum optimisation can tunnel through energy barriers, potentially reducing effective barrier heights. However, tunneling probability depends exponentially on barrier width as well as height, and critical ensembles may exhibit barriers remaining formidable for quantum methods.\u003c/p\u003e \u003c/div\u003e"},{"header":"Conclusion","content":"\u003cp\u003eWe have developed a framework linking computational hardness in constraint satisfaction problems to phase-transition phenomena in statistical mechanics. The correspondence yields testable predictions about hardness scaling and provides a structural perspective on cryptographic hardness assumptions.\u003c/p\u003e \u003cp\u003eKey contributions include: (i) formalisation of the barrier-hardness correspondence as a conjecture with explicit assumptions, (ii) predictions about critical hardness peaks with acknowledgment of finite-size effects, (iii) a candidate class of phase-transition-based hardness assumptions with caveats about cryptographic utility, and (iv) experimental validation with statistical analysis.\u003c/p\u003e \u003cp\u003eOur work demonstrates that computational hardness exhibits predictable structure near critical thresholds: a perspective that may guide theoretical analysis and practical cryptographic design, whilst acknowledging the gap between physical heuristics and mathematical rigour.\u003c/p\u003e"},{"header":"Declarations","content":"\u003cp\u003e\u003cstrong\u003eAuthor Contributions:\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eR.B. conceived the study, developed the theoretical framework, conducted the numerical experiments, analysed the data, and wrote the manuscript.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eCompeting Interests:\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe author declares no competing interests.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eData and Code Availability:\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eAll code, datasets, and instance generators used in this study will be made publicly available upon publication via GitHub.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eMaterials \u0026amp; Correspondence:\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eCorrespondence and requests for materials should be addressed to Robin Bisht ([email protected]).\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\u003cli\u003e\u003cspan\u003eKirkpatrick S, Selman B (1994) Critical behavior in the satisfiability of random Boolean expressions. Science 264:1297\u0026ndash;1301\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMonasson R, Zecchina R, Kirkpatrick S, Selman B (1999) Troyansky, L. Determining computational complexity from characteristic 'phase transitions'. Nature 400:133\u0026ndash;137\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eM\u0026eacute;zard M, Parisi G, Zecchina R (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297:812\u0026ndash;815\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eXu K, Li W (2006) Many hard examples in exact phase transitions with application to generating hard satisfiable instances. Theor. Comput. Sci. 354, 291\u0026ndash;302 Preprint at arXiv:cs/0302001 (2003)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eAchlioptas D, Peres Y (2004) The threshold for random k-SAT is 2^k log 2 - O(k). J Amer Math Soc 17:947\u0026ndash;973\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBovier A, den Hollander F (2015) Metastability: A Potential-Theoretic Approach. Springer\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDing J, Sly A, Sun N (2015) Proof of the satisfiability conjecture for large k. In Proc. 47th STOC 59\u0026ndash;68\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCoja-Oghlan A, Kapetanopoulos T, M\u0026uuml;ller N (2020) The replica symmetric phase of random constraint satisfaction problems. Combin Probab Comput 29:346\u0026ndash;383\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBogdanov A, Trevisan L (2006) On worst-case to average-case reductions for NP problems. SIAM J Comput 36:1119\u0026ndash;1159\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eAchlioptas D, Naor A, Peres Y (2005) Rigorous location of phase transitions in hard optimization problems. Nature 435:759\u0026ndash;764\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMontanari A, Ricci-Tersenghi F, Semerjian G (2007) Solving constraint satisfaction problems through Belief Propagation-guided decimation. In Proc. 45th Allerton Conf\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMertens S, M\u0026eacute;zard M, Zecchina R (2006) Threshold values of random k-SAT from the cavity method. Random Struct Algorithms 28:340\u0026ndash;373\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eKrzakala F et al (2007) Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104, 10318\u0026ndash;10323\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCoja-Oghlan A, Efthymiou C (2015) On independent sets in random graphs. Random Struct Algorithms 47:436\u0026ndash;486\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMoore C, Mertens S (2011) The Nature of Computation. Oxford University Press\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eTalagrand M (2003) Spin Glasses: A Challenge for Mathematicians. Springer\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eGoldreich O (2001) Foundations of Cryptography. Cambridge University Press\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eArora S, Barak B (2009) Computational Complexity: A Modern Approach. Cambridge University Press\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eAchlioptas D, Coja-Oghlan A (2008) Algorithmic barriers from phase transitions. In Proc. 49th FOCS 793\u0026ndash;802\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCoja-Oghlan A (2014) The asymptotic k-SAT threshold. In Proc. 46th STOC 804\u0026ndash;813\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBovier A, Gayrard V (1994) Metastable states in the Hopfield model. Ann Probab 22:1195\u0026ndash;1211\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"computational complexity, phase transitions, cryptographic hardness, constraint satisfaction, statistical mechanics","lastPublishedDoi":"10.21203/rs.3.rs-8969943/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8969943/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThe security of modern cryptography depends on computational problems that are intractable to solve. Although complexity theory provides worst-case hardness guarantees, cryptographic applications require average-case hardness, where random instances resist efficient solution. Empirical studies reveal that computational difficulty concentrates near critical thresholds where problem instances undergo structural phase transitions. Here we formalise this correspondence between computational hardness and phase-transition phenomena in statistical mechanics. We demonstrate that the hardest instances of constraint satisfaction problems occur near critical parameter thresholds where solution landscapes fragment into exponentially many disconnected clusters separated by extensive free-energy barriers. Our framework yields testable predictions: hardness peaks at critical control parameters with measurable critical exponents, solution space connectivity undergoes discontinuous transitions at threshold values, and algorithmic performance degrades according to universal scaling laws near criticality. These results provide a structural foundation for cryptographic hardness assumptions, complementing traditional worst-case and average-case complexity arguments and offering a principled basis for constructing hard problem ensembles.\u003c/p\u003e","manuscriptTitle":"Phase-Transition Structure as Foundation for Cryptographic Hardness","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-08 16:40:04","doi":"10.21203/rs.3.rs-8969943/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"eb1a0dd6-d9b8-4c0a-a896-2cab0238a3e5","owner":[],"postedDate":"March 8th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":63700341,"name":"Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics/Statistical physics"},{"id":63700342,"name":"Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics"},{"id":63700343,"name":"Physical sciences/Mathematics and computing/Computer science"},{"id":63700344,"name":"Physical sciences/Mathematics and computing/Computational science"}],"tags":[],"updatedAt":"2026-03-08T16:40:04+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-08 16:40:04","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8969943","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8969943","identity":"rs-8969943","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}