QGCL: Quantum-Guided Clause Learning for Cryptanalytic SAT

• URL: http://arxiv.org/abs/2605.25756v1
• Date: Mon, 25 May 2026 12:09:01 GMT
• Title: QGCL: Quantum-Guided Clause Learning for Cryptanalytic SAT
• Abstract summary: Power side-channel attacks on AES exploit data-dependent physical leakage to recover secret keys.<n>S.A.T.-assisted power side-channel cryptanalysis addresses this challenge by encoding AES semantics, key constraints, plaintext/text consistency, and leakage predicates as CNF.<n>We propose QGCL, a Quantum-Guided Conflict-Driven Clause Learning framework in which Grover search is invoked only on small subformulas extracted dynamically around CDCL conflict cores.
• Score: 2.5435687567731926
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Power side-channel attacks on AES exploit data-dependent physical leakage to recover secret keys, but turning noisy leakage observations into a verified AES-128 key remains a hard combinational search problem. SAT-assisted power side-channel cryptanalysis addresses this challenge by encoding AES semantics, key constraints, plaintext/ciphertext consistency, and leakage predicates as CNF, so that candidate keys must satisfy the exact cryptographic specification. These cryptanalytic SAT formulas are large and highly structured; our largest controlled AES-oriented power-SCA instances contain up to 39,389 variables and 137,712 clauses, making a full-formula Grover search well beyond the scale studied here and beyond currently practical near-term implementations. We propose QGCL, a Quantum-Guided Conflict-Driven Clause Learning (CDCL) framework in which Grover search is invoked only on small subformulas extracted dynamically around CDCL conflict cores. The quantum subsolver returns candidate assignments and violation scores that bias branching heuristics, while final SAT/UNSAT decisions and key verification remain classical. We evaluate QGCL on AES-oriented cryptanalytic SAT instances derived from power side-channel CNFs with leakage-derived hint configurations, measuring conflicts, restarts, decisions, and propagations. The experiments show consistent reductions in these solver-internal statistics on harder instances, with up to an 86% reduction in conflicts compared with the classical conflict-learning baseline. Parameter sweeps over the number of Grover oracle calls and the subproblem size identify a regime in which a modest quantum resource allocation captures most of the observed improvement.

Related papers

• Q-LEAK: Quantum-Based LEAKage Verification for Side-Channel Countermeasures [2.5435687567731926]
  We propose Q-LEAK, a quantum-based verification approach using Grover's algorithm.<n>Q-LEAK consistently recovered a satisfying assignment within 1-4 tries, with marked bitstrings amplified clearly above the background distribution.<n>The evaluation of Q-LEAK on real quantum hardware revealed at least one classically verified SAT assignment, despite the presence of noise.
  arXiv  Detail & Related papers  (2026-05-25T11:36:19Z)
• Performance Gains in Quantum SAT Solvers Using ESOP Encoding [1.3267048706241158]
  We investigate an Exclusive-Sum-of-Products-based CNF representation tailored for quantum SAT solving.<n>We derive tighter upper bounds on qubit requirements and Clifford+$T$ gate counts for Grover-based SAT solvers when e-CNF encodings are employed.<n> Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources.
  arXiv  Detail & Related papers  (2026-05-15T17:17:07Z)
• Post-Quantum Cryptography from Quantum Stabilizer Decoding [40.84312119358882]
  Post-quantum cryptography currently rests on a small number of hardness assumptions.<n>We argue that decoding random quantum stabilizer codes is an excellent candidate.<n>We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania.
  arXiv  Detail & Related papers  (2026-03-19T16:35:31Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• S-Leak: Leakage-Abuse Attack Against Efficient Conjunctive SSE via s-term Leakage [13.222101654411281]
  Conjunctive Searchable Encryption (CSSE) enables secure conjunctive searches over encrypted data.<n>In this paper, we reveal a fundamental vulnerability in state-of-the-art CSSE schemes: s-term leakage.<n>We propose S-Leak, the first passive attack framework that progressively recovers conjunctive queries by exploiting s-term leakage and global leakage.
  arXiv  Detail & Related papers  (2025-07-05T15:53:31Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem.<n>These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem.<n>We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Recovering AES Keys with a Deep Cold Boot Attack [91.22679787578438]
  Cold boot attacks inspect the corrupted random access memory soon after the power has been shut down. In this work, we combine a novel cryptographic variant of a deep error correcting code technique with a modified SAT solver scheme to apply the attack on AES keys. Our results show that our methods outperform the state of the art attack methods by a very large margin.
  arXiv  Detail & Related papers  (2021-06-09T07:57:01Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  Continuous-variable quantum key distribution (QKD) employs the quadratures of a bosonic mode to establish a secret key between two remote parties. We consider a protocol with homodyne detection in the general setting of composable finite-size security. In particular, we analyze the high signal-to-noise regime which requires the use of high-rate (non-binary) low-density parity check codes.
  arXiv  Detail & Related papers  (2021-03-30T18:02:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.