QMA Complete Quantum-Enhanced Kyber: Provable Security Through CHSH Nonlocality

• URL: http://arxiv.org/abs/2511.12318v1
• Date: Sat, 15 Nov 2025 18:31:36 GMT
• Title: QMA Complete Quantum-Enhanced Kyber: Provable Security Through CHSH Nonlocality
• Authors: Ilias Cherkaoui, Indrakshi Dey,
• Abstract summary: Post-quantum cryptography must secure large-scale communication systems against quantum adversaries.<n>We introduce the first Clauser-e-Shimony-Holt (CHSH)-certified Kyber protocol, which embeds quantum non-locality verification directly within the key exchange phase.<n>The resulting CHSH-augmented Kyber scheme establishes a mathematically rigorous, hybrid post-quantum framework.
• Score: 1.5469452301122173
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Post-quantum cryptography (PQC) must secure large-scale communication systems against quantum adversaries where classical hardness alone is insufficient and purely quantum schemes remain impractical. Lattice-based key encapsulation mechanisms (KEMs) such as CRYSTALS-Kyber provide efficient quantum-resistant primitives but rely solely on computational hardness assumptions that are susceptible to hybrid classical-quantum attacks. To overcome this limitation, we introduce the first Clauser-Horne-Shimony-Holt (CHSH)-certified Kyber protocol, which embeds quantum non-locality verification directly within the key exchange phase. The proposed design integrates CHSH entanglement tests using Einstein-Podolsky-Rosen (EPR) pairs to yield measurable quantum advantage values exceeding classical correlation limits, thereby coupling information--theoretic quantum guarantees with lattice-based computational security. Formal reductions demonstrate that any polynomial-time adversary breaking the proposed KEM must either solve the Module Learning With Errors (Module-LWE) problem or a Quantum Merlin-Arthur (QMA)-complete instance of the 2-local Hamiltonian problem, under the standard complexity assumption QMA $\subset$ NP. The construction remains fully compatible with the Fujisaki-Okamoto (FO) transform, preserving chosen-ciphertext attack (CCA) security and Kyber's efficiency profile. The resulting CHSH-augmented Kyber scheme therefore establishes a mathematically rigorous, hybrid post-quantum framework that unifies lattice cryptography and quantum non-locality to achieve verifiable, composable, and forward-secure key agreement.

Related papers

• 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)
• QuantumShield: Multilayer Fortification for Quantum Federated Learning [7.283533791778357]
  We propose a quantum-secure federated learning (QFL) framework designed to safeguard distributed learning systems against the emerging threat of quantum-enabled adversaries.<n>We integrate and rigorously evaluate advanced quantum and post-quantum protocols to fortify the QFL process against both classical and quantum threats.
  arXiv  Detail & Related papers  (2025-10-27T02:59:33Z)
• Enhanced Rényi Entropy-Based Post-Quantum Key Agreement with Provable Security and Information-Theoretic Guarantees [0.0]
  This paper presents an enhanced post-quantum key agreement protocol based on R'enyi entropy, addressing vulnerabilities in the original construction while preserving information-theoretic security properties.<n>We develop a theoretical framework leveraging entropy-preserving operations and secret-shared verification to achieve provable amplification against quantum adversaries.<n>Key innovations include a confidentiality-preserving verification mechanism using distributed oracle commitments, tightened min-entropy bounds with guaranteed non-negativity, and composable security proofs in the quantum universal composability framework.
  arXiv  Detail & Related papers  (2025-08-28T00:42:49Z)
• Performance and Storage Analysis of CRYSTALS Kyber as a Post Quantum Replacement for RSA and ECC [45.88028371034407]
  CRYSTALS-Kyber is a post-quantum cryptographic solution standardized by NIST in 2022.<n>This study evaluates Kyber's practical viability through performance testing across various implementation schemes.
  arXiv  Detail & Related papers  (2025-08-03T09:53:45Z)
• Public-Key Quantum Authentication and Digital Signature Schemes Based on the QMA-Complete Problem [0.0]
  We propose a quantum authentication and digital signature protocol whose security is founded on the Quantum Merlin Arthur(QMA)-completeness of the consistency of local density matrices.<n>We provide a rigorous security analysis, proving the scheme's unforgeability against adaptive chosen-message attacks by quantum adversaries.
  arXiv  Detail & Related papers  (2025-06-20T10:56:50Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• A Fully Device-Independent Ternary Quantum Key Distribution Protocol Based on the Impossible Colouring Game [0.59374762912328]
  We propose a quantum key distribution protocol based on the two-party Impossible Colouring pseudo-telepathy game.<n>The protocol harnesses Bell inequality violations that arise from contextuality in the Kochen-Specker theorem.<n>It operates within an adequate security framework and demonstrates an improved key generation rate compared to standard quantum key distribution schemes.
  arXiv  Detail & Related papers  (2025-05-21T14:52:31Z)
• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Implementing an information-theoretically secure Byzantine agreement with quantum signed message solution [9.643164830645038]
  Byzantine agreement (BA) enables all honest nodes in a decentralized network to reach consensus.<n>We propose a quantum signed Byzantine agreement (QSBA) protocol based on the quantum signed message (QSM) scheme.<n>Our protocol achieves information-theoretic security using only QKD-shared key resources between network nodes.
  arXiv  Detail & Related papers  (2025-02-08T10:30:37Z)
• Practical hybrid PQC-QKD protocols with enhanced security and performance [44.8840598334124]
  We develop hybrid protocols by which QKD and PQC inter-operate within a joint quantum-classical network. In particular, we consider different hybrid designs that may offer enhanced speed and/or security over the individual performance of either approach.
  arXiv  Detail & Related papers  (2024-11-02T00:02:01Z)
• Experimental quantum key distribution certified by Bell's theorem [0.0]
  cryptographic key exchange protocols traditionally rely on computational conjectures to provide security against eavesdropping attacks. quantum key distribution protocols provide information-theoretic security against such attacks. However, quantum protocols are subject to a new class of attacks exploiting implementation defects in the physical devices involved. We present here the experimental realisation of a complete quantum key distribution protocol immune to these vulnerabilities.
  arXiv  Detail & Related papers  (2021-09-29T17:52:48Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

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.