Post-Quantum Cryptography from Quantum Stabilizer Decoding

• URL: http://arxiv.org/abs/2603.19110v1
• Date: Thu, 19 Mar 2026 16:35:31 GMT
• Title: Post-Quantum Cryptography from Quantum Stabilizer Decoding
• Abstract summary: 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.
• Score: 40.84312119358882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied LPN problem -- is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practical: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE, and our OT is round-optimal. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suit of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Quantum Homomorphic Encryption: Towards Practical and Private Computation on Untrusted Quantum Hardware [0.0]
  We propose a universal quantum homomorphic encryption framework developed from the Quantum One-Time Pad scheme.<n>Our approach maintains information-theoretic security and supports a broad class of quantum operations on encrypted quantum states.<n>This work takes a step toward bridging the gap between theoretical quantum homomorphic encryption and practical realization on near-term quantum hardware.
  arXiv  Detail & Related papers  (2026-04-21T09:20:08Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs.<n>This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• Encryption with Quantum Public Keys [1.7725414095035827]
  We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions. We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
  arXiv  Detail & Related papers  (2023-03-09T16:17:19Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Quantum oblivious transfer: a short review [0.06554326244334865]
  We study the concept of oblivious transfer in the area of theoretical quantum cryptography. We review the impossibility results that daunt this primitive and discuss several quantum security models under which it is possible to prove QOT security.
  arXiv  Detail & Related papers  (2022-06-06T15:19:26Z)
• Proposal for Quantum Ciphertext-Policy Attribute-Based Encryption [0.0]
  A Quantum Ciphertext-Policy Attribute-Based Encryption scheme (QCP-ABE) has been presented. A Semi Quantum version of the scheme has also been considered.
  arXiv  Detail & Related papers  (2022-03-21T11:22:09Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

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.